A376615 a(n) is the number of iterations that n requires to reach a noninteger under the map x -> x / wt(x), where wt(k) is the binary weight of k (A000120); a(n) = 0 if n is a power of 2.

0, 0, 1, 0, 1, 2, 1, 0, 1, 2, 1, 3, 1, 1, 1, 0, 1, 2, 1, 3, 2, 1, 1, 4, 1, 1, 1, 1, 1, 1, 1, 0, 1, 2, 1, 3, 1, 1, 1, 4, 1, 2, 1, 1, 1, 1, 1, 5, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 0, 1, 2, 1, 3, 2, 1, 1, 4, 1, 1, 1, 1, 1, 1, 1, 5, 2, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1

Offset: 1

Author

Amiram Eldar, Sep 30 2024

Keywords

• nonn
• easy
• base

Comments

The powers of 2 are fixed points of the map, since wt(2^k) = 1 for all k >= 0. Therefore they are arbitrarily assigned the value a(2^k) = 0.

Each number n starts a chain of a(n) integers: n, n/wt(n), (n/wt(n))/wt(n/wt(n)), ..., of them the first a(n)-1 integers are binary Niven numbers (A049445).

Examples

			a(6) = 2 since 6/wt(6) = 3 and 3/wt(3) = 3/2 is a noninteger that is reached after 2 iterations.
a(20) = 3 since 20/wt(20) = 10, 10/wt(10) = 5 and 5/wt(5) = 5/2 is a noninteger that is reached after 3 iterations.
		

Links

• Amiram Eldar, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A000005, A000079, A000120, A049445, A065878, A376616, A376617, A376619.

Programs

Mathematica

a[n_] := a[n] = Module[{bw = DigitCount[n, 2, 1]}, If[bw == 1, 0, If[!Divisible[n, bw], 1, 1 + a[n/bw]]]]; Array[a, 100]

PARI

a(n) = {my(w = hammingweight(n)); if(w == 1, 0, if(n % w, 1, 1 + a(n/w)));}

Formula

a(n) = 0 if and only if n is in A000079 (by definition).

a(n) = 1 if and only if n is in A065878.

a(n) >= 2 if and only if n is in A049445 \ A000079 (i.e., n is a binary Niven number that is not a power of 2).

a(n) >= 3 if and only if n is in A376616 \ A000079.

a(n) >= 4 if and only if n is in A376617 \ A000079.

a(2*n) >= a(n).

a(3*2^n) = n+1 for n >= 0.

a(n) < A000005(n).