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

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

Offset

1,3

Comments

See A384383 for the definition of addition-multiplication-composition chains. The number n is identified with the constant polynomial p(x) = n.

Links

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

Formula

a(n) <= A230697(n).

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

Example

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

Crossrefs

Cf. A230697 (addition and multiplication), A384383, A384385, A384386, A384483 (addition and composition).

Sequence in context: A173419 A099053 A383335 * A230697 A322163 A075167

Adjacent sequences: A384381 A384382 A384383 * A384385 A384386 A384387

Keyword

nonn

Author

Pontus von Brömssen, Jun 01 2025

Status

approved