A126684 -id:A126684 - cp's OEIS frontend

A377412 a(n) is the least k > 0 such that k*n belongs to A126684.

1, 1, 1, 7, 1, 1, 7, 3, 1, 9, 1, 31, 7, 5, 3, 91, 1, 1, 9, 55, 1, 1, 31, 3, 7, 13, 5, 3, 3, 9, 91, 11, 1, 33, 1, 39, 9, 113, 55, 7, 1, 25, 1, 127, 31, 121, 3, 443, 7, 21, 13, 87, 5, 97, 3, 19, 3, 73, 9, 1199, 91, 21, 11, 1387, 1, 1, 33, 983, 1, 1, 39, 19, 9

Offset: 0

Rémy Sigrist, Oct 27 2024

This sequence is well defined: for any positive integer n, according to the pigeonhole principle, A195156(i) mod n = A195156(j) mod n for some distinct i and j, hence n divides b = abs(A195156(i) - A195156(j)), and as b belongs to A126684, a(n) <= b/n.

			The first terms, alongside the binary expansion of a(n)*n, are:
  n   a(n)  bin(a(n)*n)
  --  ----  -----------
   0     1            0
   1     1            1
   2     1           10
   3     7        10101
   4     1          100
   5     1          101
   6     7       101010
   7     3        10101
   8     1         1000
   9     9      1010001
  10     1         1010
  11    31    101010101
  12     7      1010100

Rémy Sigrist, Table of n, a(n) for n = 0..10000
Rémy Sigrist, C++ program

See A300867 for a similar sequence.

Cf. A032937, A126684, A195156, A377413.

(* Increase nmax for n>92 in A377412 *) nmax = 1000; b[n_] := FromDigits[IntegerDigits[n, 2], 4];A126684=Union[A000695 = b /@ Range[0, nmax], 2 A000695][[1 ;; nmax+1]] ;A377412={};Do[k=0;Until[MemberQ[A126684,k*n],k++]; AppendTo[A377412,k],{n,0,72}];A377412 (* James C. McMahon, Oct 29 2024 *)

a(n) >= A300867(n).

a(n) = 1 iff n belongs to A126684.

A377413 a(n) is the least term of A126684 of the form k*n with k > 0.

Original entry on oeis.org

0, 1, 2, 21, 4, 5, 42, 21, 8, 81, 10, 341, 84, 65, 42, 1365, 16, 17, 162, 1045, 20, 21, 682, 69, 168, 325, 130, 81, 84, 261, 2730, 341, 32, 1089, 34, 1365, 324, 4181, 2090, 273, 40, 1025, 42, 5461, 1364, 5445, 138, 20821, 336, 1029, 650, 4437, 260, 5141, 162

Offset: 0

Rémy Sigrist, Oct 27 2024

			The first terms, in decimal and in binary, are:
  n   a(n)  bin(a(n))
  --  ----  ---------
   0     0          0
   1     1          1
   2     2         10
   3    21      10101
   4     4        100
   5     5        101
   6    42     101010
   7    21      10101
   8     8       1000
   9    81    1010001
  10    10       1010
  11   341  101010101
  12    84    1010100

Rémy Sigrist, Table of n, a(n) for n = 0..10000
Rémy Sigrist, C++ program

See A300889 for a similar sequence.

Cf. A126684, A377412.

a(n) = A377412(n)*n.
a(n) >= A300889(n) for any n > 0.
a(n) = n iff n belongs to A126684.

A377414 a(n) is the largest term of A126684, say b, such that n AND b = b (where AND denotes the bitwise AND operator).

Original entry on oeis.org

0, 1, 2, 2, 4, 5, 4, 5, 8, 8, 10, 10, 8, 8, 10, 10, 16, 17, 16, 17, 20, 21, 20, 21, 16, 17, 16, 17, 20, 21, 20, 21, 32, 32, 34, 34, 32, 32, 34, 34, 40, 40, 42, 42, 40, 40, 42, 42, 32, 32, 34, 34, 32, 32, 34, 34, 40, 40, 42, 42, 40, 40, 42, 42, 64, 65, 64, 65

Offset: 0

Rémy Sigrist, Oct 27 2024

For any n > 0 with binary expansion (b_1 = 1, b_2, ..., b_k), the binary expansion of a(n) is (c_1, ..., c_k) where c_i = b_i when i is odd, c_i = 0 when i is even.

