mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2021-07-12, 03:54   #34
SmartMersenne
 
Sep 2017

2×53 Posts
Default

Quote:
Originally Posted by Yusuf View Post
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 1030
SmartMersenne is offline   Reply With Quote
Old 2021-07-12, 04:16   #35
Yusuf
 
Jan 2020

23 Posts
Default

Quote:
Originally Posted by SmartMersenne View Post
How do you check the primality of such large numbers? The conjectures I know don't go beyond 1030
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)
Attached Files
File Type: txt p30008.txt (117.2 KB, 13 views)

Last fiddled with by Yusuf on 2021-07-12 at 04:16
Yusuf is offline   Reply With Quote
Old 2021-07-12, 12:34   #36
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

467110 Posts
Default Solution to June 2021 challenge

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.

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)])
);
);
);
);
}
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]]

Last fiddled with by Dr Sardonicus on 2021-07-12 at 12:36 Reason: xingif posty
Dr Sardonicus is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
June 2020 tgan Puzzles 16 2020-07-05 22:21
June 2019 Xyzzy Puzzles 5 2019-06-03 05:54
June 2017 R. Gerbicz Puzzles 14 2017-07-03 20:01
June 2016 Xyzzy Puzzles 16 2016-07-07 02:51
June 2015 Batalov Puzzles 10 2015-07-07 14:59

All times are UTC. The time now is 08:32.


Tue Aug 3 08:32:20 UTC 2021 up 11 days, 3:01, 0 users, load averages: 1.91, 2.00, 2.17

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.