cp's OEIS Frontend

A056792 Minimal number of steps to get from 0 to n by (a) adding 1 or (b) multiplying by 2.

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