[seqfan] A057652 has no more terms below 10^4
Alonso Del Arte
alonso.delarte at gmail.com
Sat Oct 16 01:42:00 CEST 2010
When Maximilian Hasler chose A057652 for the Sequence of the Day a couple of
days ago, he piqued my interest in a question that remains unanswered since
at least 2000: is the sequence finite or infinite?
Max also asked if anyone could suggest a nice little program to compute more
terms of the sequence. I've come up with the following monstrosity:
LuckyQ[n_?EvenQ]:=False;
LuckyQ[n_?OddQ]:=Module[{sieve=Range[1,n,2],flag=True,counter=2,m=3},While[flag&&(m<=Length[sieve]),sieve=Drop[sieve,{m,(Floor[Length[sieve]/m])*m,m}];flag=MemberQ[sieve,n];++counter;m=sieve[[counter]]];Return[flag]];
LuckableQ[n_]:=Module[{k=1,max=Ceiling[Log[2,n]],flag=True},While[flag&&(k<max),flag=LuckyQ[n-2^k];k++];Return[flag]]
Select[Range[10000],LuckableQ]//Timing (* You'll probably get a partw error
message. *)
The algorithm is the most primitive sieve, so even for a modest ten
thousand, it takes 14 seconds. It confirms there are no more terms below
that threshold. (It goes without saying that this doesn't prove or disprove
there are more terms.)
A similar program for "primeable" numbers, using Mathematica's built-in
PrimeQ command, confirms there are no more terms of A039669 below 10^5 in
less than 7 seconds. If Erdos had pondered A057652, it's possible he might
have conjectured that it is also finite.
Maybe I will come up with a more sophisticated algorithm later on.
Al
P.S. There is no one who has agreed to pick the Sequence of the Day for
October 16. Now I think we should have a list going a few weeks in advance.
I have already signed myself up for some holidays (see
http://oeis.org/wiki/Template_talk:Sequence_of_the_Day#List).
More information about the SeqFan
mailing list