login
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.
6
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,6
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).
LINKS
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).
EXAMPLE
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.
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]
PROG
(PARI) a(n) = {my(w = hammingweight(n)); if(w == 1, 0, if(n % w, 1, 1 + a(n/w))); }
KEYWORD
nonn,easy,base
AUTHOR
Amiram Eldar, Sep 30 2024
STATUS
approved