June 2021

[SmartMersenne]

Originally Posted by Yusuf

Hello, how many digits was your max solution? The highest one I got is 386,642 digits (I attached the full solution), although it is a probable prime, not proven.

How do you check the primality of such large numbers? The conjectures I know don't go beyond 10³⁰

[Yusuf]

Originally Posted by SmartMersenne

How do you check the primality of such large numbers? The conjectures I know don't go beyond 10³⁰

I first found it on OpenPFGW using the 3-PRP test, then I tested it in Mathematica using PrimeQ (this takes a while to run).
For proven primes the best solution I have is 30008 digits (proof of primality provided here: https://www.mersenneforum.org/showthread.php?t=17554)

[Dr Sardonicus]

We assume that 1 < i < j, i + j is odd, and take p = i^j + j^i. One of the summands is an even integer divisible by 8, and the other is the square of an odd integer, hence p == 1 (mod 8).

Thus, if p is prime, -1 and 2 (hence also -2) are automatically quadratic residues (mod p). Consequently, if p is prime, it will automatically be simultaneously of the forms p = a^2 + b^2 and p = c^2 + 2*d^2.

In order that p = e^2 + 7*f^2, it is necessary and sufficient that -7 be a quadratic residue (mod p). By quadratic reciprocity, (-7/p) = (p/7), which is +1 when p == 1, 2, or 4 (mod 7).

In the following Pari-GP script, I entered the bounds on i and j by hand for my given bound B = 10^1000. I only checked p (mod 7) before applying ispseudoprime(p). I didn't bother excluding multiples of small primes. I didn't bother with primality proofs.

For any p that "passed" ispseudoprime(), a BPSW test, I had Pari compute the representations of p by a^2 + b^2, c^2 + 2*d^2, and e^2 + 7*f^2, and write things to a file (whose name is munged here).

I left the required pairs as Pari-GP vectors and put them all into a vector for each p rather than printing out the components for each part on a separate line.

{
h=10^1000;
qm1=Qfb(1,0,1);
qm2=Qfb(1,0,2);
qm7=Qfb(1,0,7);
for(i=2,400,
forstep(j=i+1,3321,2,
p=i^j+j^i;
if(p>h,break);
r7=p%7;
if(r7==1||r7==2||r7==4,
if(ispseudoprime(p),
write("xxxxx.txt",[[i,j],log(p)/log(10),qfbsolve(qm1,p),qfbsolve(qm2,p),qfbsolve(qm7,p)])
);
);
);
);
}

Below is an extract from the file, the seven smallest values of p output. The script found 25 values of p < 10^1000.

[[2, 15], 4.5184218070339578416226065279870946140, [143, 112], [15, 128], [25, 68]]
[[2, 21], 6.3217212250389696324375270116720426137, [1148, 883], [21, 1024], [419, 524]]
[[3, 56], 26.718790264301096488521708315361225868, [22876788410036, 13604036279], [22775212789083, 1522713932318], [21366121856593, 3089994679528]]
[[15, 32], 37.634920289781800126890189475518660515, [4757970449709757697, 4528322595298140128], [6568408355712890625, 137438953472], [4041642495815468009, 1957006250935978996]]
[[8, 69], 62.313209102444107409243951207970056541, [11841154645793353307939766561488, 8091670181090999017194080387825], [22667121, 10141204801825835211973625643008], [11960688081436004850435605405839, 2991177749022841162189864734208]]
[[9, 76], 72.522430717388690468844241294777526998, [1805424981180291818717129190170791284, 265211241553380780756413693228540681], [639424995469286446934317743090032827, 1208518109191013687379511381167248838], [1770791279158998015353160372698187673, 166559560762844711650695192072656028]]
[[34, 75], 114.86091877816913428154315917896225426, [2341523227685802973317116937233099044272373695299363945845, 1333030648893058553789277061401358577881136005688481248832], [1688720447290015642452516760229506509635032011397287059257, 1484574852876236578030099116366398251085237658488907102090], [1393905404716216131892233482794414472900782174600716102781, 871511778412605044471256876208116162244764418001268613572]]