A384483 Length of shortest addition-composition chain for n, starting with 1 and x.

0, 1, 2, 2, 3, 3, 4, 3, 4, 4, 5, 4, 5, 5, 5, 4, 5, 5, 6, 5, 5, 5, 6, 5, 5, 5, 5, 6, 6, 6, 5, 5, 6, 6, 6, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 5, 6, 6, 6, 6, 6, 7, 6, 6, 6, 6, 6, 6, 7, 6, 7, 6, 5, 6, 6, 6, 6, 6, 7

Offset

1,3

Comments

See A384480 for the definition of addition-composition chains. The number n is identified with the constant function f(x) = n.

Links

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

Formula

a(n) <= A003313(n).

a(n) <= a(n-1) + 1.

Example

The smallest n for which a(n) < A003313(n) is n = 21. The length of a shortest addition chain for 21 is A003313(21) = 6, but there are addition-composition chains of length 5, for example (1, x,) x+1, 2*x+2, 3*x+3, 6, 21. 6 and 21 are the compositions of 3*x+3 with 1 and 6, respectively.

Crossrefs

Row 0 of A384480 for columns k >= 1.

Cf. A003313 (addition only), A230697 (addition and multiplication), A384384 (addition, multiplication, and composition), A384484, A384485.

Sequence in context: A259847 A259103 A334200 * A128998 A137813 A003313

Adjacent sequences: A384480 A384481 A384482 * A384484 A384485 A384486

Keyword

nonn

Author

Pontus von Brömssen, Jun 02 2025

Status

approved