|
|
A056792
|
|
Minimal number of steps to get from 0 to n by (a) adding 1 or (b) multiplying by 2.
|
|
20
|
|
|
0, 1, 2, 3, 3, 4, 4, 5, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8, 6, 7, 7, 8, 7, 8, 8, 9, 6, 7, 7, 8, 7, 8, 8, 9, 7, 8, 8, 9, 8, 9, 9, 10, 7, 8, 8, 9, 8, 9, 9, 10, 8, 9, 9, 10, 9, 10, 10, 11, 7, 8, 8, 9, 8, 9, 9, 10, 8, 9, 9, 10, 9, 10, 10, 11, 8, 9, 9, 10, 9, 10, 10, 11, 9, 10, 10, 11, 10, 11
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
A stopping problem: begin with n and at each stage if even divide by 2 or if odd subtract 1. That is, iterate A029578 while nonzero.
The number of appearances of n in this sequence is identically A000045(n). Proof:
By application of the formula,
"a(0) = 0, a(2n+1) = a(2n) + 1 and a(2n) = a(n) + 1",
it can be seen that:
{i: a(i) = n} = {2*i: a(i) = n-1, n>0} U {2*i+1: a(i)=n-2, n>1}.
Because the two sets on the left hand side share no elements:
|{i: a(i) = n}| = |{i: a(i) = n-1, n>0}| + |{i: a(i) = n-2, n>1}|
Notice that
|{i : a(i) = 1}| = |{1}| = 1 = A000045(1) and
|{i : a(i) = 2}| = |{2}| = 1 = A000045(2).
Therefore the number of appearances of n in this sequence is A000045(n).
(End)
|
|
LINKS
|
|
|
FORMULA
|
a(0) = 0, a(2n+1) = a(2n) + 1 and a(2n) = a(n) + 1.
a(n) = (weight of binary expansion of n) + (length of binary expansion of n) - 1.
|
|
EXAMPLE
|
12 = 1100 in binary, so a(12)=2+4-1=5.
|
|
MAPLE
|
a:= n-> (l-> nops(l)+add(i, i=l)-1)(convert(n, base, 2)):
|
|
MATHEMATICA
|
f[ n_Integer ] := (c = 0; k = n; While[ k != 0, If[ EvenQ[ k ], k /= 2, k-- ]; c++ ]; c); Table[ f[ n ], {n, 0, 100} ]
f[n_] := Floor@ Log2@ n + DigitCount[n, 2, 1]; Array[f, 100] (* Robert G. Wilson v, Jul 31 2012 *)
|
|
PROG
|
(PARI) a(n)=if(n<1, 0, n-valuation(n!*sum(i=1, n, 1/i), 2))
(PARI) a(n)=if(n<1, 0, 1+a(if(n%2, n-1, n/2)))
(Haskell)
c i = if i `mod` 2 == 0 then i `div` 2 else i - 1
b 0 foldCount = foldCount
b sheetCount foldCount = b (c sheetCount) (foldCount + 1)
|
|
CROSSREFS
|
Analogous sequences with a different multiplier k: A061282 (k=3), A260112 (k=4).
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|