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

3, 6, 9, 11, 19, 24, 43, 69, 77, 123, 192, 261, 507, 699, 1029, 1536, 2043, 4101, 5637, 8187, 12288, 16389, 32763, 45051, 65541, 98304, 131067, 262149, 360453, 524283, 786432, 1048581, 2097147, 2883579, 4194309, 6291456, 8388603, 16777221, 23068677, 33554427

Offset: 1

Author

Rémy Sigrist, May 09 2022

Keywords

• nonn

Comments

The sequence is well defined:

- a(1) = 3,

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

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

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

Examples

			- 1 = 2^0, so 1 is not a term,
- 2 = 2^1, so 2 is not a term,
- a(1) = 3 (as 3 is not a power of 2),
- 4 = 2^2, so 4 is not a term,
- 3 + 5 = 2^3, so 5 is not a term,
- a(2) = 6 (as neither 6 nor 3 + 6 is a power of 2),
- 3 + 6 + 7 = 2^4, so 7 is not a term,
- 8 = 2^3, so 8 is not a term,
- a(3) = 9 (as none of 9, 3 + 9, 6 + 9, 3 + 6 + 9 is a power of 2).
		

Links

• Rémy Sigrist, C# program
• Rémy Sigrist, C++ program

Crossrefs

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

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

Programs

Python

from math import gcd
from itertools import count, islice
def agen(): # generator of terms
    a, ss, pows2, m = [], set(), {1, 2}, 2
    for k in count(1):
        if k in pows2: continue
        elif k > m: m <<= 1; pows2.add(m)
        if any(p2-k in ss for p2 in pows2): continue
        a.append(k); yield k
        ss |= {k} | {k+si for si in ss if k+si not in ss}
        while m < max(ss): m <<= 1; pows2.add(m)
print(list(islice(agen(), 32))) # Michael S. Branicky, Jun 09 2023