[seqfan] Re: A057652 has no more terms below 10^4

[hv at crypt.org]

Alonso Del Arte <alonso.delarte at gmail.com> wrote:
: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 negative result:

I tried constructing the minimal modular pattern after each new lucky
number was sieved out, and for mod m, checked how many values mod m were
candidates for this sequence taking into account powers up to the first
2^k > m expecting that they would fairly rapidly descend to zero, thus
proving that the sequence is finite.

Instead (assuming my code is correct) I get this:

After sieving 2, lucky pattern now has 1 value mod 2
Up to 2^1, 1 value mod 2 is possible
Up to 2^2, 1 value mod 2 is possible
After sieving 3, lucky pattern has 2 values mod 6
Up to 2^2, 1 value mod 6 is possible
Up to 2^3, 1 value mod 6 is possible
After sieving 7, lucky pattern has 12 values mod 42
Up to 2^3, 4 values mod 42 are possible
Up to 2^4, 3 values mod 42 are possible
Up to 2^5, 2 values mod 42 are possible
Up to 2^6, 2 values mod 42 are possible
After sieving 9, lucky pattern has 32 values mod 126
Up to 2^6, 3 values mod 126 are possible
Up to 2^7, 3 values mod 126 are possible
After sieving 13, lucky pattern has 384 values mod 1638
Up to 2^7, 18 values mod 1638 are possible
Up to 2^8, 18 values mod 1638 are possible
Up to 2^9, 18 values mod 1638 are possible
Up to 2^10, 18 values mod 1638 are possible
Up to 2^11, 18 values mod 1638 are possible
After sieving 15, lucky pattern has 1792 values mod 8190
Up to 2^11, 57 values mod 8190 are possible
Up to 2^12, 57 values mod 8190 are possible
Up to 2^13, 57 values mod 8190 are possible
After sieving 21, lucky pattern has 5120 values mod 24570
Up to 2^13, 132 values mod 24570 are possible
Up to 2^14, 130 values mod 24570 are possible
Up to 2^15, 124 values mod 24570 are possible
After sieving 25, lucky pattern has 24576 values mod 122850
Up to 2^15, 405 values mod 122850 are possible
Up to 2^16, 354 values mod 122850 are possible
Up to 2^17, 352 values mod 122850 are possible
After sieving 31, lucky pattern has 737280 values mod 3808350
Up to 2^17, 5678 values mod 3808350 are possible
Up to 2^18, 5533 values mod 3808350 are possible
Up to 2^19, 5265 values mod 3808350 are possible
Up to 2^20, 5247 values mod 3808350 are possible
Up to 2^21, 5183 values mod 3808350 are possible
Up to 2^22, 5123 values mod 3808350 are possible
[After sieving 33, lucky pattern would have 7864320 values mod 41891850]

So above 2^22, you need only check about one number in 743 as a possible
candidate for A057652; however, this approach does not look likely to yield
a proof that the sequence is finite (and maybe complete).

Hugo