A008057 Smallest sum of an addition chain for 2n+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, 237, 241, 245
Offset: 0
Examples
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.
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.
- Index to sequences related to the complexity of n
Programs
-
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)
Formula
a(n) = A376449(2*n+1) + 2*n. - Pontus von Brömssen, Apr 22 2025
Extensions
a(30)-a(46) from Sean A. Irvine, Mar 08 2018
a(47)-a(49) (using A376449 b-file) from Pontus von Brömssen, Apr 22 2025