38
$\begingroup$

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

$\endgroup$
7
  • 4
    $\begingroup$ There is some information on the square arrangements at oeis.org/A090460 $\endgroup$ Mar 11, 2015 at 12:17
  • $\begingroup$ it seems to me you are asking for too much in Q1 with the "for each $N$" part. Clearly the sum of two adjacent numbers is at most $2n-1$, while $m^N$ is at least $2^N$, so for large $N$ the number $2^N$ (and any $m^N$) would clearly overshoot $2n-1$. $\endgroup$
    – Mirko
    Mar 11, 2015 at 18:49
  • 3
    $\begingroup$ @mathlove There is some more info on circular loops of square arrangements at oeis.org/A071984 $\endgroup$
    – martin
    Mar 12, 2015 at 11:47
  • 1
    $\begingroup$ The cube case with $n=305$ and the cyclical cube case with $n=473$ appeared some years ago at primepuzzles.net/puzzles/puzz_311.htm $\endgroup$ Mar 13, 2015 at 3:52
  • 1
    $\begingroup$ It appears to be proved that for all $N\ge25$ one can arrange all the numbers from 1 to $N$ in a row such that the sum of every two adjacent numbers is a perfect square. See #22 by R. Gerbicz at mersenneforum.org/showthread.php?p=477787 $\endgroup$ May 26, 2019 at 0:56

3 Answers 3

16
$\begingroup$

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

enter image description here


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)

$\endgroup$
2
  • 1
    $\begingroup$ A warning: in your second picture, the nodes 4 and 12 are connected, but this isn't seen because of how the graph has been drawn. $\endgroup$ Sep 5, 2016 at 3:36
  • 1
    $\begingroup$ @KevinO'Bryant ah, true - should really have played with layout a bit more to make it clearer - might update if I get time at some point. $\endgroup$
    – martin
    Sep 5, 2016 at 15:57
12
$\begingroup$

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))]
$\endgroup$
2
  • $\begingroup$ Sage is new to me - is there any chance you could post the code to GitHub or similar if you still have it? $\endgroup$
    – martin
    Aug 2, 2015 at 9:08
  • $\begingroup$ @martin I added the code in the answer.. $\endgroup$ Aug 3, 2015 at 8:05
6
$\begingroup$

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

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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