Number Theory – Longest Chain of n-Digit Square Numbers

Question

Consider all the square numbers with exactly n digits, I want to arrange them such that the last digit of a square is equal to first digit of the next square and find the longest arrangement, how many elements contain and possibly how many of those longest arrangement are possible. Of course some squares will be sorted out.

For n=2 the squares are {16, 25, 36, 49, 64, 81}. So the longest arrangement is {81, 16, 64, 49} with s=4 elements

For n=3 there are s=12 elements in the longest arrangement, and one of the them (there are 26 in total) is:

{841, 121, 144, 484, 441, 169, 961, 196, 676, 625, 529, 900}

Of course there are some criteria to construct the arrangement without just trying: at most 1 square can start with {2,3,7,8} and if so, must be in the 1st position; at most 1 square with 0 as last digit.

I asked for help in this thread, hoping to use Mathematica to brute force the solutions, and I received some great and highly detailed answers, but when I try with n=4 the algorithm slows down.
I guess, but I'm not sure, that the answer for n=4 is s=30 and one of the arrangement is:

{2025, 5776, 6561, 1225, 5625, 5041, 1369, 9801, 1024, 4624, 4489, 9216, 6084, 4761, 1521, 1764, 4356, 6889, 9604, 4225, 5329, 9409, 9025, 5184, 4096, 6241, 1681, 1156, 6724, 4900}

For n = 5 the longest arrangement I found (thanks to @Peter) is:

{39204, 47089 ,97344, 46225, 53824, 41616, 66564, 42025, 51984, 43681, 12544, 48841,13225, 52441, 18225, 58081, 10609, 96721, 10404, 45369, 93025, 56644, 47524, 41209, 91809, 93636, 62001, 10816, 65536, 67081, 16641, 10201, 12321,14641, 19321, 13689, 98596, 66049, 95481, 17161, 15129, 94864, 44944, 43264, 47961, 18496, 63504, 49729, 94249, 90601, 13456, 64009, 99225, 53361, 15625, 55696, 69696, 68121, 14161, 11881, 19881, 18769, 97969, 99856, 61009, 92416, 60516, 60025, 57121, 11025, 55225, 50625, 58564, 42436, 68644, 40401, 14884, 45796, 63001, 11664, 46656, 65025, 51076, 69169, 91204, 44521, 17956, 64516, 61504, 40804, 49284, 42849, 96100} with s=93

So, how can I calculate how many elements are in the longest chain of squares with n digits?

Thanks

Answer 1

Consider the directed multigraph with vertices $\{1,4,5,6,9\}$ in which the number of edges between vertices $a$ and $b$ is the number of $n$-digit perfect squares beginning with digit $a$ and ending with digit $b$. For example, when $n=5$ the number of edges between each pair of vertices is given by the following table:

\begin{array}{c|ccccc} &1 & 4 & 5 &6 & 9 \\ \hline 1 & 9 & 8 & 4 & 8 & 8\\ 4 & 5 & 5 & 2 & 4 & 5\\ 5 & 4 & 4 & 2 & 5 & 4\\ 6 & 4 & 4 & 2 & 4 & 4\\ 9 & 3 & 3 & 2 & 4 & 3\\ \end{array}

For example, there are two squares ($245^2 = 60025$ and $255^2 = 65025$) beginning with $6$ and ending with $5$, so the entry in $6$'s row and $5$'s column is $2$.

Our goal is more or less to find the longest walk in this graph that does not repeat any edges (meaning that it uses distinct perfect squares). There are other perfect squares that can get involved, but for large $n$ we may assume that any such longest walk can be prefixed by a perfect square beginning with $2, 3, 7, 8$ and postfixed by a perfect square ending with $0$, so it does not matter where we start or end. This is still in general a hard problem, but in some sense our multigraph is always small: no matter how big $n$ is, it only has $5$ vertices.

