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
c := 2050773823560610053645500687837518188141079884796356829115939899254225527
By using the prevprime command I can do somewhat better. But I see there's still a lot of range to sieve.