|
|
A117498
|
|
Optimal combination of binary and factor methods for finding an addition chain.
|
|
1
|
|
|
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, 9, 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;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
COMMENTS
|
This is an upper bound for both addition chains (A003313) and A117497. The first few values where A003313 is smaller are 23,43,46,47,59. The first few values where A117497 is smaller are 77,143,154,172,173. The first few values where both are smaller are 77,154,172,173,203.
|
|
LINKS
|
|
|
FORMULA
|
a(1)=0; a(n) = min(a(n-1)+1, min_{d|n, 1<d<n} a(d)+a(n/d)). If n is prime, this reduces to a(n) = a(n-1)+1.
|
|
EXAMPLE
|
a(33)=6 because 6 = 1+a(32) < a(3)+a(11) = 2+5. a(36) = min(a(35)+1, a(2)+a(18), a(3)+a(12), a(4)+a(9), a(6)+a(6)) = min(1+7, 1+5, 2+4, 2+4, 3+3) = 6.
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|