|
Search: id:A061313
|
|
|
| A061313 |
|
Minimal number of steps to get from 1 to n by (a) subtracting 1 or (b) multiplying by 2. |
|
+0
4
|
|
| 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
(list; graph; listen)
|
|
|
OFFSET
|
1,3
|
|
|
COMMENT
|
Also number of steps to get from n to 1 by process of adding 1 if odd, or dividing by 2 if even.
a(n) = 2*A023416(n-1) + A000120(n-1) = A023416(A062880(n)) = A023416(A000695(n)) + 1. - Ralf Stephan (ralf(AT)ark.in-berlin.de), Jul 16 2003
|
|
LINKS
|
R. Stephan, Some divide-and-conquer sequences ...
R. Stephan, Table of generating functions
R. Stephan, Divide-and-conquer generating functions. I. Elementary sequences
|
|
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 (benoit7848c(AT)orange.fr), Aug 31 2002
G.f.: x/(1-x) * sum(k>=0, x^2^k + x^2^(k+1)/(1+x^2^k)). a(n) = A080791(n-1) + A029837(n). - Ralf Stephan (ralf(AT)ark.in-berlin.de), Jun 14 2003
a(n)=A119477(n)-1 . [From Philippe DELEHAM (kolotoko(AT)wanadoo.fr), Nov 03 2008]
|
|
EXAMPLE
|
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.
|
|
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}]
|
|
PROGRAM
|
(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) (Set p=1, then:) xpcount(n, p) = { 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" ") ) }
|
|
CROSSREFS
|
Cf. A056792, A006577, A029837.
Sequence in context: A128076 A076243 A140061 this_sequence A087669 A053087 A062327
Adjacent sequences: A061310 A061311 A061312 this_sequence A061314 A061315 A061316
|
|
KEYWORD
|
easy,nonn
|
|
AUTHOR
|
Henry Bottomley (se16(AT)btinternet.com), Jun 06 2001
|
|
|
Search completed in 0.002 seconds
|
