|
%I #57 Apr 13 2022 07:57:02
%S 0,1,3,2,5,4,4,3,7,6,6,5,6,5,5,4,9,8,8,7,8,7,7,6,8,7,7,6,7,6,6,5,11,
%T 10,10,9,10,9,9,8,10,9,9,8,9,8,8,7,10,9,9,8,9,8,8,7,9,8,8,7,8,7,7,6,
%U 13,12,12,11,12,11,11,10,12,11,11,10,11,10,10,9,12,11,11,10,11,10,10,9,11,10
%N Minimal number of steps to get from 1 to n by (a) subtracting 1 or (b) multiplying by 2.
%C Also number of steps to get from n to 1 by process of adding 1 if odd, or dividing by 2 if even.
%C It is straightforward to prove that the number n appears F(n) times in this sequence, where F(n) is the n-th Fibonacci number (A000045). - _Gary Gordon_, May 31 2019
%C Conjecture: a(n)+2 is the sum of the terms of the Hirzebruch (negative) continued fraction for the Stern-Brocot tree fraction A007305(n)/A007306(n). - _Andrey Zabolotskiy_, Apr 17 2020
%H Reinhard Zumkeller, <a href="/A061313/b061313.txt">Table of n, a(n) for n = 1..10000</a>
%H Ralf Stephan, <a href="/somedcgf.html">Some divide-and-conquer sequences ...</a>
%H Ralf Stephan, <a href="/A079944/a079944.ps">Table of generating functions</a>
%H Ralf Stephan, <a href="https://arxiv.org/abs/math/0307027">Divide-and-conquer generating functions. I. Elementary sequences</a>, arXiv:math/0307027 [math.CO], 2003.
%H <a href="/index/Com#complexity">Index to sequences related to the complexity of n</a>
%F a(2n) = a(n)+1; a(2n+1) = a(n+1)+2; a(1) = 0.
%F Is Sum_{k=1..n} a(k) asymptotic to C*n*log(n) where 3 > C > 2? - _Benoit Cloitre_, Aug 31 2002
%F G.f.: x/(1-x) * Sum_{k>=0} (x^2^k + x^2^(k+1)/(1+x^2^k)). - _Ralf Stephan_, Jun 14 2003
%F a(n) = A080791(n-1) + A029837(n). - _Ralf Stephan_, Jun 14 2003
%F a(n) = 2*A023416(n-1) + A000120(n-1) = A023416(A062880(n)) = A023416(A000695(n)) + 1. - _Ralf Stephan_, Jul 16 2003
%F a(n) = A119477(n) - 1. - _Philippe Deléham_, Nov 03 2008
%e a(2) = 1 since 2 = 1*2, a(3) = 3 since 3 = 1*2*2-1, a(11) = 6 since 11 = (1*2*2-1)*2*2-1.
%t f[n_] := Block[{c = 0, m = n}, While[m != 1, If[ EvenQ[m], While[ EvenQ[m], m = m/2; c++ ], m++; c++ ]]; Return[c]]; Table[f[n], {n, 1, 100}]
%o (PARI) a(n)=if(n<2,0,s=n; c=1; while((s+s%2)/(2-s%2)>1,s=(s+s%2)/(2-s%2); c++); c)
%o (PARI) xpcount(n) = { p = 1; for(x=1,n, p1 = x; ct=0; while(p1>1, if(p1%2==0,p1/=2; ct++,p1 = p1*p+1; ct++) ); print1(ct, ", ") ) }
%o (PARI) a(n) = if(n--,2*(logint(n,2)+1)) - hammingweight(n); \\ _Kevin Ryde_, Oct 21 2021
%o (Haskell)
%o a061313 n = fst $ until ((== 1) . snd) (\(u, v) -> (u + 1, f v)) (0, n)
%o where f n = if r == 0 then n' else n + 1 where (n', r) = divMod n 2
%o -- _Reinhard Zumkeller_, Sep 05 2015
%Y Cf. A056792, A006577, A029837, A000045.
%Y Cf. A007305, A007306, A008687.
%K easy,nonn
%O 1,3
%A _Henry Bottomley_, Jun 06 2001
|
