[math-fun] Exponentially many needles in a double-exponential haystack
Dear math-funsters, It's been conjectured that for all n above some small bound that I forget (maybe 24?), you can arrange the numbers from 1 to n in a circle so that every two adjoining numbers sum to a perfect square. I believe this conjecture is due to Richard Guy. Is this attribution correct? Back in August 2018, I asked Richard about the problem; he replied "I can't give the BEST reference. Indeed, I can't give ANY (published) reference. Am copying to Elwyn Berlekamp, who has given talks on this and may have published. Let me see if I have any files that I can attach. R." Berlekamp sent me a PowerPoint file that touched on a related problem: arranging the numbers from 1 to n along a *path* so that every two adjoining numbers sum to a perfect square. (Of course every solution to the circle problem is a solution to the path problem as well.) Has anything been written about these two problems? A curious feature of both problems (I've been told) is that it's not too hard to find solutions for *individual* values of n, but devilishly hard to find systematic solutions that apply to *lots* of values of n. If I recall correctly, Guy described the problem as one of "looking for exponentially many needles in a double-exponential haystack". One of the Mathematical Enchantments essays I was thinking of writing (unless someone's already written it!) is a collection of problems with a similar flavor; specifically, problems of the form "Show that for all n, the set A_n is nonempty" with the property that for each specific n within computational range it's easy to construct elements of A_n, but not in a systematic way that would permit us to prove that A_n is nonempty for all n. The situation would be especially poignant if we couldn't even prove that A_n is nonempty for infinitely many n. I'm thinking it might be nice to write this essay soon, in Richard's honor. Another example of a "hay in a haystack" problem is the the Bricklayer's Challenge (which IIRC Richard named the Barrycades problem in honor of its inventor Barry Cipra). I'll check with Barry to see what he knows about the status of the problem. Do you have a favorite "hay in a haystack" problem? Thanks, Jim Propp
I'll plug RKG's paper "Building Barrycades and Constructing Corrals" which appears "Barrycades and Septoku", a recent AMS / MAA Spectrum book (Vol 100), which you can find at https://bookstore.ams.org/spec-100 On Wed, Apr 1, 2020 at 6:32 PM James Propp <jamespropp@gmail.com> wrote:
Dear math-funsters,
It's been conjectured that for all n above some small bound that I forget (maybe 24?), you can arrange the numbers from 1 to n in a circle so that every two adjoining numbers sum to a perfect square. I believe this conjecture is due to Richard Guy. Is this attribution correct?
Back in August 2018, I asked Richard about the problem; he replied
"I can't give the BEST reference. Indeed, I can't give ANY (published) reference. Am copying to Elwyn Berlekamp, who has given talks on this and may have published. Let me see if I have any files that I can attach. R."
Berlekamp sent me a PowerPoint file that touched on a related problem: arranging the numbers from 1 to n along a *path* so that every two adjoining numbers sum to a perfect square. (Of course every solution to the circle problem is a solution to the path problem as well.)
Has anything been written about these two problems?
A curious feature of both problems (I've been told) is that it's not too hard to find solutions for *individual* values of n, but devilishly hard to find systematic solutions that apply to *lots* of values of n.
If I recall correctly, Guy described the problem as one of "looking for exponentially many needles in a double-exponential haystack".
One of the Mathematical Enchantments essays I was thinking of writing (unless someone's already written it!) is a collection of problems with a similar flavor; specifically, problems of the form "Show that for all n, the set A_n is nonempty" with the property that for each specific n within computational range it's easy to construct elements of A_n, but not in a systematic way that would permit us to prove that A_n is nonempty for all n. The situation would be especially poignant if we couldn't even prove that A_n is nonempty for infinitely many n.
I'm thinking it might be nice to write this essay soon, in Richard's honor.
Another example of a "hay in a haystack" problem is the the Bricklayer's Challenge (which IIRC Richard named the Barrycades problem in honor of its inventor Barry Cipra). I'll check with Barry to see what he knows about the status of the problem.
Do you have a favorite "hay in a haystack" problem?
Thanks,
Jim Propp _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Thane Plambeck tplambeck@gmail.com http://counterwave.com/
Thane, thank you for mentioning the book (and also for the choice of title — I’m enormously and embarrassingly pleased to have my name embedded in it, and forever indebted to Richard Guy for his wordplay). I received a copy in the mail last week. As for progress in what I still tend to call the Bricklayer’s Challenge, a student in Germany emailed me a couple of years ago reporting on computations that had found (rotationally symmetric) solutions for even numbers congruent to 2 mod 4 up to 110. I forwarded his email to Jim (and Richard) at the time; I can do so again to anyone interested. However I’m not sure how well the Bricklayer’s Challenge fits Jim’s criterion for a problem where it’s easy to find solutions but hard (if not impossible) to prove they exist; my impression is that the barrycade needles rapidly get hard to find. (Also, to my knowledge, the only evidence that there are exponential many needles is Brian Hayes’s calculation that there are 2184 different solutions for 2n=6.) Barry On Apr 1, 2020, at 10:35 PM, Thane Plambeck <tplambeck@gmail.com> wrote: I'll plug RKG's paper "Building Barrycades and Constructing Corrals" which appears "Barrycades and Septoku", a recent AMS / MAA Spectrum book (Vol 100), which you can find at https://bookstore.ams.org/spec-100 <https://bookstore.ams.org/spec-100> On Wed, Apr 1, 2020 at 6:32 PM James Propp <jamespropp@gmail.com <mailto:jamespropp@gmail.com>> wrote: Dear math-funsters, It's been conjectured that for all n above some small bound that I forget (maybe 24?), you can arrange the numbers from 1 to n in a circle so that every two adjoining numbers sum to a perfect square. I believe this conjecture is due to Richard Guy. Is this attribution correct? Back in August 2018, I asked Richard about the problem; he replied "I can't give the BEST reference. Indeed, I can't give ANY (published) reference. Am copying to Elwyn Berlekamp, who has given talks on this and may have published. Let me see if I have any files that I can attach. R." Berlekamp sent me a PowerPoint file that touched on a related problem: arranging the numbers from 1 to n along a *path* so that every two adjoining numbers sum to a perfect square. (Of course every solution to the circle problem is a solution to the path problem as well.) Has anything been written about these two problems? A curious feature of both problems (I've been told) is that it's not too hard to find solutions for *individual* values of n, but devilishly hard to find systematic solutions that apply to *lots* of values of n. If I recall correctly, Guy described the problem as one of "looking for exponentially many needles in a double-exponential haystack". One of the Mathematical Enchantments essays I was thinking of writing (unless someone's already written it!) is a collection of problems with a similar flavor; specifically, problems of the form "Show that for all n, the set A_n is nonempty" with the property that for each specific n within computational range it's easy to construct elements of A_n, but not in a systematic way that would permit us to prove that A_n is nonempty for all n. The situation would be especially poignant if we couldn't even prove that A_n is nonempty for infinitely many n. I'm thinking it might be nice to write this essay soon, in Richard's honor. Another example of a "hay in a haystack" problem is the the Bricklayer's Challenge (which IIRC Richard named the Barrycades problem in honor of its inventor Barry Cipra). I'll check with Barry to see what he knows about the status of the problem. Do you have a favorite "hay in a haystack" problem? Thanks, Jim Propp _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <mailto:math-fun@mailman.xmission.com> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun <https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun> -- Thane Plambeck tplambeck@gmail.com <mailto:tplambeck@gmail.com> http://counterwave.com/ <http://counterwave.com/>
Stan Wagon steered me toward https://oeis.org/A090461 where I find the assertion The conjecture has been proved: every n >= 25 is in the sequence, moreover for n >= 32 there is a Hamiltonian cycle, see Mersenneforum topic for a code and deterministic algorithm to find a sequence. - Robert Gerbicz <https://oeis.org/wiki/User:Robert_Gerbicz>, Jan 21 2018 Does anyone know anything about Gerbicz and/or the Mersenneforum? Jim On Wed, Apr 1, 2020 at 9:32 PM James Propp <jamespropp@gmail.com> wrote:
Dear math-funsters,
It's been conjectured that for all n above some small bound that I forget (maybe 24?), you can arrange the numbers from 1 to n in a circle so that every two adjoining numbers sum to a perfect square. I believe this conjecture is due to Richard Guy. Is this attribution correct?
Back in August 2018, I asked Richard about the problem; he replied
"I can't give the BEST reference. Indeed, I can't give ANY (published) reference. Am copying to Elwyn Berlekamp, who has given talks on this and may have published. Let me see if I have any files that I can attach. R."
Berlekamp sent me a PowerPoint file that touched on a related problem: arranging the numbers from 1 to n along a *path* so that every two adjoining numbers sum to a perfect square. (Of course every solution to the circle problem is a solution to the path problem as well.)
Has anything been written about these two problems?
A curious feature of both problems (I've been told) is that it's not too hard to find solutions for *individual* values of n, but devilishly hard to find systematic solutions that apply to *lots* of values of n.
If I recall correctly, Guy described the problem as one of "looking for exponentially many needles in a double-exponential haystack".
One of the Mathematical Enchantments essays I was thinking of writing (unless someone's already written it!) is a collection of problems with a similar flavor; specifically, problems of the form "Show that for all n, the set A_n is nonempty" with the property that for each specific n within computational range it's easy to construct elements of A_n, but not in a systematic way that would permit us to prove that A_n is nonempty for all n. The situation would be especially poignant if we couldn't even prove that A_n is nonempty for infinitely many n.
I'm thinking it might be nice to write this essay soon, in Richard's honor.
Another example of a "hay in a haystack" problem is the the Bricklayer's Challenge (which IIRC Richard named the Barrycades problem in honor of its inventor Barry Cipra). I'll check with Barry to see what he knows about the status of the problem.
Do you have a favorite "hay in a haystack" problem?
Thanks,
Jim Propp
I know Robert Gerbicz, of course, he has been a contributor to the OEIS for a long time. You can send him email by going to his User Page on the OEIS wiki - you gave the link - logging in to the Wiki, and clicking "email this user" Best regards Neil Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com On Wed, Apr 1, 2020 at 11:42 PM James Propp <jamespropp@gmail.com> wrote:
Stan Wagon steered me toward
where I find the assertion
The conjecture has been proved: every n >= 25 is in the sequence, moreover for n >= 32 there is a Hamiltonian cycle, see Mersenneforum topic for a code and deterministic algorithm to find a sequence. - Robert Gerbicz <https://oeis.org/wiki/User:Robert_Gerbicz>, Jan 21 2018
Does anyone know anything about Gerbicz and/or the Mersenneforum?
Jim
On Wed, Apr 1, 2020 at 9:32 PM James Propp <jamespropp@gmail.com> wrote:
Dear math-funsters,
It's been conjectured that for all n above some small bound that I forget (maybe 24?), you can arrange the numbers from 1 to n in a circle so that every two adjoining numbers sum to a perfect square. I believe this conjecture is due to Richard Guy. Is this attribution correct?
Back in August 2018, I asked Richard about the problem; he replied
"I can't give the BEST reference. Indeed, I can't give ANY (published) reference. Am copying to Elwyn Berlekamp, who has given talks on this and may have published. Let me see if I have any files that I can attach. R."
Berlekamp sent me a PowerPoint file that touched on a related problem: arranging the numbers from 1 to n along a *path* so that every two adjoining numbers sum to a perfect square. (Of course every solution to the circle problem is a solution to the path problem as well.)
Has anything been written about these two problems?
A curious feature of both problems (I've been told) is that it's not too hard to find solutions for *individual* values of n, but devilishly hard to find systematic solutions that apply to *lots* of values of n.
If I recall correctly, Guy described the problem as one of "looking for exponentially many needles in a double-exponential haystack".
One of the Mathematical Enchantments essays I was thinking of writing (unless someone's already written it!) is a collection of problems with a similar flavor; specifically, problems of the form "Show that for all n, the set A_n is nonempty" with the property that for each specific n within computational range it's easy to construct elements of A_n, but not in a systematic way that would permit us to prove that A_n is nonempty for all n. The situation would be especially poignant if we couldn't even prove that A_n is nonempty for infinitely many n.
I'm thinking it might be nice to write this essay soon, in Richard's honor.
Another example of a "hay in a haystack" problem is the the Bricklayer's Challenge (which IIRC Richard named the Barrycades problem in honor of its inventor Barry Cipra). I'll check with Barry to see what he knows about the status of the problem.
Do you have a favorite "hay in a haystack" problem?
Thanks,
Jim Propp
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (4)
-
Barry Cipra -
James Propp -
Neil Sloane -
Thane Plambeck