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