login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

Table of n, a(n) for n=1..105.

Index to sequences related to the complexity of n

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

Cf. A003313, A117497, A064097.

Sequence in context: A003313 A277608 A117497 * A064097 A014701 A207034

Adjacent sequences:  A117495 A117496 A117497 * A117499 A117500 A117501

KEYWORD

nonn

AUTHOR

Franklin T. Adams-Watters, Mar 22 2006

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 19 18:20 EDT 2019. Contains 322283 sequences. (Running on oeis4.)