A353919 -id:A353919 - cp's OEIS frontend

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

Rémy Sigrist, May 09 2022

nonn

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

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

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

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.

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

A353918 a(n) is the number of ways to write n as a sum of distinct terms of A353889.

Original entry on oeis.org

1, 0, 0, 1, 0, 0, 1, 0, 0, 2, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 2, 0, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 0, 3, 1, 1, 2, 1, 1, 3, 0, 1, 2, 2, 2, 1, 2, 1, 1, 2, 1, 0, 4, 1, 2, 2, 0, 2, 2, 0, 2, 2, 1, 4, 0, 1, 2, 1, 1, 3, 1, 2, 3, 2, 1, 1, 3, 2, 3, 2, 3, 2, 3, 2, 2, 2, 4

Offset: 0

Rémy Sigrist, May 11 2022

nonn

a(0) = 1 accounts for the empty sum.

			The first terms, alongside the corresponding subsets of A353889, are:
  n   a(n)  Corresponding subsets
  --  ----  ---------------------
   0     1  {}
   1     0  none
   2     0  none
   3     1  {3}
   4     0  none
   5     0  none
   6     1  {6}
   7     0  none
   8     0  none
   9     2  {3, 6}, {9}
  10     0  none
  11     1  {11}
  12     1  {3, 9}

Rémy Sigrist, Table of n, a(n) for n = 0..10000
Rémy Sigrist, Scatterplot of the first 2^18 terms
Rémy Sigrist, C# program
Rémy Sigrist, C++ program

Cf. A353889, A353919 (positions of 0's).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python