Another way to phrase what we want is: we want to find a subgraph of this graph which has an Eulerian trail. If we wanted a (closed) Eulerian tour, our subgraph would have to have equal indegree and outdegree at every vertex. For a trail, which begins and ends at different vertices, this condition may be violated by 1 at the start and end.

Let's understand the Eulerian tour problem first, because it's easier. Here, there is a lower bound that, experimentally, looks very achievable. For each vertex, count the indegree $d^-$ and the outdegree $d^+$. If $d^- < d^+$, then at least $d^+ - d^-$ edges leaving this vertex must be deleted in passing to our Eulerian subgraph. If $d^- > d^+$, then at least $d^- - d^+$ edges entering this vertex must be deleted. For example, when $n=5$, this tells us that we must delete:

• at least $12$ edges leaving vertex $1$ and at least $7$ edges leaving vertex $5$.
• at least $3$ edges entering vertex $4$, $7$ edges entering vertex $6$, and $9$ edges entering vertex $9$.

There is no promise that this will be possible; our restriction is that we cannot delete more edges between a pair of vertices than exist in the graph. However, if possible, it is certainly optimal.

When $n=5$, I manually found that we can delete $2$ edges $(1,4)$, $2$ edges $(1,6)$, $8$ edges $(1,9)$, $1$ edge $(5,4)$, $5$ edges $(5,6)$, and $1$ edge $(5,9)$. Deleting these $19$ edges leaves us a $91$-edge graph with an Eulerian tour.

We only wanted an Eulerian trail. This allows us to put back up to one (arbitrary) edge; let's put back an edge $(5,4)$, getting a $92$-edge graph with an Eulerian trail starting at $5$ and ending at $4$. This gets us a sequence of $92$ perfect squares. We can prepend $21025$ and append $40000$ to get the following optimal $94$-square sequence:

{21025,52441,11025,53361,13225,57121,15625,58081,12544,40401,13924,43681,14884,44521,16384,47961,17424,48841,19044,42025,50625,55225,51984,46225,53824,40804,43264,44944,47524,49284,41616,62001,12996,63001,13456,67081,15376,68121,15876,60025,56644,42436,65025,54289,90601,17956,61504,45796,63504,46656,66564,41209,95481,18496,68644,42849,93025,56169,99225,59049,91204,45369,94864,47089,97344,49729,92416,60516,64516,65536,69696,61009,93636,64009,98596,66049,99856,69169,91809,94249,97969,96721,10201,11881,12321,14161,14641,16641,17161,19321,19881,18225,58564,40000}

The same approach should allow us to efficiently compute chains of $n$-digit squares for larger $n$. I should add that the number of $n$-digit squares beginning in $a$ and ending in $b$ is a quick calculation: their square roots are in the range $[\sqrt{a \cdot 10^{n-1}}, \sqrt{(a+1) \cdot 10^{n-1}})$ and end in a digit determined by $b$ (e.g. they end in $3$ or $7$ when $b=9$). So we can compute the bound described above without too much trouble.

Is the bound achievable? Not for $n=2$, which is not too much of a problem. I picked the following strategy to try to do it in general: delete all $1 \to 9$ and $5 \to 6$ edges, then use the degree constraints to infer the number of $1 \to 4, 1\to 6, 5 \to 4, 5 \to 9$ edges to delete. In practice, this works for $n=3, \dots, 11$, which was all I checked. It should be possible to prove that it works for all sufficiently large $n$ via an asymptotic estimate of the number of $a \to b$ edges.

Mathematica code

Here is some somewhat-sloppy code implementing the above, which works for $n\ge 3$ (special-casing the choice of prefix and suffix in the $n=3$ case).

The lengths of the sequences we get from $3$ onwards are: $$12, 30, 94, 289, 905, 2856, 9021, 28521, 90186, \dots$$ These scale linearly with the number of perfect squares available, so we approximately multiply by $10$ every two steps, which is why we alternate between numbers beginning with $28$ and numbers beginning with $90$.

