# Arranging numbers from 11 to nn such that the sum of every two adjacent numbers is a perfect power

I’ve known that one can arrange all the numbers from $$11$$ to $$15\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,98,1,15,10,6,3,13,12,4,5,11,14,2,7,9$$

Also, a few days ago, a friend of mine taught me that one can arrange all the numbers from $$11$$ to $$305\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,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,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, 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,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, 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, 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, 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, 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, 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, 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,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, 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, 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, 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,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 182, 34, 30, 186, 157, 59, 284, 228, 115, 10, 206, 137, 79, 264, 248, 95$$

Here, I have a question.

Question : Does there exist at least one positive integer $$n≥2n\ge 2$$ satisfying the following condition for each $$N≥2∈NN\ge 2\in\mathbb N$$?

Condition : One can arrange all the numbers from $$11$$ to $$nn$$ in a row such that the sum of every two adjacent numbers is of the form $$mNm^N$$ for some $$m∈Nm\in\mathbb N$$.

Added : I crossposted to MO.

This is not an answer to the question (which I think is well-addressed by Micah’s comment above) but a compendium of miscellaneous observations.

First, Micah’s comment points out that it would be very surprising if there were not a solution for all sufficiently large $$NN$$, and computer search bears this out: there are solutions for $$N=1,15,16,17,23,N=1,15,16,17, 23,$$ and all numbers between $$2525$$ and $$5050$$, at which point I stopped checking. As $$NN$$ increases, the number of solutions increases very rapidly; there is 1 solution for $$N=15N=15$$, ten solutions for $$N=25N=25$$, and $$17,17517,175$$ for $$N=35N=35$$. The $$N=15N=15$$ case is atypically constrained.

Finding the solution when $$N=15N=15$$ is very easy. One can begin by observing that $$99$$ is adjacent only to $$77$$, and $$88$$ only to $$11$$, so the solution, if it exists, must begin with $$99$$ and end with $$88$$. (Or vice-versa, giving the same solutions in reverse, which we henceforth disregard.) But the moves from $$99$$ are forced: $$9−7−2−14−11−5−4−12−13−39-7-2-14-11-5-4-12-13-3$$ is the only sequence possible. From $$33$$ one can go to $$11$$ or to $$66$$, and since going to $$11$$ evidently doesn’t work (since we know $$11$$ is next-to-last) it must end $$3−6−10−15−1−83-6-10-15-1-8$$ and that is the only solution.

Consider the graph whose nodes are $${1,…,15}\{1,\ldots, 15\}$$ in which has two nodes are connected whenever their sum is a square. A solution to the problem is exactly a hamiltonian path in this graph. When we look at this graph, the uniqueness of the solution is completely obvious:

and even a child can see that there is only a single hamiltonian path. (I know because I checked with my six-year-old daughter, who agrees.) The graphs for $$N=16N=16$$ and $$N=17N=17$$ are similarly trivial, and a glance at the graph for $$N=18N=18$$ or $$N=19N=19$$ shows why there is no solution for those values:

In $$N=20,21,22N=20, 21, 22$$ the lack of solutions is still easy to see, although the troublesome dead end at 16 has been connected to 5 via 20. For $$N=24N=24$$ I did not see any obvious reason why there is no solution, but I think a simple argument could probably be made involving the disposition of $$11,22,11, 22,$$ and $$2323$$.

I have not done much investigation of the analogous problem where two numbers are connected if their sum is a perfect cube. For $$N=100N=100$$ the graph is not even connected. For $$N=200N=200$$ it is connected, but has many leaves. Even for $$N=300N=300$$ I suspect there is a fairly easy proof that there is no solution, involving the relatively independent cluster of $${29,35,90,126,217,253,259}\{29, 35, 90, 126, 217, 253, 259\}$$ which has only 4 connections to the rest of the graph.