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,1

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).

Links

Table of n, a(n) for n=1..40.

Rémy Sigrist, C# program

Rémy Sigrist, C++ program

Example

- 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).

Prog

(C#) See Links section.
(C++) See Links section.
(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

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.

Sequence in context: A344956 A332369 A101723 * A113944 A198514 A242088

Adjacent sequences: A353886 A353887 A353888 * A353890 A353891 A353892

Keyword

nonn

Author

Rémy Sigrist, May 09 2022

Status

approved