n = 10; (* how long should our perfect squares be? *)

x = Range[Ceiling[Sqrt[10^(n - 1)]], Floor[Sqrt[10^n - 1]]]^2;

start[d_] := First@IntegerDigits@d;
end[d_] := Last@IntegerDigits@d;
Clear[edges];
edges[a_, b_] := edges[a, b] = Select[x, start[#] == a && end[#] == b &];
ec[a_, b_] := Length[edges[a, b]]; (* edge count *)

indegree[k_] := Sum[ec[i, k], {i, {1, 4, 5, 6, 9}}];
outdegree[k_] := Sum[ec[k, i], {i, {1, 4, 5, 6, 9}}];

(* indegree-outdegree differences for all vertices *)
dif1 = outdegree[1] - indegree[1]; 
dif5 = outdegree[5] - indegree[5];
dif4 = indegree[4] - outdegree[4];
dif6 = indegree[6] - outdegree[6];
dif9 = indegree[9] - outdegree[9];

(* how much we subtract to get an Eulerian subgraph *)
sub19 = ec[1, 9];
sub59 = dif9 - sub19;
sub56 = ec[5, 6];
sub16 = dif6 - sub56;
sub14 = dif1 - sub16 - sub19;
sub54 = dif5 - sub56 - sub59;

(* subgraph which should have an Eulerian tour *)
graph = AdjacencyGraph[
   {{ec[1, 1], ec[1, 4] - sub14, ec[1, 5], ec[1, 6] - sub16, 0},
    {ec[4, 1], ec[4, 4], ec[4, 5], ec[4, 6], ec[4, 9]},
    {ec[5, 1], ec[5, 4] - sub54, ec[5, 5], 0, ec[5, 9] - sub59},
    {ec[6, 1], ec[6, 4], ec[6, 5], ec[6, 6], ec[6, 9]},
    {ec[9, 1], ec[9, 4], ec[9, 5], ec[9, 6], ec[9, 9]}}];
graph = VertexReplace[graph, {1 -> 1, 2 -> 4, 3 -> 5, 4 -> 6, 5 -> 9}];

(* find a cycle and turn it into a slightly-longer walk *)
cycle = First[FindEulerianCycle[graph]];
loop11 = First[FirstPosition[cycle, 1 \[DirectedEdge] 1]];
cycle = RotateLeft[cycle, loop11 - 1];(* ensures cycle begins and ends at 1 *)
walk = If[n==3, Join[{3->1}, cycle, {1->9, 9->0}],
    (* or if n>3: *) Join[{2->1}, cycle, {1->4, 4->0}]];

(* turn the walk into a sequence of squares *)
output = {};
Do[
  {a, b} = {First[edge], Last[edge]};
  (* for each edge a->b, use the first unused square of the form a____b *)
  square = First[edges[a, b]];
  edges[a, b] = Rest[edges[a, b]];
  output = Append[output, square];
  , {edge, walk}];
  
output (* the final sequence *)

Additionally, even beyond the point where computing the chain of squares is practical, here is code to compute the length the chain should have:

sqCount[a_, b_, n_] := Module[{cc = Select[Range[0, 9], Mod[#^2, 10] == b &],
    lower = Ceiling[Sqrt[a*10^(n - 1)]],
    upper = Floor[Sqrt[(a + 1)*10^(n - 1) - 1]]},
  Sum[Floor[(upper - c)/10] - Floor[(lower - 1 - c)/10], {c, cc}]];
id[b_, n_] := Sum[sqCount[a, b, n], {a, {1, 4, 5, 6, 9}}]
od[a_, n_] := Sum[sqCount[a, b, n], {b, {1, 4, 5, 6, 9}}]

s[n_] := id[1, n] + id[5, n] + od[4, n] + od[6, n] + od[9, n] + 3