Arranging numbers from $1$ to $n$ such that the sum of every two adjacent numbers is a perfect power

Question

I've known that one can arrange all the numbers from $1$ to $\color{red}{15}$ in a row such that the sum of every two adjacent numbers is a perfect square.

$$8,1,15,10,6,3,13,12,4,5,11,14,2,7,9$$

Also, about two weeks ago, a colleague taught me that one can arrange all the numbers from $1$ to $\color{red}{305}$ in a row such that the sum of every two adjacent numbers is a perfect cube.

$$256,87,129, 214, 298, 45, 171, 172, 44, 299, 213, 130, 86, 257, 255,$$ $$88, 128, 215, 297, 46, 170, 173, 43, 300, 212, 131, 85, 258, 254, 89, 127, 216, 296,$$ $$ 47, 169, 174, 42, 301, 211, 132, 84, 259, 253, 90, 126, 217, 295, 48, 168, 175, 41, 302, $$ $$210, 133, 83, 260, 252, 91, 125, 218, 294, 49, 167, 176, 40, 303, 209, 134, 82, 261, 251,$$ $$ 92, 33, 183, 160, 56, 287, 225, 118, 98, 245, 267, 76, 140, 203, 13, 14, 202, 141, 75, 268,$$ $$ 244, 99, 26, 190, 153, 63, 280, 232, 111, 105, 238, 274, 69, 147, 196, 20, 7, 1, 124, 219,$$ $$ 293, 50, 166, 177, 39, 304, 208, 135, 81, 262, 250, 93, 32, 184, 159, 57, 286, 226, 117, 8,$$ $$ 19, 197, 146, 70, 273, 239, 104, 112, 231, 281, 62, 154, 189, 27, 37, 179, 164, 52, 291, 221,$$ $$ 122, 3, 5, 22, 194, 149, 67, 276, 236, 107, 109, 234, 278, 65, 151, 192, 24, 101, 242, 270,$$ $$ 73, 143, 200, 16, 11, 205, 138, 78, 265, 247, 96, 120, 223, 289, 54, 162, 181, 35, 29, 187,$$ $$156, 60, 283, 229, 114, 102, 241, 271, 72, 144, 199, 17, 108, 235, 277, 66, 150, 193, 23,$$ $$ 4, 121, 222, 290, 53, 163, 180, 36, 28, 188, 155, 61, 282, 230, 113, 103, 240, 272, 71, 145,$$ $$ 198, 18, 9, 116, 227, 285, 58, 158, 185, 31, 94, 249, 263, 80, 136, 207, 305, 38, 178, 165,$$ $$ 51, 292, 220, 123, 2, 6, 21, 195, 148, 68, 275, 237, 106, 110, 233, 279, 64, 152, 191, 25,$$ $$100, 243, 269, 74, 142, 201, 15, 12, 204, 139, 77, 266, 246, 97, 119, 224, 288, 55, 161,$$ $$ 182, 34, 30, 186, 157, 59, 284, 228, 115, 10, 206, 137, 79, 264, 248, 95$$

Here, I have a few questions.

Question 1 : For each $N\ge 2\in\mathbb N$, does there exist at least one positive integer $n\ge 2$ satisfying the following condition ?

Condition : One can arrange all the numbers from $1$ to $n$ in a row such that the sum of every two adjacent numbers is of the form $m^N$ for some $m\in\mathbb N$.

Question 2 : Can we find at least one concrete $n$ with an arragement for a given $N$?

Question 3 : How about cyclic arrangements where the sum of the first and last numbers is also a perfect power?

I would like to know any relevant references as well.

Remark : Question 1 has been asked previously on math.SE without receiving any answers.

Additional information : On math.SE, a user Micah commented, "For fixed $n$ and $N$, this is equivalent to asking whether some graph on $n$ vertices with $O(n^{1+1/N})$ edges has a Hamiltonian path. This is substantially above the threshold for a random graph to have a Hamiltonian path (which happens when the expected number of edges is $O(n\log n)$ or so), so the answer is probably "yes" unless there's some interesting structure in this specific graph that interferes with your chances."

Also, a user MJD showed a square-cyclic arrangement for $n=32$ : $$\small1,8,28,21,4,32,17,19,30,6,3,13,12,24,25,11,5,31,18,7,29,20,16,9,27,22,14,2,23,26,10,15$$

Answer 1

Not an answer, but maybe a start:

It is fairly clear why trivial cases like $n=18,$ power$=2$ don't work, after all of the sum-pairs $\neq$ a power of $2$ that are $\leq2n$ are stripped away:

Complete cycles are much easier to search for: cycleP[33, 2] (for $n=33,$ power$=2$, code below) produces

whereas cyclePall[23, 2] produces

and it is clear why nothing below $300$ish will work for power $3$ by just looking at dangling nodes of $n=200,$ power$=3$:

---

