A063787 a(2^k) = k + 1 and a(2^k + i) = 1 + a(i) for k >= 0 and 0 < i < 2^k.

1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4

Offset: 1

Author

Reinhard Zumkeller, Aug 16 2001

Keywords

• nonn

Comments

Hamming weights of odd numbers. - Friedjof Tellkamp, Jan 11 2024

Examples

			k = 3: a(2^3) = a(8) = 4 = 3 + 1.
k = 3, i = 5: a(2^3 + 5) = a(13) = 3 = 1 + 2 = 1 + a(5).
From _Omar E. Pol_, Jun 12 2009: (Start)
Triangle begins:
  1;
  2,2;
  3,2,3,3;
  4,2,3,3,4,3,4,4;
  5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5;
  6,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6;
  7,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,3,4,4,5,...
(End)
		

Links

• Michael Gilleland, Some Self-Similar Integer Sequences

Crossrefs

Cf. A000079, A000120, A007814, A086799, A047457, A131136.

Cf. A330038 (partial sums).

Programs

Mathematica

Table[DigitCount[2 n - 1, 2, 1], {n, 1, 105}] (* Friedjof Tellkamp, Jan 11 2024 *)

PARI

a(n) = hammingweight(n-1) + 1; \\ Michel Marcus, Nov 23 2022

Python

def a(n): return bin(n-1).count('1') + 1
print([a(n) for n in range(1, 106)]) # Michael S. Branicky, Dec 16 2021

Formula

a(n) = A000120(n-1) + 1.

a(n) = log(A131136)/log(2). - Stephen Crowley, Aug 25 2008

a(n) = A007814(n) + A000120(n). - Gary W. Adamson, Jun 04 2009

a(n) = A000120(A086799(n)). - Reinhard Zumkeller, Jul 31 2010

a(n) = A000120(A047457(n)-1) = A000120(A047457(n)+1). - Ilya Lopatin, Mar 16 2014

a(n) = A000120(2n-1). - Friedjof Tellkamp, Jan 11 2024