login
Lexicographically earliest sequence of distinct positive integers with no finite subset summing to a power of 2.
8

%I #20 Jun 09 2023 07:52:01

%S 3,6,9,11,19,24,43,69,77,123,192,261,507,699,1029,1536,2043,4101,5637,

%T 8187,12288,16389,32763,45051,65541,98304,131067,262149,360453,524283,

%U 786432,1048581,2097147,2883579,4194309,6291456,8388603,16777221,23068677,33554427

%N Lexicographically earliest sequence of distinct positive integers with no finite subset summing to a power of 2.

%C The sequence is well defined:

%C - a(1) = 3,

%C - for n > 0, let k be such that 2^k + 1 + a(1) + ... + a(n) < 2^(k+1),

%C - then a(n+1) <= 2^k + 1.

%C The variant where we avoid powers of 3 corresponds to the positive even numbers (A299174).

%H Rémy Sigrist, <a href="/A353889/a353889.txt">C# program</a>

%H Rémy Sigrist, <a href="/A353889/a353889_1.txt">C++ program</a>

%e - 1 = 2^0, so 1 is not a term,

%e - 2 = 2^1, so 2 is not a term,

%e - a(1) = 3 (as 3 is not a power of 2),

%e - 4 = 2^2, so 4 is not a term,

%e - 3 + 5 = 2^3, so 5 is not a term,

%e - a(2) = 6 (as neither 6 nor 3 + 6 is a power of 2),

%e - 3 + 6 + 7 = 2^4, so 7 is not a term,

%e - 8 = 2^3, so 8 is not a term,

%e - a(3) = 9 (as none of 9, 3 + 9, 6 + 9, 3 + 6 + 9 is a power of 2).

%o (C#) See Links section.

%o (C++) See Links section.

%o (Python)

%o from math import gcd

%o from itertools import count, islice

%o def agen(): # generator of terms

%o a, ss, pows2, m = [], set(), {1, 2}, 2

%o for k in count(1):

%o if k in pows2: continue

%o elif k > m: m <<= 1; pows2.add(m)

%o if any(p2-k in ss for p2 in pows2): continue

%o a.append(k); yield k

%o ss |= {k} | {k+si for si in ss if k+si not in ss}

%o while m < max(ss): m <<= 1; pows2.add(m)

%o print(list(islice(agen(), 32))) # _Michael S. Branicky_, Jun 09 2023

%Y Cf. similar sequences: A052349 (prime numbers), A133662 (square numbers), A353966 (Fibonacci numbers), A353969 (factorial numbers), A353980 (primorial numbers), A353983 (Catalan numbers), A354005 (Pell numbers).

%Y Cf. A000079, A008585, A299174, A353918, A353919.

%K nonn

%O 1,1

%A _Rémy Sigrist_, May 09 2022