|
Search: id:A117497
|
|
|
| A117497 |
|
Length of shortest sequence b with b(0) = 1, b(i+1) = b(i)+d where d|b(i), and b(k) = n. |
|
+0
4
|
|
| 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, 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, 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
(list; graph; listen)
|
|
|
OFFSET
|
1,3
|
|
|
COMMENT
|
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.
|
|
FORMULA
|
a(1)=0, a(n) = 1 + min_{d|n, d<n} a(n-d).
|
|
EXAMPLE
|
The sequence 1,2,4,8,16,32,64,128,132,143 gets 143 in 9 steps, so a(143) = 9.
|
|
CROSSREFS
|
Cf. A003313, A117498.
Sequence in context: A128998 A137813 A003313 this_sequence A117498 A064097 A014701
Adjacent sequences: A117494 A117495 A117496 this_sequence A117498 A117499 A117500
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Frank Adams-Watters (FrankTAW(AT)Netscape.net), Mar 22 2006
|
|
|
Search completed in 0.002 seconds
|
