Organizar números de$1$ a$n$ de modo que la suma de cada dos números adyacentes sea una potencia perfecta

Question

He sabido que uno puede organizar todos los números de $1$ a $\color{red}{15}$ en una fila de modo que la suma de cada dos números adyacentes es un cuadrado perfecto.

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

También, hace unas dos semanas, un colega me enseñó que uno puede organizar todos los números de $1$ a $\color{red}{305}$ en una fila de modo que la suma de cada dos números adyacentes es un cubo perfecto.

$$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$$

Aquí, tengo un par de preguntas.

Pregunta 1 : Para cada una de las $N\ge 2\in\mathbb N$, ¿existe al menos un entero positivo $n\ge 2$ la satisfacción de las siguientes condiciones ?

Condición : Uno puede organizar todos los números de $1$ a $n$ en una fila de modo que la suma de cada dos números adyacentes es de la forma $m^N$ para algunos $m\in\mathbb N$.

Pregunta 2 : ¿se Puede encontrar al menos una hormigón $n$ con un arragement para un determinado $N$?

Pregunta 3 : ¿ cíclico acuerdos donde la suma de la primera y el último número es también un poder perfecto?

Me gustaría saber las correspondientes referencias.

Comentario : la Pregunta 1 se ha solicitado previamente en matemáticas.SÍ , sin recibir ninguna respuesta.

Información adicional : En matemáticas.SÍ, un usuario Miqueas comentó, "Para fijo $n$ e $N$, esto equivale a preguntar si algún gráfico en $n$ vértices con $O(n^{1+1/N})$ bordes tiene un camino Hamiltoniano. Este es sustancialmente por encima del umbral de azar gráfico tiene un camino Hamiltoniano (lo cual ocurre cuando el número esperado de bordes es $O(n\log n)$ o así), así que la respuesta es probablemente "sí" a menos que haya alguna interesante estructura en este gráfico que interfiere con sus posibilidades."

Además, un usuario MJD mostró una plaza-cíclico de acuerdo para $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

No una respuesta, pero quizá en un inicio:

Es bastante claro el por qué de casos triviales como $n=18,$ poder$=2$ no trabajo, después de todo, de la suma de los pares de $\neq$ un poder de $2$ que $\leq2n$ son despojados:

Completar los ciclos son mucho más fáciles de búsqueda para: cycleP[33, 2] (para $n=33,$ poder$=2$, código de abajo) produce

mientras que cyclePall[23, 2] produce

y es claro por qué nada por debajo de $300$ish de trabajo para poder $3$ simplemente observando colgando nodos de $n=200,$ poder$=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)

Answer 2

Este es un largo para un comentario:

Deje $G(n,N)$ Micah grafo con vértices de los números de $1,..,n$ y los bordes $\{i,j\}$ si $i+j$ es una potencia de $N$. Su condición se satisface si y sólo si $G$ contiene un camino Hamiltoniano. (Y los análogos de la pregunta para un ciclo si y sólo si $G$ contiene un ciclo Hamiltoniano).

Deje $m(N)$ ser el más pequeño $n$ tal que $G(n,N)$ contiene un camino Hamiltoniano y $m_c(N)$ el más pequeño $n$ tal que $G(n,N)$ contiene un ciclo Hamiltoniano.

Desde algunos cálculos con la salvia se puede ver que $$\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}$$ Ejemplo para $15$, $32$ y $305$ ya están en su pregunta, he calculado ejemplos de los 473 y el 9641.

Para las entradas con signos de preguntas: estas son sólo algunas conjeturas. Para $m(4)$, uno puede ver rápidamente, con la ayuda de sage que $G(9253,4)$ no tiene un camino Hamiltoniano, y ninguna de las $G(n,4)$ para $n=9252, 9251, 9250,\dots$ o $9210$. Pero hasta ahora no pude encontrar un camino Hamiltoniano en $G(9253,4)$, tal vez alguien puede darle una oportunidad. Del mismo modo, $G(490462,5)$ no contiene un ciclo Hamiltoniano.

Me parece que el argumento de su "Información Adicional" bastante convincente y sería de esperar que la mayoría de los gráficos con más de $m(N)$ (o $m_c(N)$) cumplir con su condición; posiblemente con un par de excepciones, justo encima de $m(N)$ (o $m_c(N)$). Tal vez probabilística argumento podría convertir en una prueba.

También se podría preguntar acerca de la asymptotics de $m(N)$ e $m_c(N)$ o encontrar límites inferiores para ellos.

---

Actualización: a petición de martin, aquí está el sabio código. Para N=3, n=473 toma .2 segundos para encontrar el hamiltoniano del ciclo, para N=4, n=9641 toma 290 segundos en mi equipo.

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

Si no arreglamos el exponente, la suma de cada dos números adyacentes puede ser cualquier poder perfecto, entonces obtendremos una clase más amplia de soluciones. He modificado el Sabio código proporcionado por Moritz Firsching a controlar este caso, un applet se puede encontrar aquí:

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

por $n$ busca un acuerdo apropiado. E. g. si $n=17,$, entonces se tiene la siguiente disposición cíclica $$1,3,5,4,12,13,14,11,16,9,7,2,6,10,15,17,8.$$