How to speed up the search for a special number

elementary-number-theorynumber theoryprime factorizationprime numbers

A number $N$ is given. The object is to find the smallest nonnegative integer $k$, such that $N+k$ is the product of three distinct primes, each having the same number of decimal digits.

For example, for $N=33^{33}$, the smallest $k$ is $27484$ because $$33^{33}+27484$$ splits in three $17$-digit prime factors and no smaller number beyond $N$ has this property.

Of course, brute force finds such a number, and the first step is sieving out small factors, but is a significant speed-up possible ? In particular, I am interested in the solution for $N=44^{44}$

Best Answer

Wouldn't it be easier to construct the number rather then search for it? I don't know what the algorithm is for Maple's nextprime command, but it returns primes of this size (25 digits) instantly. I did

with(numtheory):

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

                a := 1270493912412969033418155

p1:=nextprime(a);

               p1 := 1270493912412969033418201

p2:=nextprime(p1);

               p2 := 1270493912412969033418217

p3:=nextprime(p2);

               p3 := 1270493912412969033418231

c:=p1*p2*p3;

c := 2050773823560610053645500687837518188141079884796356829115939899254225527

k:-c-44^44;

     295078665142152654900048275749281821022933064858231

By using the prevprime command I can do somewhat better. But I see there's still a lot of range to sieve.

Related Question