cycleP[n_, pow_] := 
With[{graph = Graph[DeleteDuplicates[Flatten[Thread[#[[1]] -> #[[2]]] & /@ 
Transpose[{Range@n, Table[If[#[[1]] == hh, #[[2]], #[[1]]] & /@ 
Select[Flatten[DeleteCases[Table[With[{aa = Transpose@{(ConstantArray[#, #]
&@nn - Range@nn), Reverse@(ConstantArray[#, #] &@nn - Range@nn)}}, 
Select[Rest@ Take[aa, Floor[Length@aa/2]], #[[1]] <= n && #[[2]] <= n &]], 
{nn, Range[2, Floor[(2 n)^(1/pow)]]^pow + 1}], {}], 1], #[[1]] == hh \[Or] #[[2]] 
== hh &], {hh, n}]}]], Sort[#1] == Sort[#2] &], DirectedEdges -> False, 
VertexLabels -> "Name"]}, Column[{Show[#, ImageSize -> 400] &@
HighlightGraph[graph, Style[FindCycle[graph, {n}], {Darker@Red, Thick}]], 
Flatten@(#[[All, 1]] & /@ FindCycle[graph, {n}])}]]

cyclePall[n_, pow_] := 
With[{cc = DeleteDuplicates[Flatten[Thread[#[[1]] -> #[[2]]] & /@ 
Transpose[{Range@n, Table[If[#[[1]] == hh, #[[2]], #[[1]]] & /@ 
Select[Flatten[DeleteCases[Table[With[{aa = Transpose@{(ConstantArray[#, #] &@nn - 
Range@nn), Reverse@(ConstantArray[#, #] &@nn - Range@nn)}}, 
Select[Rest@ Take[aa, Floor[Length@aa/2]], #[[1]] <= n && #[[2]] <= 
n &]], {nn, Range[2, Floor[(2 n)^(1/pow)]]^pow + 1}], {}], 1], #[[1]] == hh \[Or] 
#[[2]] == hh &], {hh, n}]}]], Sort[#1] == Sort[#2] &]}, With[{dd = 
Split@Sort@Join[cc[[All, 1]], cc[[All, 2]]]},
With[{jj = DeleteCases[Flatten@(If[Length@# == First@Sort[Length@# & /@ dd], #, 0] 
& /@ dd), 0]}, With[{ll = Flatten@Table[Thread[#[[1]] -> #[[2]]] & /@ 
Transpose@{ConstantArray[jj[[kk]], n], Range@n}, {kk, Length@jj}]},
With[{zz = Table[Join[{ll[[vv]]}, cc], {vv, Length@ll}]}, With[{zzz = 
DeleteCases[Table[FindCycle[Graph[zz[[ww]], DirectedEdges -> False, 
VertexLabels -> "Name"], {n}], {ww, Length@zz}], {}]}, With[{graphs = 
(HighlightGraph[Graph[cc, DirectedEdges -> False, VertexLabels -> "Name"], 
Style[#, {Darker@Red, Thick}]] & /@ zzz)},Column[{If[Length@graphs == 0, 
Show[Graph[cc, DirectedEdges -> False, VertexLabels -> "Name"], ImageSize -> 400], 
Show[#, ImageSize -> 400] & /@ graphs],#[[All, 1]] & /@ (Rest@# & /@
Flatten[zzz, 1])}]]]]]]]]

(Mathematica 10 only)

Answer 2

This is a to long for a comment:

Let $G(n,N)$ Micah's graph with vertices the numbers $1,..,n$ and edges $\{i,j\}$ if $i+j$ is a power of $N$. Your condition is satisfied if and only if $G$ contains a Hamiltonian path. (And the analogues question for a cycle if and only if $G$ contains a Hamiltonian cycle).

Let $m(N)$ be the smallest $n$ such that $G(n,N)$ contains a Hamiltonian path and $m_c(N)$ the smallest $n$ such that $G(n,N)$ contains a Hamiltonian cycle.

From a some calculations with sage one can see that $$\begin{array}{c|cc}N&m(N)&m_c(N)\\\hline1&2&3\\2&15&32\\3&305&473\\4&?(\geq9254)&9641 \\5&?&?(\geq490463)\end{array} $$ Example for $15$, $32$ and $305$ are already in your question, I calculated examples of the 473 and the 9641.

For the entries with questions marks: these are just some guesses. For $m(4)$, one can quickly see, with the help of sage that $G(9253,4)$ does not have a Hamiltonian path, and neither $G(n,4)$ for $n=9252, 9251, 9250,\dots$ or $9210$. But so far I could not find a Hamiltonian path in $G(9253,4)$, maybe somebody else can give it a try. Similarly, $G(490462,5)$ does not contain a Hamiltonian cycle.

I find the argument in your "Additional Information" quite convincing and would expect that most graphs with more than $m(N)$ (or $m_c(N)$) satisfy your condition; with possibly a few exceptions just above $m(N)$ (or $m_c(N)$). Maybe a probabilistic argument could turn this into a proof.

One could also ask about the asymptotics of $m(N)$ and $m_c(N)$ or find lower bounds for them.

---

Update: By request from martin, here is the sage code for it. For N=3, n=473 it takes .2 seconds to find the hamiltonian cycle, for N=4, n=9641 it takes 290 seconds on my computer.

def getgraph(n,N,path):
    powers=[(i+1)^N for i in range(ceil((2*n)^(1/N)))]
    G=Graph()
    G.add_vertices([1,..,n])
    edges=[]
    for p in powers:
        for i in range(1,ceil(p/2)+1):
            if i<=n and p-i<=n and p-i>0:
                edges.append([i,p-i])

    if path:   #add an extra vertex connected to all others
        G.add_vertex(0)  #to get path from cycle
        for i in [1,..,n]:
            edges.append([0,i])
    G.add_edges(edges)
    return G

path=False
n=473
N=3
time G=getgraph(n,N,path)
time hami=G.hamiltonian_cycle()

l=hami.cycle_basis()[0]
print [l[(i+l.index(int(not(path))))%len(l)] for i in range(len(l))]

Answer 3

If we do not fix the exponent, the sum of every two adjacent numbers can be any perfect power, then we obtain a larger class of solutions. I modified the Sage code provided by Moritz Firsching to handle this case, an applet can be found here:

https://cloud.sagemath.com/projects/43540988-5a9c-473c-b2f0-d5adf4168301/files/2015-08-03-161507.sagews

for given $n$ it looks for an appropriate arrangement. E.g. if $n=17,$ then one has the following cyclic arrangement $$ 1,3,5,4,12,13,14,11,16,9,7,2,6,10,15,17,8. $$