cp's OEIS Frontend

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

%I A353889 #20 Jun 09 2023 07:52:01
%S A353889 3,6,9,11,19,24,43,69,77,123,192,261,507,699,1029,1536,2043,4101,5637,
%T A353889 8187,12288,16389,32763,45051,65541,98304,131067,262149,360453,524283,
%U A353889 786432,1048581,2097147,2883579,4194309,6291456,8388603,16777221,23068677,33554427
%N A353889 Lexicographically earliest sequence of distinct positive integers with no finite subset summing to a power of 2.
%C A353889 The sequence is well defined:
%C A353889 - a(1) = 3,
%C A353889 - for n > 0, let k be such that 2^k + 1 + a(1) + ... + a(n) < 2^(k+1),
%C A353889 - then a(n+1) <= 2^k + 1.
%C A353889 The variant where we avoid powers of 3 corresponds to the positive even numbers (A299174).
%H A353889 Rémy Sigrist, <a href="/A353889/a353889.txt">C# program</a>
%H A353889 Rémy Sigrist, <a href="/A353889/a353889_1.txt">C++ program</a>
%e A353889 - 1 = 2^0, so 1 is not a term,
%e A353889 - 2 = 2^1, so 2 is not a term,
%e A353889 - a(1) = 3 (as 3 is not a power of 2),
%e A353889 - 4 = 2^2, so 4 is not a term,
%e A353889 - 3 + 5 = 2^3, so 5 is not a term,
%e A353889 - a(2) = 6 (as neither 6 nor 3 + 6 is a power of 2),
%e A353889 - 3 + 6 + 7 = 2^4, so 7 is not a term,
%e A353889 - 8 = 2^3, so 8 is not a term,
%e A353889 - a(3) = 9 (as none of 9, 3 + 9, 6 + 9, 3 + 6 + 9 is a power of 2).
%o A353889 (C#) See Links section.
%o A353889 (C++) See Links section.
%o A353889 (Python)
%o A353889 from math import gcd
%o A353889 from itertools import count, islice
%o A353889 def agen(): # generator of terms
%o A353889     a, ss, pows2, m = [], set(), {1, 2}, 2
%o A353889     for k in count(1):
%o A353889         if k in pows2: continue
%o A353889         elif k > m: m <<= 1; pows2.add(m)
%o A353889         if any(p2-k in ss for p2 in pows2): continue
%o A353889         a.append(k); yield k
%o A353889         ss |= {k} | {k+si for si in ss if k+si not in ss}
%o A353889         while m < max(ss): m <<= 1; pows2.add(m)
%o A353889 print(list(islice(agen(), 32))) # _Michael S. Branicky_, Jun 09 2023
%Y A353889 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 A353889 Cf. A000079, A008585, A299174, A353918, A353919.
%K A353889 nonn
%O A353889 1,1
%A A353889 _Rémy Sigrist_, May 09 2022