For any n, the value c = n - a(n) also belongs to A126684 and satisfies n AND c = c (see A377415).

			The first terms, in decimal and in binary, are:
  n   a(n)  bin(n)  bin(a(n))
  --  ----  ------  ---------
   0     0       0          0
   1     1       1          1
   2     2      10         10
   3     2      11         10
   4     4     100        100
   5     5     101        101
   6     4     110        100
   7     5     111        101
   8     8    1000       1000
   9     8    1001       1000
  10    10    1010       1010
  11    10    1011       1010
  12     8    1100       1000
  13     8    1101       1000
  14    10    1110       1010
  15    10    1111       1010

Rémy Sigrist, Table of n, a(n) for n = 0..8191
Index entries for sequences related to binary expansion of n

See A063694, A063695 and A374356 for similar sequences.

Cf. A000975, A070939, A126684, A371442, A377415.

a(n) = { my (v = 0, x = exponent(n), y); while (n, n -= 2^y = exponent(n); if (x%2 == y%2, v += 2^y;);); return (v); }

a(n) <= n with equality iff n belongs to A126684.
a(a(n)) = a(n).
a(2*n) = 2*a(n).
a(n) = n AND A000975(A070939(n)). - Alan Michael Gómez Calderón, Jun 27 2025

A302757 a(n) is the smallest number whose greedy representation as a sum of terms of A126684 uses n terms.

Original entry on oeis.org

1, 3, 13, 55, 225, 907, 3637, 14559, 58249, 233011, 932061, 3728263, 14913073, 59652315, 238609285, 954437167, 3817748697, 15270994819, 61083979309, 244335917271, 977343669121, 3909374676523, 15637498706133, 62549994824575, 250199979298345, 1000799917193427

Offset: 1

David Eppstein, Apr 12 2018

A126684 is described as the fastest-growing sequence such that every nonnegative integer is the sum of two of its terms. However, if one uses a greedy algorithm to find a representation as a sum of its terms, the length of the representation will typically be more than two. This sequence gives the numbers whose greedy representations have record-setting lengths. For example, a(3) = 13 because (although 13 = 8 + 5, a representation as a sum of two terms of A126684) the greedy algorithm represents it as the three-term sum 13 = 10 + 2 + 1.

Colin Barker, Table of n, a(n) for n = 1..1000
David Eppstein, Making Change in 2048, arXiv:1804.07396 [cs.DM], 2018.
Index entries for linear recurrences with constant coefficients, signature (6,-9,4).

Cf. A126684.

