10
$\begingroup$

Inspired by this interesting question and in order to solve an old problem, I have the following question:

Can we construct a strictly increasing sequence $(N_i)_{i\in \mathbb{N}}$, such that for every integer $i$, we can arrange all the numbers from 1 to $N_i$, in a row such that the sum of every two adjacent numbers is a perfect square.

The first term of the sequence cannot be less than $14$, so we can take $N_0=15$: $$8,1,15,10,6,3,13,12,4,5,11,14,2,7,9$$ And we can take also $N_1=16$ because we can add $16$ at the end, and $N_2=17$ by adding $17$ in the beginning (@mathlove). And as pointed by @gnasher729 in his answer we can not take $N_3=18$.

This is related to the connectedness of a graph, if we consider the graph $G_N = (V, E)$ with $V=\{1,\cdots,N\}$ and $\{i,j\}\in E$ if and only if $i+j$ is a square, The question is equivalent to prove that $G_N$ have a Hamiltonian path for large integers $N$.

Edit I updated the question, I hope it's very clear and more direct.

$\endgroup$
8
  • $\begingroup$ Out of curiosity, why do you think that there should be infinitely many integers with this property? $\endgroup$ – A.P. Feb 28 '15 at 15:55
  • $\begingroup$ I have an old problem of mines without an answer and when I found this propriety I think that this may help me to answer my question: math.stackexchange.com/questions/1162534/… $\endgroup$ – Elaqqad Feb 28 '15 at 15:59
  • $\begingroup$ By the way: did you mean "This is true for $N = 15$" instead of "This is true for $N = 5$"? $\endgroup$ – A.P. Feb 28 '15 at 16:10
  • $\begingroup$ Should be "This is true for $N=15$". $\endgroup$ – barak manos Feb 28 '15 at 16:10
  • 3
    $\begingroup$ @Elaqqad: From this OEIS, it is conjectured that there is a solution for all $n\gt 24$. $\endgroup$ – mathlove Feb 28 '15 at 17:05
3
$\begingroup$

Look at the numbers 16, 17, 18: We have 16 < 16+x < 36, 16 < 17+y < 36, 16 < 18+z < 36. Therefore 16+x = 17+y = 18+z = 25, making x = 9, y = 8, z = 7. Therefore each of these numbers has only one possible neighbour and therefore must be the first or last of the sequence. Which is not possible, since we have three of them.

(Sorry, doesn't quite answer the question. )

$\endgroup$
5
  • $\begingroup$ This is only true for $N=18$; the sequence could become possible again for larger $N$. $\endgroup$ – Steven Stadnicki Feb 28 '15 at 15:59
  • $\begingroup$ Still, this proves that not every number shares the property highlighted in OP's question. $\endgroup$ – A.P. Feb 28 '15 at 16:00
  • $\begingroup$ Yes this proves that this is not true for every integer $N$, but still we can maybe find larger $N$ $\endgroup$ – Elaqqad Feb 28 '15 at 16:04
  • $\begingroup$ @Elaqqad I didn't say that this fully answered your question, just that it answered the quoted part: "Given an integer $N$, can we...?" "No, we can't; here's a counterexample." $\endgroup$ – A.P. Feb 28 '15 at 16:06
  • $\begingroup$ @A.p, I understated, thanks, $\endgroup$ – Elaqqad Feb 28 '15 at 16:10
0
$\begingroup$

Here is some quick and dirty Prolog code to brute-force solutions:

:- use_module(library(clpfd)).

conseq_squares([A,B]) :-
    A + B #= C * C.
conseq_squares([A,B|S]) :-
    A + B #= C * C,
    conseq_squares([B|S]).

sqlist(N, L) :-
    length(L, N),
    L ins 1..N,
    all_distinct(L),
    conseq_squares(L),
    label(L).

To use:

?- sqlist(23, L).
L = [2, 23, 13, 12, 4, 21, 15, 10, 6, 19, 17, 8, 1, 3, 22, 14, 11, 5, 20, 16, 9, 7, 18] ;
L = [9, 16, 20, 5, 11, 14, 22, 3, 1, 8, 17, 19, 6, 10, 15, 21, 4, 12, 13, 23, 2, 7, 18] ;
L = [18, 7, 2, 23, 13, 12, 4, 21, 15, 10, 6, 19, 17, 8, 1, 3, 22, 14, 11, 5, 20, 16, 9] ;
L = [18, 7, 9, 16, 20, 5, 11, 14, 2, 23, 13, 12, 4, 21, 15, 10, 6, 19, 17, 8, 1, 3, 22] ;
L = [18, 7, 9, 16, 20, 5, 11, 14, 22, 3, 1, 8, 17, 19, 6, 10, 15, 21, 4, 12, 13, 23, 2] ;
L = [22, 3, 1, 8, 17, 19, 6, 10, 15, 21, 4, 12, 13, 23, 2, 14, 11, 5, 20, 16, 9, 7, 18] ;
false.

However, the definitive answer is given by Gerbicz: there exists an admissible arrangement for $N=15,16,17,23$ and all $N\ge25$, with cycles possible at $N\ge32$. Moreover, there is an effective algorithm to find such arrangements.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.