[math-fun] Square (& other) chains and necklaces.
I recently mentioned a problem of finding chains and necklaces in which adjacent links add to a square (or other things). Such problems can be restated as: Draw a graph having the numbers from 1 to n as vertices and an edge between any pair of vertices whose labels add to a square (or whatever). Is there a Hamilton path (circuit) in the graph? For example (requested by at least one listener), n = 32. 28 8 1 15 10 21 26 4 23 32 2 17 14 19 22 30 27 6 9 3 16 13 20 12 29 24 7 25 11 5 31 18 This can be upped to 33 by inserting ... 9 16 33 31 18 7 29 20 5 11 ... so we now have chains for n = 15 16 17 31 32 33 34 35 ... (and no smaller others??). This (and 32 33 ... for necklaces) seem to be in too much of an inchoate state for acceptance as sequences for OEIS ?? Finding Hamilton paths is NP-hard in general, but those of us who don't know about such things can often find them in particular cases. Any offers for contributions to knowledge, or references to existing knowledge that Ed Pegg hasn't told me about? R.
On Fri, 22 Nov 2002, Richard Guy wrote:
I recently mentioned a problem of finding chains and necklaces in which adjacent links add to a square (or other things). Such problems can be restated as: Draw a graph having the numbers from 1 to n as vertices and an edge between any pair of vertices whose labels add to a square (or whatever). Is there a Hamilton path (circuit) in the graph? For example (requested by at least one listener), n = 32.
28 8 1 15 10 21 26 4 23 32 2 17 14 19 22 30 27 6 9 3 16 13 20 12 29 24 7 25 11 5 31 18
This can be upped to 33 by inserting
... 9 16 33 31 18 7 29 20 5 11 ...
so we now have chains for n = 15 16 17 31 32 33 34 35 ... (and no smaller others??).
Dealing with the case where i adjacent to j iff i + j is a square: A short Maple program shows that for n < 14 the graphs are not connected and so cannot contain Hamiltonian circuits or paths. The graph for n = 14 has three vertices for degree one so clearly cannot contain either a spanning path or circuit. n=18 is not possible since it has 3 degree 1 vertices n = 20 thru 30 each have only one vertex of degree 1 so they are also ruled out. The graph for n = 19 has degree sequence [1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3] and according to Maple is connected. So it could have a Hamiltonial path. But I have a little ad hoc argument that shows it cannot. So I guess you have the beginning of a new sequence for the OLEIS. Edwin ------------------------------------------------------------ W. Edwin Clark, Math Dept, University of South Florida, http://www.math.usf.edu/~eclark/ ------------------------------------------------------------
Continued fractions of functions of e often contain arithmetically increasing terms. Given a continued fraction with some finite number of interspersed arithmetically increasing sequences and some finite set of constant terms (like the 1,1 terms in the cf for e itself), is there an algorithm to determine what function of e it is? -- Mike Stay staym@datawest.net
Thanks for your comments. The argument about 20 to 30 having only one vertex of valence one doesn't quite work, since you can drop an edge to a 2-valent vertex to make the other end of the chain. Ed Pegg has chains for 23, 25, 26, 27, 28, 29, 30, 31 and cycles (which can be broken anywhere to make a chain) for 32, 33, 34, 35, 36, 37. Probably cycles exist for all n from here on, but I haven't proved it. R. On Fri, 22 Nov 2002, Edwin Clark wrote:
On Fri, 22 Nov 2002, Richard Guy wrote:
I recently mentioned a problem of finding chains and necklaces in which adjacent links add to a square (or other things). Such problems can be restated as: Draw a graph having the numbers from 1 to n as vertices and an edge between any pair of vertices whose labels add to a square (or whatever). Is there a Hamilton path (circuit) in the graph? For example (requested by at least one listener), n = 32.
28 8 1 15 10 21 26 4 23 32 2 17 14 19 22 30 27 6 9 3 16 13 20 12 29 24 7 25 11 5 31 18
This can be upped to 33 by inserting
... 9 16 33 31 18 7 29 20 5 11 ...
so we now have chains for n = 15 16 17 31 32 33 34 35 ... (and no smaller others??).
Dealing with the case where i adjacent to j iff i + j is a square:
A short Maple program shows that for n < 14 the graphs are not connected and so cannot contain Hamiltonian circuits or paths. The graph for n = 14 has three vertices for degree one so clearly cannot contain either a spanning path or circuit.
n=18 is not possible since it has 3 degree 1 vertices
n = 20 thru 30 each have only one vertex of degree 1 so they are also ruled out.
The graph for n = 19 has degree sequence
[1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3]
and according to Maple is connected. So it could have a Hamiltonial path. But I have a little ad hoc argument that shows it cannot.
So I guess you have the beginning of a new sequence for the OLEIS.
Edwin
------------------------------------------------------------ W. Edwin Clark, Math Dept, University of South Florida, http://www.math.usf.edu/~eclark/ ------------------------------------------------------------
I realize my argument fails for n from 20 to 30. I agree with the conjecture that all graphs from n = 36 on are probably Hamiltonian. I tried a few using Maple to create the graphs and another program called Groups and Graphs to find Hamiltonian cycles. This way I have found Hamiltonian cycles for n = 36, 64, 100, and 200--the only ones I tried. I would send them but the format is difficult to handle. The program gives the cycles as nice pictures arranged in a circle, but I cannot figure out how to printout the vertices in that order. I have a colleague who is much better at writing fast programs for such things. I will try to get him to whip it out. I suspect that he can easily decide all values of n up to several hundred and print out the cycles very quickly. There are likely many Hamiltonian cycles for each such graph. Of course, the more the merrier. I have also been able to use a little graph theory to prove that no Hamiltonian path exit for n = 18,19,20,21,and 22. The idea is to find x vertices so that when removed the graph remaining has more than x+1 components. I was working on the case 23. Now I see that was futile. ---Edwin On Sat,23 Nov 2002, Richard Guy wrote:
Thanks for your comments. The argument about 20 to 30 having only one vertex of valence one doesn't quite work, since you can drop an edge to a 2-valent vertex to make the other end of the chain. Ed Pegg has chains for 23, 25, 26, 27, 28, 29, 30, 31 and cycles (which can be broken anywhere to make a chain) for 32, 33, 34, 35, 36, 37. Probably cycles exist for all n from here on, but I haven't proved it. R.
On Fri, 22 Nov 2002, Edwin Clark wrote:
On Fri, 22 Nov 2002, Richard Guy wrote:
I recently mentioned a problem of finding chains and necklaces in which adjacent links add to a square (or other things). Such problems can be restated as: Draw a graph having the numbers from 1 to n as vertices and an edge between any pair of vertices whose labels add to a square (or whatever). Is there a Hamilton path (circuit) in the graph? For example (requested by at least one listener), n = 32.
28 8 1 15 10 21 26 4 23 32 2 17 14 19 22 30 27 6 9 3 16 13 20 12 29 24 7 25 11 5 31 18
This can be upped to 33 by inserting
... 9 16 33 31 18 7 29 20 5 11 ...
so we now have chains for n = 15 16 17 31 32 33 34 35 ... (and no smaller others??).
Dealing with the case where i adjacent to j iff i + j is a square:
A short Maple program shows that for n < 14 the graphs are not connected and so cannot contain Hamiltonian circuits or paths. The graph for n = 14 has three vertices for degree one so clearly cannot contain either a spanning path or circuit.
n=18 is not possible since it has 3 degree 1 vertices
n = 20 thru 30 each have only one vertex of degree 1 so they are also ruled out.
The graph for n = 19 has degree sequence
[1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3]
and according to Maple is connected. So it could have a Hamiltonial path. But I have a little ad hoc argument that shows it cannot.
So I guess you have the beginning of a new sequence for the OLEIS.
Edwin
------------------------------------------------------------ W. Edwin Clark, Math Dept, University of South Florida, http://www.math.usf.edu/~eclark/ ------------------------------------------------------------
------------------------------------------------------------ W. Edwin Clark, Math Dept, University of South Florida, http://www.math.usf.edu/~eclark/ ------------------------------------------------------------
Concerning the problem of "square" chains and necklaces: Now I am confident that for n < 32 the only values of n for which a chain exists are 15, 16, 17, 23 and 25 thru 31. It seems that for n > 31 cycles always exist. I have only checked this up to 50 or so plus 64, 100 and 200. The latter two were done using Bill Kocay's program Groups and Graphs. (The Hamiltonian cycle for the case n = 200 is found almost immediately!). My colleague Stephen Suen thought of a related question. Is there a Hamiltonian path for the infinite graph with vertices = all positive integers with adjacence defined by "sum to a square"? I decided to write a greedy program to see how far this would take me. Then I looked at Sloane's EIS and found the sequence ID Number: A034175 Sequence: 0,1,3,6,10,15,21,4,5,11,14,2,7,9,16,20,29,35,46,18,31,33,48, 52,12,13,23,26,38,43,57,24,25,39,42,22,27,37,44,56,8,17,19, 30,34,47,53,28,36,45,55,66,78,91,105,64,80,41,40,60,61,83, 86,58,63,81,88,108,117,79,65 Name: a(n) is minimal such that a(n)+a(n-1) is a square and a(n) is not in {a(0), ..., a(n-1)}. Comments: Conjectured to be a permutation of the nonnegative integers [There is also a similar sequence in EIS for "sums to a prime".] Here's a more general question: Let G be a graph whose vertices are N, the natural numbers. Suppose for every n the subgraph G_n of G induced on {1,2,...,n} has a Hamiltonian path starting with 1. Does G necessarily have a Hamiltonian path? (The converse is false as the graph 1-3-2-5-4-7-6-... shows.) Edwin Clark On Sat, 23 Nov 2002, Richard Guy wrote:
Thanks for your comments. The argument about 20 to 30 having only one vertex of valence one doesn't quite work, since you can drop an edge to a 2-valent vertex to make the other end of the chain. Ed Pegg has chains for 23, 25, 26, 27, 28, 29, 30, 31 and cycles (which can be broken anywhere to make a chain) for 32, 33, 34, 35, 36, 37. Probably cycles exist for all n from here on, but I haven't proved it. R.
On Fri, 22 Nov 2002, Edwin Clark wrote:
On Fri, 22 Nov 2002, Richard Guy wrote:
I recently mentioned a problem of finding chains and necklaces in which adjacent links add to a square (or other things). Such problems can be restated as: Draw a graph having the numbers from 1 to n as vertices and an edge between any pair of vertices whose labels add to a square (or whatever). Is there a Hamilton path (circuit) in the graph? For example (requested by at least one listener), n = 32.
28 8 1 15 10 21 26 4 23 32 2 17 14 19 22 30 27 6 9 3 16 13 20 12 29 24 7 25 11 5 31 18
This can be upped to 33 by inserting
... 9 16 33 31 18 7 29 20 5 11 ...
so we now have chains for n = 15 16 17 31 32 33 34 35 ... (and no smaller others??).
Dealing with the case where i adjacent to j iff i + j is a square:
A short Maple program shows that for n < 14 the graphs are not connected and so cannot contain Hamiltonian circuits or paths. The graph for n = 14 has three vertices for degree one so clearly cannot contain either a spanning path or circuit.
n=18 is not possible since it has 3 degree 1 vertices
n = 20 thru 30 each have only one vertex of degree 1 so they are also ruled out.
The graph for n = 19 has degree sequence
[1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3]
and according to Maple is connected. So it could have a Hamiltonial path. But I have a little ad hoc argument that shows it cannot.
So I guess you have the beginning of a new sequence for the OLEIS.
Edwin
------------------------------------------------------------ W. Edwin Clark, Math Dept, University of South Florida, http://www.math.usf.edu/~eclark/ ------------------------------------------------------------
------------------------------------------------------------ W. Edwin Clark, Math Dept, University of South Florida, http://www.math.usf.edu/~eclark/ ------------------------------------------------------------
I was able to get an n = 300 "square" necklace using Kocay's program. For the skeptical here it is: 1, 288, 112, 212, 188, 136, 153, 103, 186, 138, 151, 74, 122, 134, 190, 99, 157, 167, 194, 206, 118, 171, 54, 142, 83, 113, 56, 140, 184, 105, 219, 181, 108, 148, 77, 179, 110, 146, 50, 119, 170, 191, 133, 156, 100, 125, 164, 197, 59, 137, 187, 102, 154, 135, 121, 75, 150, 106, 183, 73, 152, 104, 185, 139, 222, 178, 78, 147, 214, 227, 173, 116, 208, 81, 144, 180, 109, 215, 226, 174, 115, 209, 80, 176, 224, 217, 72, 289, 35, 221, 220, 69, 292, 32, 257, 67, 294, 30, 259, 65, 296, 28, 261, 63, 298, 26, 263, 61, 300, 24, 265, 264, 25, 299, 62, 262, 27, 297, 64, 260, 29, 295, 66, 258, 31, 293, 68, 256, 33, 291, 70, 254, 2, 287, 37, 252, 4, 285, 39, 250, 6, 283, 41, 248, 8, 281, 43, 246, 10, 279, 45, 244, 12, 277, 47, 242, 14, 275, 49, 240, 16, 273, 88, 236, 20, 269, 92, 232, 168, 57, 199, 162, 127, 98, 158, 131, 193, 96, 228, 172, 53, 203, 86, 238, 18, 271, 90, 234, 22, 267, 94, 230, 211, 189, 36, 160, 129, 195, 166, 123, 201, 55, 141, 84, 205, 51, 145, 216, 225, 175, 114, 210, 231, 93, 268, 21, 235, 89, 200, 124, 132, 192, 97, 128, 161, 163, 126, 130, 159, 165, 196, 60, 229, 95, 266, 23, 233, 91, 270, 19, 237, 52, 272, 17, 239, 85, 204, 120, 169, 155, 101, 223, 177, 79, 117, 207, 82, 143, 218, 182, 107, 149, 76, 213, 111, 58, 198, 202, 87, 274, 15, 241, 48, 276, 13, 243, 46, 278, 11, 245, 44, 280, 9, 247, 42, 282, 7, 249, 40, 284, 5, 251, 38, 286, 3, 253, 71, 290, 34, 255 ------------------------------------------------------------ W. Edwin Clark, Math Dept, University of South Florida, http://www.math.usf.edu/~eclark/ ------------------------------------------------------------
Thanks again. In all these cases the valences increase steadily. Not enough to employ Dirac's Theorem, but to make `for all sufficiently large n' plausible for functions which are not increasing too rapidly. The Fibonacci numbers (and presusumably other recurring sequences) seem to be the interesting cut-off point. Elwyn Berlekamp and I have shown that there are `Fibonacci chains' (no necklaces) just for n = 9, 11 and F_k - 1 and F_k for k > 3. R.
Sudipta Das sent me an interesting question. Define the n-complement of a number j as the number k, such that corresponding digits of j and k always add to n. For example, the 9-complement of 73149812 is 26850187. Sudipta noticed: ( 225 , 441 ) are 6-complements, and both are square numbers ( 39866596 , 82355625 ) are 11-complements, and both are square numbers I wondered several things, and I don't have answers. 1. Does this concept of n-complements has a better known name? 2. What is the next set of n-complementary square numbers? 3. What other interesting things can be done with n-complements? --Ed Pegg Jr, www.mathpuzzle.com
Ed, et al:
Define the n-complement of a number j as the number k, such that corresponding digits of j and k always add to n.
In other words, j+k = n*(10^a-1)/9, for some A, and all digits of J and K are <= N, < 10, >= 0, and > N-10.
( 225 , 441 ) are 6-complements, and both are square numbers ( 39866596 , 82355625 ) are 11-complements, and both are square numbers 2. What is the next set of n-complementary square numbers?
This is a lot like representing X=n*(10^a-1)/9 as the sum of two squares. (In your case, you also want all digits to be in-bounds.) I think the two-square-sum problem has been done to death. If you can factor X, it's easy to determine whether it has such representations; does anyone know how to generate them? -- Don Reble djr@nk.ca
I think the two-square-sum problem has been done to death. If you can factor X, it's easy to determine whether it has such representations;
i've been looking at the three square case. i assume the squares have to be equal length (there are many more triples if you assume leading zeroes). aside from the obvious sets of squares of length 1, i've found the following. i especially like the last one. 400, 256, 121 625, 400, 196 676, 400, 256 784, 625, 256 841, 169, 100 5625, 4096, 2500 6400, 5776, 1156 6400, 5776, 4489 7056, 3721, 1444 7396, 3600, 1225 8281, 2916, 1024 8464, 2601, 1156 8464, 3844, 1024 8464, 4489, 2601 42025, 14641, 10000 43681, 36100, 31329 44100, 33124, 11664 44100, 34969, 32041 51076, 48400, 33856 55225, 34596, 32400 55225, 35721, 20164 55696, 40000, 37636 59049, 51984, 44521 60025, 39204, 11881 62001, 34225, 14884 65025, 25921, 20164 65536, 55696, 12100 68121, 42436, 11664 70225, 26244, 14641 75625, 55696, 35344 77284, 22801, 11025 77841, 66049, 11664 81225, 22500, 18496 82369, 16641, 12100 84100, 15129, 11881 84100, 33856, 15376 85264, 24964, 23104 91204, 29584, 12544 95481, 44944, 15129 97344, 44521, 13689 99225, 12996, 10000 301401, 242064, 123201 erich
to start a completely different thread... what is the smallest constant c so that the graph of the function f(x) = x^3 - c x contains the vertices of an equilateral triangle? erich
--- Don Reble <djr@nk.ca> wrote:
I think the two-square-sum problem has been done to death. If you can factor X, it's easy to determine whether it has such representations; does anyone know how to generate them?
Maple has a function "sum2sqr" which lists all the representations. You could examine the code. Gene __________________________________________________ Do you Yahoo!? Yahoo! Mail Plus - Powerful. Affordable. Sign up now. http://mailplus.yahoo.com
I've written some mathematica code to do bifurcating continued fractions. The code is pretty straight-forward, but I'm not an experienced mathematica programmer, so I'm sure there are some optimisations that could be done. Something's going wrong with it now; I think it has to do with precision or some other nasty implementation issue. I get the first convergents correct, but later ones are dodgy. Does anyone feel qualified and generous enough to take a look? -- Mike Stay staym@datawest.net
It turns out (silly me) that I assumed things would be displayed in the same horizontal position on the screen if the data matched up to that point. Apparently mathematica determines the formatting for the entire block of data at once, and not line by line. So what I thought were changing values were really just values moving around. The code works; sorry for the traffic. One math-fun reader has expressed interest in seeing the code; if anyone else is interested, I'd be happy to send it to you. -- Mike Stay staym@datawest.net
I wrote:
Has anyone proven that one can't do better with any method of approximation? I guess one could do it with a counting argument; heuristically I've only got lg n bits to spend. If I spend them all on one number, I can make it as small as I want (the penultimate convergent from the continued fraction gives the modular inverse of m), but if I split it among two of them, I can only get them half as small. -- Mike Stay staym@datawest.net
participants (8)
-
Don Reble -
ed pegg -
Edwin Clark -
Erich Friedman -
Eugene Salamin -
Mike Stay -
R. William Gosper -
Richard Guy