A061313 Minimal number of steps to get from 1 to n by (a) subtracting 1 or (b) multiplying by 2.

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, 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, 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

Offset: 1

Author

Henry Bottomley, Jun 06 2001

Keywords

• easy
• nonn

Comments

Also number of steps to get from n to 1 by process of adding 1 if odd, or dividing by 2 if even.

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

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

Examples

			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.
		

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
• Ralf Stephan, Some divide-and-conquer sequences ...
• Ralf Stephan, Table of generating functions
• Ralf Stephan, Divide-and-conquer generating functions. I. Elementary sequences, arXiv:math/0307027 [math.CO], 2003.
• Index to sequences related to the complexity of n

Crossrefs

Cf. A056792, A006577, A029837, A000045.

Cf. A007305, A007306, A008687.

Programs

Haskell

a061313 n = fst $ until ((== 1) . snd) (\(u, v) -> (u + 1, f v)) (0, n)
   where f n = if r == 0 then n' else n + 1  where (n', r) = divMod n 2
-- Reinhard Zumkeller, Sep 05 2015

Mathematica

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}]

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)

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, ", ") ) }

PARI

a(n) = if(n--,2*(logint(n,2)+1)) - hammingweight(n); \\ Kevin Ryde, Oct 21 2021

Formula

a(2n) = a(n)+1; a(2n+1) = a(n+1)+2; a(1) = 0.

Is Sum_{k=1..n} a(k) asymptotic to C*n*log(n) where 3 > C > 2? - Benoit Cloitre, Aug 31 2002

G.f.: x/(1-x) * Sum_{k>=0} (x^2^k + x^2^(k+1)/(1+x^2^k)). - Ralf Stephan, Jun 14 2003

a(n) = A080791(n-1) + A029837(n). - Ralf Stephan, Jun 14 2003

a(n) = 2*A023416(n-1) + A000120(n-1) = A023416(A062880(n)) = A023416(A000695(n)) + 1. - Ralf Stephan, Jul 16 2003

a(n) = A119477(n) - 1. - Philippe Deléham, Nov 03 2008