Fold[Append[#1, 4 Last[#1] + 2 #2 - 5] &, {1}, Range[2, 25]] (* Michael De Vlieger, Apr 12 2018 *)

Vec(x*(1 - 3*x + 4*x^2) / ((1 - x)^2*(1 - 4*x)) + O(x^60)) \\ Colin Barker, Apr 13 2018

a(n) = 4*a(n-1) + 2*n - 5.
From Colin Barker, Apr 13 2018: (Start)
G.f.: x*(1 - 3*x + 4*x^2) / ((1 - x)^2*(1 - 4*x)).
a(n) = (7 + 2^(1+2*n) - 6*n) / 9.
a(n) = 6*a(n-1) - 9*a(n-2) + 4*a(n-3) for n>3.
(End)

A000695 Moser-de Bruijn sequence: sums of distinct powers of 4.

Original entry on oeis.org

0, 1, 4, 5, 16, 17, 20, 21, 64, 65, 68, 69, 80, 81, 84, 85, 256, 257, 260, 261, 272, 273, 276, 277, 320, 321, 324, 325, 336, 337, 340, 341, 1024, 1025, 1028, 1029, 1040, 1041, 1044, 1045, 1088, 1089, 1092, 1093, 1104, 1105, 1108, 1109, 1280, 1281, 1284, 1285

Offset: 0

N. J. A. Sloane

Although this is a list, it has offset 0 for both historical and mathematical reasons.
Numbers whose set of base-4 digits is a subset of {0,1}. - Ray Chandler, Aug 03 2004, corrected by M. F. Hasler, Oct 16 2018
Numbers k such that the sum of the base-2 digits of k = sum of the base-4 digits of k. - Clark Kimberling
Numbers having the same representation in both binary and negabinary (A039724). - Eric W. Weisstein
This sequence has many other interesting and useful properties. Every term k corresponds to a unique pair i,j with k = a(i) + 2*a(j) (i=A059905(n), j=A059906(n)) -- see A126684. Every list of numbers L = [L1,L2,L3,...] can be encoded uniquely by "recursive binary interleaving", where f(L) = a(L1) + 2*a(f([L2,L3,...])) with f([])=0. - Marc LeBrun, Feb 07 2001
This may be described concisely using the "rebase" notation b[n]q, which means "replace b with q in the expansion of n", thus "rebasing" n from base b into base q. The present sequence is 2[n]4. Many interesting operations (e.g., 10[n](1/10) = digit reverse, shifted) are nicely expressible this way. Note that q[n]b is (roughly) inverse to b[n]q. It's also natural to generalize the idea of "basis" so as to cover the likes of F[n]2, the so-called "fibbinary" numbers (A003714) and provide standard ready-made images of entities obeying other arithmetics, say like GF2[n]2 (e.g., primes = A014580, squares = the present sequence, etc.). - Marc LeBrun, Mar 24 2005
a(n) is also equal to the product n X n formed using carryless binary multiplication (A059729, A063010). - Henry Bottomley, Jul 03 2001
Numbers k such that A004117(k) is odd. - Pontus von Brömssen, Nov 25 2008
Fixed point of the morphism: 0 -> 01; 1 -> 45; 2 -> 89; ...; n -> (4n)(4n+1), starting from a(0)=0. - Philippe Deléham, Oct 22 2011
If n is even and present, so is n+1. - Robert G. Wilson v, Oct 24 2014
Also: interleave binary digits of n with 0's. (Equivalent to the "rebase" interpretation above.) - M. F. Hasler, Oct 16 2018
Named after the Austrian-Canadian mathematician Leo Moser (1921-1970) and the Dutch mathematician Nicolaas Govert de Bruijn (1918-2012). - Amiram Eldar, Jun 19 2021
Conjecture: The sums of distinct powers of k > 2 can be constructed as the following (k-1)-ary rooted tree. For each n the tree grows and a(n) is then the total number of nodes. For n = 1, the root of the tree is added. For n > 1, if n is odd one leaf of depth n-2 grows one child. If n is even all leaves of depth >= (n - 1 - A000225(A001511(n/2))) grow the maximum number of children. An illustration is provided in the links. - John Tyler Rascoe, Oct 09 2022

			G.f.: x + 4*x^2 + 5*x^3 + 16*x^4 + 17*x^5 + 20*x^6 + 21*x^7 + 64*x^8 + ...
If n=27, then b_0=1, b_1=1, b_2=0, b_3=1, b_4=1. Therefore a(27) = 4^4 + 4^3 + 4 + 1 = 325; k = b_0 + b_2*2 + b_4*2^2 = 5, l = b_1 + b_3*2 = 3, such that a(5)=17, a(3)=5 and 27 = 17 + 2*5. - _Vladimir Shevelev_, Nov 10 2008

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 0..1023
Jean-Paul Allouche and Jeffrey Shallit, The ring of k-regular sequences, Theoretical Computer Sci., Vol. 98 (1992), pp. 163-197.
Jean-Paul Allouche and Jeffrey Shallit, The ring of k-regular sequences, Theoretical Computer Sci., Vol. 98 (1992), pp. 163-197.
David Applegate, Marc LeBrun and N. J. A. Sloane, Carryless Arithmetic (I): The Mod 10 Version.
David Applegate, Omar E. Pol and N. J. A. Sloane, The Toothpick Sequence and Other Sequences from Cellular Automata, Congressus Numerantium, Vol. 206 (2010), pp. 157-191. [There is a typo in Theorem 6: (13) should read u(n) = 4.3^(wt(n-1)-1) for n >= 2.]
David Applegate, Marc LeBrun and N. J. A. Sloane, Dismal Arithmetic, J. Int. Seq., Vol. 14 (2011), Article 11.9.8.
Joerg Arndt, Matters Computational (The Fxtbook), pp. 59-60, pp. 750-751.
Robert Baillie and Thomas Schmelzer, Summing Kempner's Curious (Slowly-Convergent) Series, Mathematica Notebook kempnerSums.nb, Wolfram Library Archive, 2008.
N. G. de Bruijn, Some direct decompositions of the set of integers, Math. Comp., Vol. 18, No. 88 (1964), pp. 537-546.
Karl Dilcher and Larry Ericksen, Hyperbinary expansions and Stern polynomials, Elec. J. Combin, Vol. 22, No. 2 (2015), #P2.24.
Roger B. Eggleton, Maximal Midpoint-Free Subsets of Integers, International Journal of Combinatorics Volume 2015, Article ID 216475, 14 pages.
S. J. Eigen, Y. Ito, and V. S. Prasad, Universally bad integers and the 2-adics, J. Number Theory, Vol. 107, No. 2 (2004), pp. 322-334.
Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Identities and periodic oscillations of divide-and-conquer recurrences splitting at half, arXiv:2210.10968 [cs.DS], 2022, p. 44.
Bin Lan and James A. Sellers, Properties of a Restricted Binary Partition Function a la Andrews and Lewis, Electronic Journal of Combinatorial Number Theory, Volume 15 #A23.
Lukasz Merta, Composition inverses of the variations of the Baum-Sweet sequence, arXiv:1803.00292 [math.NT], 2018. See m(n) p. 11.
Leo Moser, An application of generating series, Math. Mag., Vol. 35, No. 1 (1962), pp. 37-38.
Leo Moser, An application of generating series, Math. Mag., Vol. 35, No. 1 (1962), pp. 37-38. [Annotated scanned copy]
John Tyler Rascoe, Illustration of terms.
Vladimir Shevelev, Two analogs of Thue-Morse sequence, arXiv:1603.04434 [math.NT], 2016-2017.
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS
Ralf Stephan, Some divide-and-conquer sequences with (relatively) simple ordinary generating functions, 2004.
Ralf Stephan, Table of generating functions.
Ralf Stephan, Divide-and-conquer generating functions. I. Elementary sequences, arXiv:math/0307027 [math.CO], 2003.
Stephen Nicholas Swatman, Ana-Lucia Varbanescu, Andy D. Pimentel, Andreas Salzburger, and Attila Krasznahorkay, Finding Morton-Like Layouts for Multi-Dimensional Arrays Using Evolutionary Algorithms, arXiv:2309.07002 [cs.NE], 2023.
Eric Weisstein's World of Mathematics, Moser-de Bruijn Sequence.
Eric Weisstein's World of Mathematics, Negabinary.
Wikipedia, Morton code. (also known as Z-order curve. Cf. Marc LeBrun's comments about binary interleaving.)
Index entries for 2-automatic sequences.

For generating functions Product_{k>=0} (1 + a*x^(b^k)) for the following values of (a,b) see: (1,2) A000012 and A000027, (1,3) A039966 and A005836, (1,4) A151666 and A000695, (1,5) A151667 and A033042, (2,2) A001316, (2,3) A151668, (2,4) A151669, (2,5) A151670, (3,2) A048883, (3,3) A117940, (3,4) A151665, (3,5) A151671, (4,2) A102376, (4,3) A151672, (4,4) A151673, (4,5) A151674.
Main diagonal of A048720, second column of A048723.
Cf. A000225, A000302, A001511, A007583, A059884, A059901, A059904, A059905, A059906, A007088, A033042-A033052, A126684, A145812.
A062880(n) = 2*a(n); A001196(n) = 3*a(n).
Row 4 of array A104257.

uint32_t a_next(uint32_t a_n) { return (a_n + 0xaaaaaaab) & 0x55555555; } /* Falk Hüffner, Jan 24 2022 */

a000695 n = if n == 0 then 0 else 4 * a000695 n' + b
            where (n',b) = divMod n 2
-- Reinhard Zumkeller, Feb 21 2014, Dec 03 2011

function a(n)
    m, r, b = n, 0, 1
    while m > 0
        m, q = divrem(m, 2)
        r += b * q
        b *= 4
    end
r end; [a(n) for n in 0:51] |> println # Peter Luschny, Jan 03 2021

m:=60; R:=PowerSeriesRing(Integers(), m); [0] cat Coefficients(R!( (&+[4^k*x^(2^k)/(1+x^(2^k)): k in [0..20]])/(1-x) )); // G. C. Greubel, Dec 06 2018

a:= proc(n) local m, r, b; m, r, b:= n, 0, 1;
      while m>0 do r:= r+b*irem(m, 2, 'm'); b:= b*4 od; r
    end:
seq(a(n), n=0..100);  # Alois P. Heinz, Mar 16 2013

Table[FromDigits[Riffle[IntegerDigits[n, 2], 0], 2], {n, 0, 51}] (* Jacob A. Siehler, Jun 30 2010 *)
Table[FromDigits[IntegerDigits[n, 2], 4], {n, 0, 51}] (* IWABUCHI Yu(u)ki, Apr 06 2013 *)
Union@ Flatten@ NestList[ Join[ 4#, 4# + 1] &, {0}, 6] (* Robert G. Wilson v, Aug 30 2014 *)
Select[ Range[0, 1320], Total@ IntegerDigits[#, 2] == Total@ IntegerDigits[#, 4] &] (* Robert G. Wilson v, Oct 24 2014 *)
Union[FromDigits[#,4]&/@Flatten[Table[Tuples[{0,1},n],{n,6}],1]] (* Harvey P. Dale, Oct 03 2015 *)
a[ n_] := Which[n < 1, 0, EvenQ[n], a[n/2] 4, True, a[n - 1] + 1]; (* Michael Somos, Nov 30 2016 *)

a(n)=n=binary(n);sum(i=1,#n,n[i]*4^(#n-i)) \\ Charles R Greathouse IV, Mar 04 2013

{a(n) = if( n<1, 0, n%2, a(n-1) + 1, a(n/2) * 4)}; /* Michael Somos, Nov 30 2016 */

A000695(n)=fromdigits(binary(n),4) \\ M. F. Hasler, Oct 16 2018

def a(n):
    n = bin(n)[2:]
    x = len(n)
    return sum(int(n[i]) * 4**(x - 1 - i) for i in range(x))
[a(n) for n in range(101)] # Indranil Ghosh, Jun 25 2017

def a():
    x = 0
    while True:
        yield x
        y = ~(x << 1)
        x = (x - y) & y # Falk Hüffner, Dec 21 2021

from itertools import count, islice
def A000695_gen(): # generator of terms
    yield (a:=0)
    for n in count(1):
        yield (a := a+((1<<((~n & n-1).bit_length()<<1)+1)+1)//3)
A000695_list = list(islice(A000695_gen(),30)) # Chai Wah Wu, Feb 22 2023

def A000695(n): return int(bin(n)[2:],4) # Chai Wah Wu, Aug 21 2023

s=(sum(4^k*x^(2^k)/(1+x^(2^k)) for k in range(10))/(1-x)).series(x, 60); s.coefficients(x, sparse=False) # G. C. Greubel, Dec 06 2018

G.f.: 1/(1-x) * Sum_{k>=0} 4^k*x^2^k/(1+x^2^k). - Ralf Stephan, Apr 27 2003
Numbers k such that the coefficient of x^k is > 0 in Product_{n>=0} 1+x^(4^n). - Benoit Cloitre, Jul 29 2003
For n >= 1, a(n) = a(n-1) + (4^t+2)/6, where t is such that 2^t||2n,or t=A007814(2n). a(n) = (A145812(n+1) - 1)/2. - Vladimir Shevelev, Nov 07 2008
To get a(n), write n as Sum b_j*2^j, then a(n) = Sum b_j*2^(2j). The Diophantine equation a(k)+2a(l)=n has the unique solution: k=Sum b_(2j)*2^j, l=Sum b_(2j+1)*2^j. - Vladimir Shevelev, Nov 10 2008
If a(k)*a(l)=a(m), then k*l=m (the inverse, generally speaking, is not true). - Vladimir Shevelev, Nov 21 2008
Let F(x) be the generating function, then F(x)*F(x^2) = 1/(1-x). - Joerg Arndt, May 12 2010
a(n+1) = (a(n) + 1/3) & -1/3, where & is bitwise AND, -1/3 is represented as the infinite dyadic ...010101 (just as -1 is ...111111 in two's complement) and +1/3 is ...101011. - Marc LeBrun, Sep 30 2010
a(n) = Sum_{k>=0} {A030308(n,k)*b(k)} with b(k) = 4^k = A000302(k). - Philippe Deléham, Oct 18 2011
A182560(6*a(n)) = 0. - Reinhard Zumkeller, May 05 2012
G.f.: x/(1-x^2) + 4*x^2/((1-x)*(W(0) - 4*x - 4*x^2)), where W(k) = 1 + 4*x^(2^k) + 5*x^(2^(k+1)) - 4*x^(2^(k+1))*(1 + x^(2^(k+1)))^2/W(k+1); (continued fraction). - Sergei N. Gladkovskii, Jan 04 2014
liminf a(n)/n^2 = 1/3 and limsup a(n)/n^2 = 1. - Gheorghe Coserea, Sep 15 2015
Let f(x) = (Sum_{k=-oo..oo} floor(x*2^k)/4^k)/2. Then f(x) is a real-valued extension of a(n), which a(n) approximates in the sense that f(x) = lim_{k->oo} a(floor(x*2^k))/a(2^k). - Velin Yanev, Nov 28 2016
G.f. A(x) satisfies x/(1 - x^2) = A(x) - 4 * (1+x) * A(x^2). - Michael Somos, Nov 30 2016
a(2^k) = 4^k = A000302(k). a(n + 2^k) = a(n) + a(2^k) for 2^k > n >= 1. - David A. Corneth, Oct 16 2018
Sum_{n>=1} 1/a(n) = 1.886176434476107244547259512076353532930680508099044818673061351780360211128... (calculated using Baillie and Schmelzer's kempnerSums.nb, see Links). - Amiram Eldar, Feb 12 2022

A008932 Number of increasing sequences of Goldbach type of length n; a(0) = 1 by convention.

Original entry on oeis.org

1, 1, 2, 5, 17, 65, 292, 1434, 7875, 47098, 305226, 2122983, 15752080, 124015310, 1031857395, 9041908204, 83186138212, 801235247145, 8059220936672, 84463182889321

Offset: 0

Mauro Torelli (torelli(AT)hermes.mc.dsi.unimi.it)

From David S. Newman, Feb 17 2009: (Start)
This sequence also arises in the following way.
Call a set A of nonnegative integers a basis if every nonnegative integer can be written as the sum of two (not necessarily distinct) elements of A.
Call a basis an increasing basis if its elements are arranged in increasing order, a0 < a1 < a2 < ...
For example, A126684: 0, 1, 2, 4, 5, 8, 10, 16, 17, 20, 21, 32, 34, 40, ... is an increasing basis.
Now consider the set of all initial subsequences of any length {a0, a1, a2,...,an} of all the increasing bases.
These can be arranged in lexicographic order, giving:
  0
  0, 1
  0, 1, 2
  0, 1, 3
  0, 1, 2, 3
  0, 1, 2, 4
  0, 1, 2, 5
  0, 1, 3, 4
  0, 1, 3, 5
  ...
How many such subsequences are there of length n? (End)
The answer is a(n-1), or a(n) if "length n" ignores the initial zero. A Goldbach sequence is then an increasing basis with each element increased by 1. - [Corrected by Martin Fuller, Apr 28 2025]
The largest value for each term in any increasing basis is given by A123509. - Martin Fuller, Jun 01 2010

M. Torelli, Increasing integer sequences and Goldbach's conjecture, preprint, 1996.

M. Torelli, Increasing integer sequences and Goldbach's conjecture, RAIRO - Theoretical Informatics and Applications, vol.40, no.02 (April 2006), pp.107-121.
Index entries for sequences related to Goldbach conjecture

Cf. A123509.

A008932(n,pol=0)= { local(a=0, i, pol2);
!n && return(1);
i = #pol;
pol2 = pol^2;
for (i=#pol, #pol2+1,
a += A008932(n-1, pol+'x^i);
!polcoeff(pol2,i) && break;);
a } \\ Martin Fuller, Jun 01 2010

a(9)-a(14) from Martin Fuller, Feb 18 2009
Edited by N. J. A. Sloane, Mar 12 2009
a(15)-a(16) from Sean A. Irvine, Apr 19 2018
a(17)-a(19) from Martin Fuller, Apr 30 2025

A032937 Numbers k whose base-2 representation Sum_{i=0..m} d(i)*2^(m-i) has d(i)=0 for all odd i, excluding 0. Here m is the position of the leading bit of k.

Original entry on oeis.org

1, 2, 4, 5, 8, 10, 16, 17, 20, 21, 32, 34, 40, 42, 64, 65, 68, 69, 80, 81, 84, 85, 128, 130, 136, 138, 160, 162, 168, 170, 256, 257, 260, 261, 272, 273, 276, 277, 320, 321, 324, 325, 336, 337, 340, 341, 512, 514, 520, 522, 544, 546

Offset: 1

Clark Kimberling

Essentially the same as A126684. - R. J. Mathar, Jun 15 2008

A126684 is the primary entry for this sequence. - Franklin T. Adams-Watters, Aug 30 2014

Cf. A033053, A126684.

Join[{1},Select[Range[0,600],Union[Take[IntegerDigits[#,2],{2,-1,2}]]=={0}&]] (* Harvey P. Dale, Sep 17 2023 *)

from gmpy2 import digits
def A032937(n):
    def bisection(f,kmin=0,kmax=1):
        while f(kmax) > kmax: kmax <<= 1
        while kmax-kmin > 1:
            kmid = kmax+kmin>>1
            if f(kmid) <= kmid:
                kmax = kmid
            else:
                kmin = kmid
        return kmax
    def g(x):
        s = digits(x,4)
        for i in range(l:=len(s)):
            if s[i]>'1':
                break
        else:
            return int(s,2)
        return int(s[:i]+'1'*(l-i),2)
    def f(x): return n+x-g(x)-g(x>>1)
    return bisection(f,n,n) # Chai Wah Wu, Oct 29 2024

A032945 Numbers k whose base-10 representation Sum_{i=0..m} d(i)*10^(m-i) has d(i)=0 for all odd i. Here m is the position of the lead digit of k.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 200, 201, 202, 203, 204, 205, 206, 207, 208, 209, 300, 301, 302, 303, 304, 305, 306, 307, 308, 309, 400, 401, 402, 403

Offset: 1

Clark Kimberling

Every nonnegative integer can be represented as the sum of two members of this sequence. - Franklin T. Adams-Watters, Aug 30 2014

This first differs from A236402 at a(110)=1000 (followed by 1010, 1020, 1030, ...), while A236402(110)=910 (followed by 1000, 1001, 1002, ...). - M. F. Hasler, Dec 28 2014

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A126684.

N:= 6: # to get all terms with up to N digits
A[1]:= 0:
count:= 1:
for d from 1 to N do
   dp:= ceil(d/2);
   for j from 10^(dp-1) to 10^dp-1 do
      L:= ListTools[Reverse](convert(j,base,10));
      L:= ListTools[Interleave](L,[0$(d-dp)]);
      count:= count+1;
      A[count]:= add(L[i]*10^(d-i),i=1..d);
    od
od:
seq(A[i],i=1..count); # Robert Israel, Aug 31 2014

is(n)=!forstep(i=2,#n=digits(n),2,n[i]&&return) \\ M. F. Hasler, Dec 28 2014

def ok(n): return str(n)[1::2].strip('0') == ""
print([k for k in range(404) if ok(k)]) # Michael S. Branicky, Apr 12 2022

Definition corrected by Franklin T. Adams-Watters, Aug 30 2014

A260488 Numbers of the form 2^m * (6k + 1) for m, k >= 0, and 0.

Original entry on oeis.org

0, 1, 2, 4, 7, 8, 13, 14, 16, 19, 25, 26, 28, 31, 32, 37, 38, 43, 49, 50, 52, 55, 56, 61, 62, 64, 67, 73, 74, 76, 79, 85, 86, 91, 97, 98, 100, 103, 104, 109, 110, 112, 115, 121, 122, 124, 127, 128, 133, 134, 139, 145, 146, 148, 151, 152, 157

Offset: 0

Franklin T. Adams-Watters, Jul 27 2015

Alternate definition: starting with a(0) = 0, include 2n if n is in the sequence, and include 2n+1 if no two previous terms sum to 2n+1.
It suffices to prove this for odd n. If n == 3(6), n-2 == 1 (mod 6); if n == 5 (mod 6), n-4 == 1 (mod 6). However, if n == 1 (mod 6), any even k in the sequence, 0 < k < n, will have k !== 0 (mod 3), and so n-k != 1 (mod 3), so it is not in the sequence; thus n must be.
Every nonnegative integer is the sum of two members of this sequence; every positive integer is the sum of two distinct members of this sequence. For odd n, this is by the construction in the alternate definition; and for even n, by induction n/2 = i + j, and so n = 2i + 2j.
It follows that:
* No member of this sequence except 0 is a multiple of 3.
* The sequence has a density of 1/3.
* The difference between consecutive terms is always one of {1, 2, 3, 5, 6}, and each of these occurs infinitely often, with 1 having density 1/3 and the others having density 1/6.
* The sequence is closed under multiplication.
* The primes in the sequence are A045375.

			Using the alternate definition:
1 is in the sequence because it is not the sum of 2 elements from {0}.
2 is in the sequence because 2 = 2*1, and 1 is in the sequence.
3 is not in the sequence because 3 = 1 + 2, and 1 and 2 are in the sequence.
6 is not in the sequence because 6 = 2*3, and 3 is not in the sequence.

Franklin T. Adams-Watters, Table of n, a(n) for n = 0..10000

Cf. A126684, A260489, primes A045375, A000265.

Cf. A113448, A115235, A123863.

N:= 1000: # to get all terms <= N
sort([0, seq(seq(2^m*(6*k+1), k = 0 .. floor((N/2^m - 1)/6)), m = 0 .. ilog2(N))]);  # Robert Israel, Aug 25 2015

mx=160;Join[{0},Sort@Flatten@Table[2^m*(6k+1),{m,0,Log2[mx]},{k,0,mx/(6*2^m)}]] (* Robert G. Wilson v, Aug 16 2015 *)

alist(n) = my(r=vector(n),j,k);r[1]=0;j=1;while(j

alim(n)={my(p=1,p2=p,r,j);
  for(k=1,n,
    if(if(k%2==0, polcoeff(p,k\2),polcoeff(p2,k)==0),p+=x^k;p2+=x^k*p));
  r=vector(subst(p,x,1));for(k=0,n,if(polcoeff(p,k),r[j++]=k));r}

n is in the sequence if and only if n = 0 or A000265(n) == 1 (mod 6). [Clarified by Peter Munn, Jun 11 2021]

n is in the sequence if n = 0 or b(n) is nonzero where b = A113448, A115235, or A123863. - Michael Somos, Jul 29 2015

A033053 Numbers whose base-2 representation Sum_{i=0..m} d(i)*2^i has d(i)=1 when i != m mod 2.

Original entry on oeis.org

1, 3, 6, 7, 13, 15, 26, 27, 30, 31, 53, 55, 61, 63, 106, 107, 110, 111, 122, 123, 126, 127, 213, 215, 221, 223, 245, 247, 253, 255, 426, 427, 430, 431, 442, 443, 446, 447, 490, 491, 494, 495, 506, 507, 510, 511, 853, 855, 861, 863

Offset: 1

Clark Kimberling

Numbers 2^(2k)-1 - A062880(m) where 2^(2k-2) >= A062880(m) or 2^(2k+1)-1 - A000695(m) where 2^(2k-1) >= A000695(m). - Franklin T. Adams-Watters, Aug 30 2014

			26 = 11010_2 has m=4, and d(i) = 1 for i=1 and 3.
53 = 110101_2 has m=5, and d(i) = 1 for i=0, 2 and 4.

Robert Israel, Table of n, a(n) for n = 1..12286

Cf. A126684, A000695, A062880.

Disjoint with A032937 if more than 1 digit.

F:= proc(m)
   local n0,j,S;
   n0:= 2^m + add(2^(m-1-2*j),j=0..floor((m-1)/2));
   S:= combinat[powerset]({seq(2^(m-2*j),j=1..floor(m/2))});
   map(t -> convert(t,`+`)+n0,S);
end;
`union`(seq(F(m),m=0..24)}; # Robert Israel, Mar 30 2014

a(2j+2) = 4 a(j)+3,
a(2j+1) = 4 a(j) + 2 if j <= 3*2^(m-1)-2,
a(2j+1) = 4 a(j) + 1 otherwise, where m = floor(log_2(j+1)).

Definition corrected, incorrect cross-reference removed, and recurrence formulas by Robert Israel, Mar 30 2014

cp's OEIS Frontend

A377412 a(n) is the least k > 0 such that k*n belongs to A126684.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A377413 a(n) is the least term of A126684 of the form k*n with k > 0.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A377414 a(n) is the largest term of A126684, say b, such that n AND b = b (where AND denotes the bitwise AND operator).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A302757 a(n) is the smallest number whose greedy representation as a sum of terms of A126684 uses n terms.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A000695 Moser-de Bruijn sequence: sums of distinct powers of 4.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

C

Haskell

Julia

Magma

Maple

Mathematica

PARI

PARI

PARI

Python

Python

Python

Python

Sage

Formula

A008932 Number of increasing sequences of Goldbach type of length n; a(0) = 1 by convention.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI

Extensions

A032937 Numbers k whose base-2 representation Sum_{i=0..m} d(i)*2^(m-i) has d(i)=0 for all odd i, excluding 0. Here m is the position of the leading bit of k.

Views