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

2018-01-22, 03:16   #23
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

24×613 Posts

Quote:
 Originally Posted by R. Gerbicz There is a solution for every n>=25 !
Very nice! Man, you are good!

 2018-01-22, 09:20 #24 henryzz Just call me Henry     "David" Sep 2007 Cambridge (GMT/BST) 3×1,979 Posts Very nice. Maybe someone should let numberphile know. Also I believe papers have been published on less worthwhile subjects.
 2018-01-23, 01:50 #25 MattcAnderson     "Matthew Anderson" Dec 2010 Oregon, USA 953 Posts I posted to the numberphile youtube page that this problem has been solved. Regards, Matt
2018-01-23, 02:07   #26
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

20C016 Posts

Quote:
 Originally Posted by MattcAnderson I posted to the numberphile youtube page that this problem has been solved. Regards, Matt
I posted a link to this thread on the video page near the start of it as well.

2018-01-23, 21:59   #27
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

2·3·11·23 Posts

Quote:
 Originally Posted by henryzz Also I believe papers have been published on less worthwhile subjects.
I've thought the same in the recent days, maybe I'll come up with a paper.

 2018-03-16, 19:12 #28 Auto Felix   Feb 2018 110 Posts How do you know that all sequences start with 1, and end with 8 (for even) or 3 (for odd)? Is there a proof?
2018-03-17, 09:05   #29
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

2×3×11×23 Posts

Quote:
 Originally Posted by Auto Felix How do you know that all sequences start with 1, and end with 8 (for even) or 3 (for odd)? Is there a proof?
I"ve constructed all basic sequences that holds this, and then by induction we still maintain this. Note that all integers in [1,24] is free, because T(c,0) and T(c,1) doesn't use them. So we can use these small (1,3,8) integers at the endpoints.

You could ask why we haven't used a shifted and reversed representation, so the sequences starts with 1,3 and 1,8; because in that case we don't know the last term of seq0 and seq1, so we can't glue the sequences. Or why we haven't used the constant 3 at the end for every sequence, because in that case 3=seq0(n)=seq1(n+1), but (n+1-n)=1 is odd so the parity position condition wouldn't be true. There are some traps here.

Last fiddled with by R. Gerbicz on 2018-03-17 at 09:09

2021-11-02, 10:51   #30
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

2·3·11·23 Posts

Quote:
 Originally Posted by R. Gerbicz The above ideas were quite good, call seq0 and seq1 a nice pair of sequence iff length(seq0)=n and length(seq1)=n+1 and for all k<=n it is true that if k=seq0[p]=seq1[q] then p-q is even (in other word p+q is even), so we see the same terms in the same position's parity. ... Observe that it is determined what we should choose T(c,0) or T(c,1) for each c (so here you have no real choice), because these contain the same integers, and we know the extra term in T(c,1), why(?), because if in seq1 the (n+1) is in position k, then k==n+1 mod 2.
There was a request to explain this more, took me some time to understand some tricks.

First why parity is so important here. It is trivial: for each c=-24..24 we choose T(c,0) or T(c,1), exactly one of them. Say c=6,-6 if you choose T(6,1) and T(-6,1) then we are good, covering the 6 and -6 residues mod 49, the same happens for choosing T(6,0) and T(-6,0). But why isn't this broken if we'd select T(6,0) and T(-6,1), these contains for all x<=n the 49*x+-6 numbers, if you choose 49*x+6 in T(6,0) and 49*x+6 in T(-6,1) then the sequence is broken, the same integer appears twice. The trick is that in seq0 and seq1 all x<=n numbers appear in the same parity position, this forces that if one seq you'll choose 49*x+6 then in the other it'll be 49*x-6.

Let res=47 so we want the solution for N=49*n+47, when we know the good sequence pair for n and n+1. Just for the example remain at c=6,-6 the extra n+1 term in seq1 is in the parity position of n+1 mod 2, because with seq0 these contain the 1..n integers in the same parity position, so the largest two terms in T(6,1) and T(-6,1) are:
y0=49*(n+1)+(-1)^(n+1)*6 and
y1=49*(n+1)+(-1)^(n+1)*(-6).
First notice that all terms except y0,y1 in these two seq are at most 49*n+24, so not larger than N=49*n+47 and this is true in general, because we recurse for res>=24. What is really not explained, but in the code (quite hidden), that you need to know also the parity of n to know these two terms: say n is even then y0=49*n+43 and y1=49*n+55, but N=49*n+47, so here y0 should be selected but not y1 and this is forced, so you have to select T(6,1) and T(-6,0).

What is also important: you have to maintain the parity condition for N (to make a working induction), how do you ensure that this will hold? When you glue the sequences you're using 1 integer or n or n+1 integers in a block, if you know the parity of n you'll know the parity between subsequences, and a smaller trick: for a subsequence it is enough to see that the first term goes to the same parity position.

ps. in some places we used the reverse of the T(c,) subsequence to give more breath to the method.

2021-11-12, 14:34   #31
arbooker

"Andrew Booker"
Mar 2013

3·29 Posts

Quote:
 Originally Posted by R. Gerbicz There was a request to explain this more, took me some time to understand some tricks.
You really should write this up for publication, if only to provide a reference point and a proof that's more than a quick description on an internet forum. You're welcome to send it to me for consideration at JNT, and there are loads of other good options. (The American Mathematical Monthly comes to mind, given that the problem has broad interest and the proof is also very accessible.)

2021-11-15, 15:12   #32
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

2×3×11×23 Posts

Quote:
 Originally Posted by arbooker You really should write this up for publication, if only to provide a reference point and a proof that's more than a quick description on an internet forum. You're welcome to send it to me for consideration at JNT, and there are loads of other good options. (The American Mathematical Monthly comes to mind, given that the problem has broad interest and the proof is also very accessible.)
Thanks for the idea, then I'll try the AMM first, need to write down the solution.
It is a somewhat recreational Maths problem, but worth a paper.

 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 07:19.

Tue Nov 30 07:19:33 UTC 2021 up 130 days, 1:48, 0 users, load averages: 1.29, 1.05, 1.04