mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2017-01-30, 15:36   #1
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

141910 Posts
Default February 2017

The new Ibm puzzle is out:
https://www.research.ibm.com/haifa/p...ruary2017.html
R. Gerbicz is offline   Reply With Quote
Old 2017-03-02, 23:13   #2
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

3·11·43 Posts
Default

The official solution is here: https://www.research.ibm.com/haifa/p...ruary2017.html

Just a small note: since the total search space (2^42) is not that large, semi-bruteforce routine with a sample c code (without dirty optimizations, avx2 etc.) is possible: use the mod 7 trick, precompute 6+s*(5+s*s*s*(2+s*(3+s))) + b*(5+s*(5+s*(6+s*s*(3+s*6)))) for b=0..1,s=0..6, then the problem is solvable in roughly 3 days on a a fast i7 using 1 core, or in say a week on a slow core i3. Ofcourse the distribution of the problem to all cores/threads is trivial if you want a faster (bruteforce) solution.

My sent solution (not for the star):
The answer is:
3271652365264

A dynamic programming solution in PARI-GP:
Code:
fun(L)={A=matrix(7,2*L+1,i,j,0);A[2,L+1]=1;
for(i=1,L,B=matrix(7,2*L+1,i,j,0);
for(b=0,1,for(k=1,7,for(l=1,2*L+1,if(A[k,l]!=0,
s=k%7;r=l-(L+1);
if(s==b,r=r+2*b-1);
s=(6+s*(5+s*s*s*(2+s*(3+s)))+b*(5+s*(5+s*(6+s*s*(3+s*6)))))%7;
k2=s%7;if(k2==0,k2=7);
l2=r+(L+1);
B[k2,l2]+=A[k,l]))));A=B);
return(2^L-sum(i=1,7,A[i,L+1]))}
Here fun(42) gives the answer for 42 bits.
The complexity of the above algorithm is O(L^2) for L bits, much faster then the almost trivial O(2^L*L) algorithm.
In general if we need the answer for L bits, then for every sequence and in each step r will be in [-L,L] interval and it is enough to know s mod 7. For a given v if we know r and (s mod 7) when we process the bit's of v, then we can get the value of r at the end of the function. So count only the number of possible sequences of length i bits for that we have r and (s mod 7), for the next bit we have 2 possibilities b=0 or 1, for all these sequences we have the same new
r2 and (s2 mod 7) values if we fix the bit. After i=L we get the number of sequences with L bits for each (possible) r and (s mod 7).

In the code: we store the number of sequences in the matrix A, in A[k,l] we see the number of sequences that has s=k mod 7 and r=l-(L+1), in this way the size of matrix is 7X(2*L+1).
At the end, after we processed all L bits, the number of sequences that return a zero value is just sum(i=1,7,A[i,L+1]), so the number of sequences for a non-zero return value is just 2^L-sum(i=1,7,A[i,L+1]).
R. Gerbicz is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
February 2018 Xyzzy Puzzles 27 2018-03-08 06:31
May 2017 R. Gerbicz Puzzles 42 2017-06-06 02:23
February 2016 Xyzzy Puzzles 1 2016-03-07 02:48
February 2015 Xyzzy Puzzles 1 2015-03-02 19:01
P95v238 - anyone else notice the new version Dated February 17, 2004. robreid Software 2 2004-03-02 12:40

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

Wed Dec 2 06:17:26 UTC 2020 up 83 days, 3:28, 1 user, load averages: 1.55, 1.69, 2.02

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.