6
$\begingroup$

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}$

$\endgroup$
6
  • $\begingroup$ By 'sieving out small factors', do you mean sieving multiples of squares of primes? Otherwise, that's something that should speed things up at least a little. $\endgroup$
    – Mastrem
    Commented Nov 14, 2018 at 9:54
  • $\begingroup$ @Mastrem I mean sieving out the small prime factors. The desired number cannot have small factors. For my number, the prime factors all must have $25$ digits $\endgroup$
    – Peter
    Commented Nov 14, 2018 at 10:04
  • $\begingroup$ O yes, I missed the part about all three having the same amound of digits. Well, I suppose you could sieve the squares of large primes too, but that probably won't give any significant speedup $\endgroup$
    – Mastrem
    Commented Nov 14, 2018 at 10:07
  • $\begingroup$ @Mastrem I can't follow. If I rule out $p$ as a prime factor, then $p^2$ is ruled out as well. $\endgroup$
    – Peter
    Commented Nov 14, 2018 at 10:08
  • $\begingroup$ Yes, but you only filter small $p$. For large primes, $p$ can be a factor of $N+k$, but $p^2$ can't be, since $N+k$ has to be the product of three distinct primes, right? $\endgroup$
    – Mastrem
    Commented Nov 14, 2018 at 10:10

1 Answer 1

Reset to default
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .