mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Puzzles (https://www.mersenneforum.org/forumdisplay.php?f=18)
-   -   June 2021 (https://www.mersenneforum.org/showthread.php?t=26866)

Xyzzy 2021-06-02 00:06

June 2021
 
[url]https://www.research.ibm.com/haifa/ponderthis/challenges/June2021.html[/url]

uau 2021-06-02 00:50

The second required property is completely meaningless as currently phrased. I assume it should say the numbers have to be at least 2.

LaurV 2021-06-02 07:56

What do you mean? That is the most important filtering criteria. Under a million, there are only about 40 numbers which suffice, and of them, less that a handful are prime.

Dieter 2021-06-02 08:12

[QUOTE=LaurV;579751]What do you mean? That is the most important filtering criteria. Under a million, there are only about 40 numbers which suffice, and of them, less that a handful are prime.[/QUOTE]

That's my opinion, too. I have only 246 under 2**64.

retina 2021-06-02 08:20

[QUOTE=uau;579736]The second required property is completely meaningless as currently phrased. I assume it should say the numbers have to be at least 2.[/QUOTE][QUOTE=LaurV;579751]What do you mean? That is the most important filtering criteria. Under a million, there are only about 40 numbers which suffice, and of them, less that a handful are prime.[/QUOTE]You are both correct.

The page has been edited to show "... > 1". Before it said "... ≥ 1"

LaurV 2021-06-02 08:41

[QUOTE=retina;579755]The page has been edited to show "... > 1". Before it said "... ≥ 1"[/QUOTE]
Oh...

swellman 2021-06-22 17:15

Fun problem. Believe I got a correct answer.

Anybody go for the bonus *?

0scar 2021-06-22 20:10

My bottleneck is primality proving.
I used YAFU implementation of APR-CL for solutions with less than 2k digits.

Dr Sardonicus 2021-06-23 01:14

[QUOTE=swellman;581555]Fun problem. Believe I got a correct answer.

Anybody go for the bonus *?[/QUOTE]Apparently. The page with the challenge currently lists fifty-seven solvers who earned the bonus.

Yusuf 2021-06-23 04:31

[QUOTE=swellman;581555]Fun problem. Believe I got a correct answer.

Anybody go for the bonus *?[/QUOTE]

Solved it today, largest solution I found so far is greater than 10^545

Kebbaj 2021-06-24 22:02

[QUOTE=Yusuf;581598]Solved it today, largest solution I found so far is greater than 10^545[/QUOTE]

10 ^ 545 good!
Go to the maximum yusuf.
we compare our max after the solution. if you want?

Yusuf 2021-06-24 23:40

[QUOTE=Kebbaj;581802]10 ^ 545 good!
Go to the maximum yusuf.
we compare our max after the solution. if you want?[/QUOTE]

Sure, I'll let you know what my largest solution is once the challenge ends

Kebbaj 2021-06-25 08:19

[QUOTE=Yusuf;581814]Sure, I'll let you know what my largest solution is once the challenge ends[/QUOTE]

Ok yusuf.
Thinks.
:smile:

Dr Sardonicus 2021-06-25 14:16

[QUOTE=Yusuf;581598]Solved it today, largest solution I found so far is greater than 10^545[/QUOTE]This is inspiring! My original, stupidly written and embarrassingly slow script would still be running to try to reach that high. It did, however, quickly produce solutions > 10^100 which I submitted in early June.

I later had a simple idea that greatly improved my script. I only pushed to 10^400, though.

But when I saw 10^545, how could I resist pushing further? I can report that, if my improved script is writ right, there are two solutions between 10^545 and 10^600.

uau 2021-06-25 18:57

With Sage, generating all solutions up to 10^1000 was pretty fast (there are 25 including the example solutions). I tried generating one with more digits, and got a solution above 10^9000.

Dr Sardonicus 2021-06-25 20:54

[QUOTE=uau;581907]With Sage, generating all solutions up to 10^1000 was pretty fast (there are 25 including the example solutions). I tried generating one with more digits, and got a solution above 10^9000.[/QUOTE]Thanks for giving me a way to check my script! It was easy to adjust it to check up to 10^1000. Lo and behold, 25 solutions! :tu:

0scar 2021-06-26 04:41

[QUOTE=uau;581907]With Sage, generating all solutions up to 10^1000 was pretty fast (there are 25 including the example solutions). I tried generating one with more digits, and got a solution above 10^9000.[/QUOTE]

Your findings below 10^1000 also match mine.
25 solutions up to 10^1000.
34 solutions up to 10^2000.
46 solutions up to 10^3000. Or less?
Last 12 candidates only passed a BPSW test, I stopped primality proving after 10^2000 because APR-CL was becoming too lengthy. Anyway, my aged YAFU implementation can only prove numbers up to 6021 digits, so your finding above 10^9000 is doubly remarkable to me.
I wonder how long did you take to prove it prime, and if you used some code specially written for Leyland numbers.

axn 2021-06-26 06:45

Are people referring to [url]http://www.primefan.ru/xyyxf/primes.html[/url] ?

Dr Sardonicus 2021-06-26 12:14

[QUOTE=0scar;581940]<snip>
I wonder how long did you take to prove it prime, and if you used some code specially written for Leyland numbers.[/QUOTE]Heck, I just used BPSW [Pari-GP's ispseudoprime() function]. If any of the "small" Leyland numbers I was looking at had "passed" that test but were actually composite, I reckoned that would already be known. I did state in my submitted solution that the numbers had only "passed" a BPSW test.

I note that Pari-GP had no trouble finding representations of the solutions by the quadratic forms specified.

uau 2021-06-26 21:46

[QUOTE=0scar;581940]I wonder how long did you take to prove it prime, and if you used some code specially written for Leyland numbers.[/QUOTE]
I didn't "prove" it prime - in fact I explicitly turned proofs off in Sage to speed things up (I'm not sure why they're enabled by default, seems silly to me). The unrealistic chance that a probabilistic primality test could return a wrong result is a much less relevant worry than the script being buggy, other software error on the machine, or even a hardware failure.

LaurV 2021-06-27 02:37

[QUOTE=axn;581948]Are people referring to ?[/QUOTE]
Grrr... you kinda spoiled it :lol:

0scar 2021-07-01 03:25

[QUOTE=LaurV;582023]Grrr... you kinda spoiled it :lol:[/QUOTE]

Actually, it seems that I spoiled it before. Within this thread, I was the first one to say "Leyland" (should I say "xilman"?)

Wikipedia page about Leyland numbers mentions the largest known Leyland proven primes and references XYYXF's search project.
This forum also has many threads about Leyland prp finding / primality proving.

Dr Sardonicus 2021-07-05 11:44

The solution promised for noon EST on the Fourth of July isn't up yet.

Would it be OK if I posted one here?

SmartMersenne 2021-07-05 13:23

[QUOTE=Dr Sardonicus;582611]The solution promised for noon EST on the Fourth of July isn't up yet.

Would it be OK if I posted one here?[/QUOTE]

They allow answers until the last minute. Why don't you wait a few more days.

Dr Sardonicus 2021-07-05 14:07

Hmm, I don't see any deadline posted, and couldn't find any actual rules about when submissions would be accepted, so I guess the safe assumption is that they'll accept solutions until they post their own.

I was surprised that they gave "12PM" (noon) EST on the Fourth of July as the posting date for the solution. For one thing, "EST" is Eastern Standard Time, a time zone for the eastern USA and Canada. However, at this time of year, the eastern USA is on EDT, Eastern Daylight Time. Also, the Fourth of July is a holiday here in the good ol' USA, and this year fell on a Sunday, so a lot of folks are off work today. Of the folks who have to go to work today, a lot will probably be too hung-over to get much done.

SmartMersenne 2021-07-05 14:51

[QUOTE=Dr Sardonicus;582619]Hmm, I don't see any deadline posted, and couldn't find any actual rules about when submissions would be accepted, so I guess the safe assumption is that they'll accept solutions until they post their own.

I was surprised that they gave "12PM" (noon) EST on the Fourth of July as the posting date for the solution. For one thing, "EST" is Eastern Standard Time, a time zone for the eastern USA and Canada. However, at this time of year, the eastern USA is on EDT, Eastern Daylight Time. Also, the Fourth of July is a holiday here in the good ol' USA, and this year fell on a Sunday, so a lot of folks are off work today. Of the folks who have to go to work today, a lot will probably be too hung-over to get much done.[/QUOTE]

They are never on time, especially the new puzzlemaster.

uau 2021-07-07 13:16

There's a solution link now - but currently it doesn't seem to work... (shows some general page)

SmartMersenne 2021-07-07 20:52

[QUOTE=uau;582766]There's a solution link now - but currently it doesn't seem to work... (shows some general page)[/QUOTE]

I don't think they care enough.

Dr Sardonicus 2021-07-08 11:34

[QUOTE=uau;582766]There's a solution link now - but currently it doesn't seem to work... (shows some general page)[/QUOTE]Here's the solution - but first, a word from [strike]our sponsor[/strike] [i][b]us![/b][/i]

SmartMersenne 2021-07-08 19:50

[QUOTE=Dr Sardonicus;582811]Here's the solution - but first, a word from [strike]our sponsor[/strike] [i][b]us![/b][/i][/QUOTE]

Exactly! :grin:

Max0526 2021-07-11 18:22

[URL]https://www.research.ibm.com/haifa/ponderthis/solutions/June2021.html[/URL]
After days of pointing to the wrong page, the easiest solution finally showed up today (a week after July 4), it has no closing bracket at the end (sent them an email), and doesn't follow the format suggested initially (there should be no brackets at all). Disappointing.

SmartMersenne 2021-07-11 20:44

[QUOTE=Max0526;583022][URL]https://www.research.ibm.com/haifa/ponderthis/solutions/June2021.html[/URL]
After days of pointing to the wrong page, the easiest solution finally showed up today (a week after July 4), it has no closing bracket at the end (sent them an email), and doesn't follow the format suggested initially (there should be no brackets at all). Disappointing.[/QUOTE]

Yes, unfortunately.
I felt like the previous puzzlemaster was slow, but it turns out he was much faster than the current one. And he cared, because he would immediate engage into a conversation after people send their solutions. Now, we can't even get the solutions in time, and we have to wait at least 10 days to know if the solutions we submitted are correct.

Yusuf 2021-07-12 03:20

1 Attachment(s)
[QUOTE=Kebbaj;581802]10 ^ 545 good!
Go to the maximum yusuf.
we compare our max after the solution. if you want?[/QUOTE]

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.

SmartMersenne 2021-07-12 03:54

[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]

Yusuf 2021-07-12 04:16

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

Dr Sardonicus 2021-07-12 12:34

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)])
);
);
);
);
}[/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:28.

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