cp's OEIS Frontend

Theorem. For every even integer m there exists a representation of the form m=a(r)+a(s). If A(x) is the counting function of a(n)<=x, then A(x)=O(sqrt(x))and Omega(sqrt(x)). Conjecture. The sequence is minimal in the following sense: if any sequence has the counting function B(x)<=A(x) for all x>=1 and B(x) < A(x) for x>=x_0, then there exists an even integer N which is not expressible as a sum of two terms of such sequence.

Every positive odd integer m==3 (mod 8) is a unique sum of the form a(s)+2a(t), while other odd integers are not expressible in this form.

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

Theorem. A positive odd number is in the sequence iff in its binary expansion all bits in the k-th position from the end, for k=2, 4, 6, ..., are zeros. For example, 337, 341 have binary expansions 101010001, 101010101. Thus both of them are in the sequence. If A(x) is the counting function of a(n) <= x, then A(x)=O(sqrt(x))and Omega(sqrt(x)). If f(x) = Sum_{n>=1} x^a(n), abs(x) < 1, then f(x)*f(x^2) = x^3/(1-x^4); a(n) = 2*A145812(n) - 1.

Every positive odd integer m == 3 (mod 2^(2r)) is a unique sum of the form a(2^(r-1)*(s-1)+1) + a(2^(r-1)*(t-1)+1), r=1,2,..., while other odd integers are not expressible in such form (see also comment to A145812). - Vladimir Shevelev, Oct 21 2008

To get the decomposition of m=4k+3 as the sum a(l)+2*a(s), write m-2 as Sum b_j 2^j, then a(s) = 1 + Sum_{j odd} b_j 2^(j-1). For example, if m=55, then we have 53 = 2^0 + 2^2 + 2^4 + 2^5. Thus a(l) = 1 + 2^4 = 17 and the required decomposition is 55 = a(l) + 2*17, such that a(l)=21. We see that l=4, s=3, i.e., "index coordinates" of 55 are (4,3). Thus we have a one-to-one map of positive integers of the form 4k+3 to the positive lattice points on the plane. - Vladimir Shevelev, Oct 26 2008

Odd terms of A000695 (the Moser-de Bruijn sequence: sums of distinct powers of 4). - Jon E. Schoenfield, Mar 18 2021

Or a(n) is in A145812 such that (2*n + 3 - a(n))/2 is in A145812 as well. Note also that a(n) + 2*A090569(n+1) = 2*n + 3. - Vladimir Shevelev, Oct 20 2008

Arrange n persons {1,2,...,n} consecutively on a line rather than around in a circle. Beginning at the left end of the line, we remove every q-th person until we reach the end of the line. At this point we immediately reverse directions, taking care not to "double count" the person at the end of the line and continue to eliminate every q-th person, but now moving right to left. We continue removing people in this back-and-forth manner until there remains a lone survivor w(n,q).

Or a(n) is in A145812 such that 2n+1-2a(n) is in A145812 as well. Note also that 2a(n)+A088442(n-1)=2n+1. - Vladimir Shevelev, Oct 20 2008

Theorem. An integer is in the sequence iff in its expansion on base 3 all digits at the k-th position from the end, k=3, 5, 7, ..., are zeros while the first digit from the end is 1. To get the decomposition of m==1(mod 3) as sum a(l)+3a(s), write m-3 as Sum b_j 3^j, then a(l) = 1 + Sum_{j odd} b_j 3^j.

Every positive odd integer m == 3 (mod 16) is a unique sum of the form a(s) + 2a(t), while other odd integers are not expressible in such form.

Positive integers such that for every integer m==8 (mod 9) there exists a unique representation of m as a sum of the form a(l)+3a(s).

Every even N>=6 is a sum of two terms of the sequence.