7
$\begingroup$

The positive integers from $1$ to $n$ (where $n>1$) are arranged in a line such that the sum of any two adjacent numbers is a square. What is the minimum value of $n$?

$\endgroup$
  • 2
    $\begingroup$ Is this your own question or you heard it somewhere because n=1 $\endgroup$ – Abhishek May 13 '18 at 8:28
  • 3
    $\begingroup$ I found one for n=15 but don't know about maximum value of n $8,1,15,10,6,3,13,12,4,5,11,14,2,7,9$ and this one for n=32 on internet $1,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$ $\endgroup$ – Love Invariants May 13 '18 at 8:39
  • 2
    $\begingroup$ @LoveInvariants, it is lovely to get it for two numbers $\endgroup$ – Satish Ramanathan May 13 '18 at 8:54
  • $\begingroup$ @Satish Ramanathan-Thx $\endgroup$ – Love Invariants May 13 '18 at 9:08
4
$\begingroup$

It is conjectured that there is not a maximum value of $n$. See this post. It is a question of mine regarding exactly this, and today, it still remains an open problem such that most people I know refer to it as the "Square-Sum Problem."

An Australian mathematician by the name of Matt Parker perhaps introduced this problem or popularised it in one of his books, Things to Make and Do in the Fourth Dimension $(2014)$. In the book, he conjectured that there always exists such a sequence for $n > 89$, and then $n > 91$.

However, in a Numberphile YouTube video, Matt Parker and his friend talks about how they tested this conjecture for more values, and as far as I know, the conjecture is true thus far and we now want to test for values $n > 300$.

The video has two parts, Part 1 and Part 2.


The minimum value of $n$ is definitely not $2$, as $1+2=3\neq k^2$ for an integer $k$. I believe the minimum value is $15$, but I have to go through the book again. In the meantime, I will attempt to write a program...

Edit: Notice that the $15$-length sequence (as pointed out by @LoveInvariants), $$8,1,15,10,6,3,13,12,4,5,11,14,2,7,9$$ has a particular method of being found. You start with all the number from $1$ to $15$. Then, you start your sequence with $1$. Now, looking at the remainding numbers, find the highest number out of those such that when you add $1$ to it, the result is a square number. The answer, is $15$. Now with your new remainding numbers, find the lowest number out of those such that when you add $15$ to it, the result is a square number. Next, find the highest, then the lowest, and continue. You should have one number left: $8$, and now, all is left is to put the $8$ at the beginning of the sequence before $1$. As far as I have tested in the last two months or so, this is the only sequence that can be generated using this specific method.

This might contribute to why $15$ might be the minimum value for $n$.


Update:

Ok the coding finished and I left the program running overnight. After fixing a couple of errors in the morning, it turns out $15$ is in fact the minimum value of $n$.

$\endgroup$
  • 2
    $\begingroup$ Doesn't the method from the video (succesively setting up a graph and connecting numbers with an edge that sum to a square number) show that $n=15$ is the minimum value because this is the smallest $n$ where you have a Hamiltoninan path? $\endgroup$ – Janik May 13 '18 at 9:33
  • $\begingroup$ @Janik Well if that is the case, then it is. I am no expert in Hamiltonian paths and such kinds of networks (or graphs). My coding hasn't finished yet, but soon, I will be able to check by brute-force. $\endgroup$ – Feeds May 13 '18 at 9:35
  • $\begingroup$ Thank You all for the solutions. Now, I understand the problem very well. Greatly appreciated! :-) $\endgroup$ – Math Tise May 16 '18 at 8:57

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.