|
%I #67 May 31 2019 19:17:21
%S 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,
%T 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,
%U 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
%N Minimal number of steps to get from 0 to n by (a) adding 1 or (b) multiplying by 2.
%C 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.
%C From _Peter Kagey_, Jul 16 2015: (Start)
%C The number of appearances of n in this sequence is identically A000045(n). Proof:
%C By application of the formula,
%C "a(0) = 0, a(2n+1) = a(2n) + 1 and a(2n) = a(n) + 1",
%C it can be seen that:
%C {i: a(i) = n} = {2*i: a(i) = n-1, n>0} U {2*i+1: a(i)=n-2, n>1}.
%C Because the two sets on the left hand side share no elements:
%C |{i: a(i) = n}| = |{i: a(i) = n-1, n>0}| + |{i: a(i) = n-2, n>1}|
%C Notice that
%C |{i : a(i) = 1}| = |{1}| = 1 = A000045(1) and
%C |{i : a(i) = 2}| = |{2}| = 1 = A000045(2).
%C Therefore the number of appearances of n in this sequence is A000045(n).
%C (End)
%H Charles R Greathouse IV, <a href="/A056792/b056792.txt">Table of n, a(n) for n = 0..10000</a>
%H Hugo Pfoertner, <a href="/A003313/a003313.txt">Addition chains</a>
%H <a href="/index/Com#complexity">Index to sequences related to the complexity of n</a>
%F a(0) = 0, a(2n+1) = a(2n) + 1 and a(2n) = a(n) + 1.
%F a(n) = n-valuation(A000254(n), 2) for n>0. - _Benoit Cloitre_, Mar 09 2004
%F a(n) = A000120(n) + A070939(n) - 1. - _Michel Marcus_, Jul 17 2015
%F a(n) = (weight of binary expansion of n) + (length of binary expansion of n) - 1.
%e 12 = 1100 in binary, so a(12)=2+4-1=5.
%p a:= n-> (l-> nops(l)+add(i, i=l)-1)(convert(n, base, 2)):
%p seq(a(n), n=0..105); # _Alois P. Heinz_, Jul 16 2015
%t f[ n_Integer ] := (c = 0; k = n; While[ k != 0, If[ EvenQ[ k ], k /= 2, k-- ]; c++ ]; c); Table[ f[ n ], {n, 0, 100} ]
%t f[n_] := Floor@ Log2@ n + DigitCount[n, 2, 1]; Array[f, 100] (* _Robert G. Wilson v_, Jul 31 2012 *)
%o (PARI) a(n)=if(n<1,0,n-valuation(n!*sum(i=1,n,1/i),2))
%o (PARI) a(n)=if(n<1,0,1+a(if(n%2,n-1,n/2)))
%o (PARI) a(n)=n=binary(n);sum(i=1,#n,n[i])+#n-1 \\ _Charles R Greathouse IV_, Apr 11 2012
%o (Haskell)
%o c i = if i `mod` 2 == 0 then i `div` 2 else i - 1
%o b 0 foldCount = foldCount
%o b sheetCount foldCount = b (c sheetCount) (foldCount + 1)
%o a056792 n = b n 0 -- _Peter Kagey_, Sep 02 2015
%Y Equals A056791 - 1. The least inverse (indices of record values) of A056792 is A052955 prepended with 0. See also A014701, A115954, A056796, A056817.
%Y Cf. A000120, A070939, A007088: base 2 sequences.
%Y Analogous sequences with a different multiplier k: A061282 (k=3), A260112 (k=4).
%K nonn,easy
%O 0,3
%A _N. J. A. Sloane_, Sep 01 2000
%E More terms from _James A. Sellers_, Sep 06 2000
%E More terms from _David W. Wilson_, Sep 07 2000
|
