A105033 Read binary numbers downwards to the right.

0, 1, 0, 3, 2, 1, 4, 7, 6, 5, 0, 11, 10, 9, 12, 15, 14, 13, 8, 3, 18, 17, 20, 23, 22, 21, 16, 27, 26, 25, 28, 31, 30, 29, 24, 19, 2, 33, 36, 39, 38, 37, 32, 43, 42, 41, 44, 47, 46, 45, 40, 35, 50, 49, 52, 55, 54, 53, 48, 59, 58, 57, 60, 63, 62, 61, 56, 51, 34, 1, 68, 71, 70, 69, 64, 75

Offset: 0

Author

N. J. A. Sloane, Apr 04 2005

Keywords

• nonn
• base

Comments

Equals A103530(n+2) - 1. - Philippe Deléham, Apr 06 2005

This sequence can also be produced as follows:

Using binary arithmetic, start with zero and repeatedly add 1 while deferring carries one iteration.

a(0) = 0, c(0) = 1

a(n) = a(n-1) XOR c(n-1)

c(n) = (a(n-1) AND c(n-1))*2+1

where c is the carries, XOR is bitwise exclusive-or, and AND is bitwise and.

This has the property that a(n) = n-c(n)+1. - Christopher Scussel, Jan 31 2025

Examples

			Start with the binary numbers:
  ......0
  ......1
  .....10
  .....11
  ....100
  ....101
  ....110
  ....111
  ...1000
  .......
and read downwards to the right, getting 0, 1, 0, 11, 10, 1, 100, 111, ...
		

Links

• David Applegate, Benoit Cloitre, Philippe Deléham and N. J. A. Sloane, Sloping binary numbers: a new sequence related to the binary numbers, J. Integer Seq. 8 (2005), no. 3, Article 05.3.6, 15 pp.

Crossrefs

Analog of A102370. Cf. A105034, A105025.

Cf. triangular array in A103589.

Programs

Maple

f:= proc (n) local t1, l; t1 := n; for l from 0 to n do if `mod`(n-l,2^(l+1)) = 0 and n >= 2^(l+1) then t1 := t1-2^(l+1) fi; od; t1; end proc;

Mathematica

f[n_] := Block[{k = 0, s = 0}, While[2^(k + 1) < n + 1, If[ Mod[n, 2^(k + 1)] == k, s = s + 2^(k + 1)]; k++ ]; n - s]; Table[ f[n], {n, 0, 75}] (* Robert G. Wilson v, Apr 06 2005 *)

Formula

a(n) = n - Sum_{ k >= 0, 2^{k+1} <= n, n == k mod 2^(k+1) } 2^(k+1).

Structure: blocks of size 2^k taken from A105025, interspersed with terms a(n) itself! Thus a(2^k + k - 1 ) = a(k-1) for k >= 1.

From David Applegate, Apr 06 2005: (Start)

"a(n) = 2^k + a(n-2^k) if k >= 1 and 0 <= n - 2^k - k < 2^k, = a(n-2^k) if k >= 1 and n - 2^k - k = -1, or = 0 if n = 0 (and exactly one of the three conditions is true for any n >= 0).

"Equivalently, a(2^k + k + x) = 2^k + a(k+x) if 0 <= x < 2^k, = a(k+x) if x = -1 (for each n >= 0, there is a unique k, x such that 2^k + k + x = n, k >= 0, -1 <= x < 2^k). This recurrence follows immediately from the definition.

"The recurrence captures three observed facts about a: a(2^k + k - 1) = a(k-1); a consists of blocks of length 2^k of A105025 interspersed with terms of a; a(n) = n - Sum_{ k >= 0, 2^{k+1} <= n, n = k mod 2^(k+1) } 2^(k+1)." (End)

a(n) = sum_{k=0..n} A103589(n,k)*2^(n-k). - L. Edson Jeffery, Dec 01 2013