- **Puzzles**
(*https://www.mersenneforum.org/forumdisplay.php?f=18*)

- - **June 2021**
(*https://www.mersenneforum.org/showthread.php?t=26866*)

[QUOTE=Yusuf;583038]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.[/QUOTE]
How do you check the primality of such large numbers? The conjectures I know don't go beyond 10[SUP]30[/SUP] |

1 Attachment(s)
[QUOTE=SmartMersenne;583041]How do you check the primality of such large numbers? The conjectures I know don't go beyond 10[SUP]30[/SUP][/QUOTE]
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: [URL="https://www.mersenneforum.org/showthread.php?t=17554"]https://www.mersenneforum.org/showthread.php?t=17554[/URL]) |

Solution to June 2021 challengeWe 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. [code]{ 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)]) ); ); ); ); }[/code] Below is an extract from the file, the seven smallest values of p output. The script found 25 values of p < 10^1000. [code][[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]][/code] |

All times are UTC. The time now is 06:38. |

Powered by vBulletin® Version 3.8.11

Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.