¿Cómo puedo acelerar la búsqueda de un número especial?

Question

Un número $N$ es dado. El objeto es encontrar el menor entero no negativo $k$, de tal manera que $N+k$ es el producto de tres números primos, cada uno con el mismo número de dígitos decimales.

Por ejemplo, para $N=33^{33}$, el más pequeño de $k$ es $27484$ porque $$33^{33}+27484$$ splits in three $17$-digit prime factors and no smaller number beyond $N$ tiene esta propiedad.

Por supuesto, la fuerza bruta considera como un número, y el primer paso es tamizado de pequeños factores, pero es una importante aceleración posible ? En particular, estoy interesado en la solución de $N=44^{44}$

Answer 1

¿No sería más fácil construir el número en lugar de buscar? No sé cuál es el algoritmo de Maple comandos nextprime comando, pero devuelve los números primos de este tamaño (25 dígitos) al instante. Yo lo hice

con(numtheory):

a:=floor(evalf(44^(44/3),26));

                a := 1270493912412969033418155

p1:=comandos nextprime(a);

               p1 := 1270493912412969033418201

p2:=comandos nextprime(p1);

               p2 := 1270493912412969033418217

p3:=comandos nextprime(p2);

               p3 := 1270493912412969033418231

c:=p1*p2*p3;

c := 2050773823560610053645500687837518188141079884796356829115939899254225527

k:-c-44^44;

     295078665142152654900048275749281821022933064858231

Mediante el uso de la prevprime comando que puedo hacer algo mejor. Pero veo que todavía hay un montón de variedad al tamiz.