mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2018-01-22, 03:16   #23
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

24×613 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
There is a solution for every n>=25 !
Very nice! Man, you are good!
LaurV is offline   Reply With Quote
Old 2018-01-22, 09:20   #24
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

3×1,979 Posts
Default

Very nice. Maybe someone should let numberphile know.
Also I believe papers have been published on less worthwhile subjects.
henryzz is online now   Reply With Quote
Old 2018-01-23, 01:50   #25
MattcAnderson
 
MattcAnderson's Avatar
 
"Matthew Anderson"
Dec 2010
Oregon, USA

953 Posts
Default

I posted to the numberphile youtube page that this problem has been solved.

Regards,
Matt
MattcAnderson is offline   Reply With Quote
Old 2018-01-23, 02:07   #26
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

20C016 Posts
Default

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

2·3·11·23 Posts
Default

Quote:
Originally Posted by henryzz View Post
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.
R. Gerbicz is offline   Reply With Quote
Old 2018-03-16, 19:12   #28
Auto Felix
 
Feb 2018

110 Posts
Default

How do you know that all sequences start with 1, and end with 8 (for even) or 3 (for odd)? Is there a proof?
Auto Felix is offline   Reply With Quote
Old 2018-03-17, 09:05   #29
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

2×3×11×23 Posts
Default

Quote:
Originally Posted by Auto Felix View Post
How do you know that all sequences start with 1, and end with 8 (for even) or 3 (for odd)? Is there a proof?
Thanks for your interest!
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
R. Gerbicz is offline   Reply With Quote
Old 2021-11-02, 10:51   #30
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

2·3·11·23 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
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.
R. Gerbicz is offline   Reply With Quote
Old 2021-11-12, 14:34   #31
arbooker
 
arbooker's Avatar
 
"Andrew Booker"
Mar 2013

3·29 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
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.)
arbooker is offline   Reply With Quote
Old 2021-11-15, 15:12   #32
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

2×3×11×23 Posts
Default

Quote:
Originally Posted by arbooker View Post
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.
R. Gerbicz 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 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

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.