¿Nombre o entrada OEIS para un cierto conjunto de números?

Question

Estoy considerando el conjunto de enteros positivos $n$ tal manera que los enteros de $1$ $n$ se pueden arreglar en una línea tal que añadir cada dos números consecutivos de un cuadrado perfecto. El más pequeño no trivial que es el tal $n$ $15$, con el pedido $8, 1, 15, 10, 6, 3, 13, 12, 4, 5, 11, 14, 2, 7, 9$.

$35$ también trabaja, resulta. ¿Hay un nombre para estos números? He intentado buscar el OEIS, pero tener sólo dos términos es problemático...

Answer 1

El problema de encontrar un reordenamiento de $1,\ldots, n$ puede ser reflejado en el gráfico términos de teoría.

Para cualquier entero $n > 0$, considere un grafo con a $n$ vértices. La etiqueta de los vértices de$1$$n$. Para cualquier par de vértices $i$$j$, nos unimos a ellos por un borde cuando y sólo cuando $i + j$ es un prefecto de la plaza. El problema de encontrar un deseada reordenamiento es equivalente a encontrar un camino Hamiltoniano en un grafo.

Por ejemplo, el código siguiente en maixma

load(graphs);
H[i,j] := if(integerp(sqrt(i+j))) then 1 else 0;
G(n)   := from_adjacency_matrix(genmatrix(H,n,n));
hamilton_path(G(15))+1;

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

which is essentially the rearrangement you have in reverse order.

Using codes above, I have checked for $n \le el 100$, the set of $$ n, que permiten tales un arreglo se $15,16,17,23^{\color{blue}{[1]}}$ y todos los $n \ge 25$ (a excepción de $n = 86$ cuando el código anterior se bloquea).

Como ha señalado Michael, una búsqueda en este número de devolución OEIS A090461 y $86$ también es permitido.

Notas

• $\color{blue}{[1]}$ Gracias por Michael señalando mi error en $23$.