login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A008057 Smallest sum of an addition chain for 2n+1. 1
0, 5, 10, 16, 20, 27, 31, 35, 40, 47, 51, 56, 60, 65, 74, 78, 80, 86, 92, 96, 102, 106, 110, 120, 121, 125, 134, 137, 142, 148, 153, 156, 160, 167, 171, 182, 184, 185, 192, 201, 200, 206, 210, 219, 227, 231, 233 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,2
LINKS
H. Zantema, Minimizing sums of addition chains, RUU-CS-89-15 (1989).
H. Zantema, Minimizing sums of addition chains, J. Algorithms 12 (1991) 281-307.
EXAMPLE
The smallest chain for 5 is 2, 3, 5 with sum a(2) = 2+3+5 = 10.
the smallest chain for 7 is 2, 3, 4, 7 with sum a(3) = 2+3+4+7 = 16.
PROG
(PARI) step(V)=my(U=List(), v); for(i=1, #V, v=V[i]; for(i=1, #v, for(j=i, #v, if(v[i]+v[j]>v[#v], listput(U, concat(v, v[i]+v[j])))))); vecsort(Vec(U), , 8)
sm(v)=sum(i=2, #v, v[i])
a(n)=if(n<2, return(5*n)); n=2*n+1; my(V=[[1, 2]], U, t); while(#(U=select(v->v[#v]==n, V))==0, V=select(v->v[#v]<=n, step(V))); t=vecmin(apply(sm, U)); while(#V, V=step(select(v->sm(v)<t-n, V)); for(i=1, #V, my(v=V[i]); if(v[#v]==n, t=min(sm(v), t)))); t \\ Charles R Greathouse IV, Jul 17 2013
CROSSREFS
Sequence in context: A313842 A313843 A313844 * A313845 A313846 A313847
KEYWORD
nonn,nice,more
AUTHOR
N. J. A. Sloane, Aug 07 2003
EXTENSIONS
a(30)-a(46) from Sean A. Irvine, Mar 08 2018
STATUS
approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 1 08:00 EST 2024. Contains 370430 sequences. (Running on oeis4.)