mersenneforum.org The Square-Sum problem
 Register FAQ Search Today's Posts Mark Forums Read

 2018-01-11, 19:10 #1 henryzz Just call me Henry     "David" Sep 2007 Liverpool (GMT/BST) 2×5×599 Posts The Square-Sum problem 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?
2018-01-11, 19:42   #2
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

838410 Posts

Quote:
 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.

Last fiddled with by science_man_88 on 2018-01-11 at 20:09 Reason: Fixing math, counted 1 as a summable square.

2018-01-11, 21:26   #3
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

Quote:
 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.

Last fiddled with by science_man_88 on 2018-01-11 at 21:27

2018-01-12, 14:31   #4
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 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)

Last fiddled with by science_man_88 on 2018-01-12 at 15:30

 2018-01-12, 19:21 #5 henryzz Just call me Henry     "David" Sep 2007 Liverpool (GMT/BST) 2·5·599 Posts 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. Attached Thumbnails
2018-01-12, 19:37   #6
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

Quote:
 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.

2018-01-12, 20:33   #7
henryzz
Just call me Henry

"David"
Sep 2007
Liverpool (GMT/BST)

2×5×599 Posts

Quote:
 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?

2018-01-12, 20:44   #8
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

838410 Posts

Quote:
 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.

2018-01-12, 23:58   #9
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

112·13 Posts

Quote:
 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.

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

2018-01-13, 00:03   #10
CRGreathouse

Aug 2006

135338 Posts

Quote:
 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.

 2018-01-13, 01:42 #11 science_man_88     "Forget I exist" Jul 2009 Dumbassville 26·131 Posts 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. Last fiddled with by science_man_88 on 2018-01-13 at 02:10

 Similar Threads Thread Thread Starter Forum Replies Last Post firejuggler Puzzles 1 2018-01-24 23:27 Damian Math 3 2010-01-01 01:56 davar55 Puzzles 9 2008-05-21 12:54 Fusion_power Puzzles 14 2008-04-25 11:37 Zeta-Flux Math 16 2005-12-14 06:55

All times are UTC. The time now is 16:46.

Wed Jul 6 16:46:43 UTC 2022 up 83 days, 14:48, 0 users, load averages: 1.85, 1.72, 1.68