mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2018-01-11, 19:10   #1
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

25·5·37 Posts
Default 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?
henryzz is online now   Reply With Quote
Old 2018-01-11, 19:42   #2
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

100000110000002 Posts
Default

Quote:
Originally Posted by henryzz View Post
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.
science_man_88 is offline   Reply With Quote
Old 2018-01-11, 21:26   #3
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

838410 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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
science_man_88 is offline   Reply With Quote
Old 2018-01-12, 14:31   #4
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

838410 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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
science_man_88 is offline   Reply With Quote
Old 2018-01-12, 19:21   #5
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

25·5·37 Posts
Default

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
Click image for larger version

Name:	124.png
Views:	414
Size:	155.0 KB
ID:	17531  
henryzz is online now   Reply With Quote
Old 2018-01-12, 19:37   #6
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

203008 Posts
Default

Quote:
Originally Posted by henryzz View Post
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.
science_man_88 is offline   Reply With Quote
Old 2018-01-12, 20:33   #7
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

592010 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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?
henryzz is online now   Reply With Quote
Old 2018-01-12, 20:44   #8
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by henryzz View Post
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.
science_man_88 is offline   Reply With Quote
Old 2018-01-12, 23:58   #9
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

2×32×83 Posts
Default

Quote:
Originally Posted by henryzz View Post
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.
R. Gerbicz is offline   Reply With Quote
Old 2018-01-13, 00:03   #10
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3·1,993 Posts
Default

Quote:
Originally Posted by henryzz View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2018-01-13, 01:42   #11
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

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
science_man_88 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
The Square-Diff problem firejuggler Puzzles 1 2018-01-24 23:27
Square root of 3 Damian Math 3 2010-01-01 01:56
Square of Primes davar55 Puzzles 9 2008-05-21 12:54
red square Fusion_power Puzzles 14 2008-04-25 11:37
How often is 2^p-1 square-free Zeta-Flux Math 16 2005-12-14 06:55

All times are UTC. The time now is 14:17.


Sat Oct 23 14:17:53 UTC 2021 up 92 days, 8:46, 0 users, load averages: 1.04, 1.26, 1.21

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.