A360269 Least sum of 2's and 3's required to build n using +, * and parentheses.

2, 3, 4, 5, 5, 7, 6, 6, 7, 8, 7, 10, 9, 8, 8, 10, 8, 11, 9, 10, 10, 12, 9, 10, 11, 9, 11, 11, 10, 13, 10, 11, 12, 12, 10, 14, 12, 13, 11, 15, 12, 14, 12, 11, 14, 13, 11, 14, 12, 13, 13, 15, 11, 13, 13, 14, 13, 16, 12, 16, 14, 13, 12, 15, 13, 15, 14, 15, 14

Offset

2,1

Links

Andrew Howroyd, Table of n, a(n) for n = 2..10000

Index to sequences related to the complexity of n

Example

a(7) = 7 because 7 built by the rules is 2*2+3 or 2+2+3, and in both cases the sum is 7 and there is no other combination with a lesser sum.
a(17) = 10 because 17 = (2+3)*3+2, with 10 being the minimal sum.
a(22) = 10 because 22 = 2*(3*3+2) and these 2's and 3's add up to 10, which is the least possible sum.
a(44) = 12 because 44 = 2*2*(3*3+2), with the least possible sum being 12.

Prog

(PARI) seq(n)=my(a=vector(n)); for(n=1, #a, my(m=if(n==2||n==3, n, oo)); for(k=2, n-2, m=min(m, a[k]+a[n-k])); fordiv(n, d, if(d>1&&d<n, m=min(m, a[d]+a[n/d]))); a[n]=m); a[2..n] \\ Andrew Howroyd, Jan 31 2023

Crossrefs

Cf. A000040, A025280.

Sequence in context: A112264 A118503 A086295 * A345423 A159303 A262049

Adjacent sequences: A360266 A360267 A360268 * A360270 A360271 A360272

Keyword

nonn

Author

Tamas Sandor Nagy, Jan 31 2023

Extensions

Terms a(46) and beyond from Andrew Howroyd, Feb 01 2023

Status

approved