This site is supported by donations to The OEIS Foundation.



Invitation: celebrating 50 years of OEIS, 250000 sequences, and Sloane's 75th, there will be a conference at DIMACS, Rutgers, Oct 9-10 2014.

(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A117497 Length of shortest sequence b with b(0) = 1, b(i+1) = b(i)+d where d|b(i) and b(k) = n. 3


%S 0,1,2,2,3,3,4,3,4,4,5,4,5,5,5,4,5,5,6,5,6,6,7,5,6,6,6,6,7,6,7,5,6,6,

%T 7,6,7,7,7,6,7,7,8,7,7,8,9,6,7,7,7,7,8,7,8,7,8,8,9,7,8,8,8,6,7,7,8,7,

%U 8,8,9,7,8,8,8,8,8,8,9,7,8,8,9,8,8,9,9,8,9,8,9,9,9,10,9,7,8,8,8,8,9,8,9,8,9

%N Length of shortest sequence b with b(0) = 1, b(i+1) = b(i)+d where d|b(i) and b(k) = n.

%C This is similar to the shortest addition chain for n. Both the binary method and the divisor method for finding an addition chain will find a sequence of this type. The smallest few n where there is an addition chain shorter than this sequence are 23,43,46,47,59. The first few n where this sequence is smaller than the shortest addition chain are 143,267,275,286,407. The smallest few n such that a(n) = a(2n) are 86,213,285,342,383.

%H <a href="/index/Com#complexity">Index to sequences related to the complexity of n</a>

%F a(1)=0, a(n) = 1 + min_{d|n, d<n} a(n-d).

%e The sequence 1,2,4,8,16,32,64,128,132,143 gets 143 in 9 steps, so a(143) = 9.

%Y Cf. A003313, A117498.

%K nonn

%O 1,3

%A _Franklin T. Adams-Watters_, Mar 22 2006

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified September 30 16:10 EDT 2014. Contains 247460 sequences.