The Square-Sum problem

[henryzz]

https://www.youtube.com/watch?v=G1m7goLCJDY
https://www.youtube.com/watch?v=7_ph5djCCnM

How far can you prove upto 299 seems fairly easy to beat?
Are cubes possible?

[science_man_88]

Originally Posted by henryzz

https://www.youtube.com/watch?v=G1m7goLCJDY
https://www.youtube.com/watch?v=7_ph5djCCnM

How far can you prove upto 299 seems fairly easy to beat?
Are cubes possible?

Well we can at least use combinatorial arguments to figure out how many times at least 1 square gets used etc. 300 is less than half of 625 so there are only 23 squares to sum up to for the numbers under it. That means, by pigeonhole principle either all of them show up equally ( which low ones can't) or at least one shows up 14 times as a sum in any Hamiltonian path for 300.

[science_man_88]

Originally Posted by science_man_88

Well we can at least use combinatorial arguments to figure out how many times at least 1 square gets used etc. 300 is less than half of 625 so there are only 23 squares to sum up to for the numbers under it. That means, by pigeonhole principle either all of them show up equally ( which low ones can't) or at least one shows up 14 times as a sum in any Hamiltonian path for 300.

Doh should say at least 14 times. You can use the same thing for cubes for numbers under 63 there are only 4 cubes they could sum up to. As 62 mod 4 = 2 and 62/4>15 there are at least 2 cubes with at least 16 pairings for cube sums. This still doesn't include low ones not having enough for equal splitting. If we knew if odd or Even for the powers we can relate that to the edges between pairs of opposite parity or same parity etc.

[science_man_88]

Originally Posted by science_man_88

Well we can at least use combinatorial arguments to figure out how many times at least 1 square gets used etc. 300 is less than half of 625 so there are only 23 squares to sum up to for the numbers under it. That means, by pigeonhole principle either all of them show up equally ( which low ones can't) or at least one shows up 14 times as a sum in any Hamiltonian path for 300.

In fact most must show up 14 times as the first 4 summable squares total 24 sums out of the 52 needed of them leaving 28 to be made up of the remaining 19 squares pushing most up (in fact , 9 squares must appear at least 15 times each)

[henryzz]

I have attached a graph of summing upto a cube complete to 124. No solution yet. Unless 108 is an end the solution is at least 235. It is at least all connected.

[science_man_88]

Originally Posted by henryzz

I have attached a graph of summing upto a cube complete to 124. No solution yet. Unless 108 is an end the solution is at least 235. It is at least all connected.

Nice work did my pm clue help ? There is still one other rule in my head, but it's more about number of possible connections versus actual connections.

[henryzz]

Originally Posted by science_man_88

Nice work did my pm clue help ? There is still one other rule in my head, but it's more about number of possible connections versus actual connections.

Are you saying that it can't work for odd powers?

[science_man_88]

Originally Posted by henryzz

Are you saying that it can't work for odd powers?

My clue by pm ,was that the endpoint sum parity is the same parity as the number of sums to the odd based powers. In Matt's first video we find endpoints 18 and 22 these sum to an even number, therefore there must be an even number of sums that sum to the odd squares ( aka the pairings of opposite parity, count 12) . The point about number of possible connections total, is simply that numbers that are half of an even based power have less connections, 18 only had 1 because it couldn't pair with itself and there are only two squares between it and twice it one that can't be made.

[R. Gerbicz]

Originally Posted by henryzz

How far can you prove upto 299 seems fairly easy to beat?

Nice problem, easily outperformed that in one day of work.

There exists a solution for n=15,16,17,23 and for all 25<=n<=1048576. (the last checked is n=2^20).
To prove more we give a Hamiltonian cycle for 32<=n<=1048576.

Download the "proof" at my drive https://drive.google.com/file/d/1S9E...ew?usp=sharing
(8.9 MB compressed zip).

There are only two cases in the algorithm:

S: we give simply a valid sequence with length=n.

F: we use the previous sequence with length=n-1, and the two indexes i,j after the F symbol
that is: S=a(1),...,a(n-1) sequence
flip the terms between i to j and insert n to the i-th place (the indexes starts with one).
We have binomial(n-1,2) choices for i,j, and roughly n^(-3/2) chance that this will be a good sequence,
because we see only 3 new terms in the modified sequence:
a(i-1)+n, n+a(j) and a(i)+a(j+1)
hence the probability that we can't find a solution for n is roughly
(1-n^(-3/2))^(n^2)~exp(-sqrt(n)) so we have not only good probability for a continuation, but
this serie converges, so likely this will give a solution for each (large) n value.

So for example
if seq=[2,4,1,5,6,3] and
we see n=7: F 2,4 then seq'=[2,7,5,1,4,6,3]

To give a Hamiltonian cycle we use only 1<i<j<n-1, because with this the first and the last term of the sequence
won't change, so if it is a Hamiltonian path then also a cycle.

And this happens in practice the largest n index for that we needed 'S' is at n=6109,
The given solution is a Hamiltonian cycle for all 32<=n<=2^20.

Computed these solutions in only 15 minutes.

ps. there are much more such sequence transformations, but using only these we see only a few S,
so needed to find a sequence from scratch in a few n cases.
Double checking the file with brute force is still possible.

[CRGreathouse]

Originally Posted by henryzz

I have attached a graph of summing upto a cube complete to 124. No solution yet. Unless 108 is an end the solution is at least 235. It is at least all connected.

296 is the first number that I can't easily prove impossible, if I'm understanding correctly.

[science_man_88]

I think factoring is actually an answer to this in a sense. The sum of powers is 2*T_n - endpoint sum. Modulo or factoring may have implications on any given case.