A383002 -id:A383002 - cp's OEIS frontend

A230697 Length of shortest addition-multiplication chain for n.

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, 6, 4, 5, 5, 5, 4, 5, 5, 5, 5, 6, 5, 6, 6, 5, 6, 6, 5, 5, 5, 6, 6, 6, 5, 6, 6, 6, 6, 7, 5, 6, 6, 6, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 5, 6, 6, 6, 7, 5, 4, 5, 5, 5, 6, 6, 6, 6

Offset: 1

Harry Altman, Oct 27 2013

			A shortest addition-multiplication chain for 16 is (1,2,4,16), of length a(16) = 3.
A shortest addition-multiplication chain for 281 is (1,2,4,5,16,25,256,281), of length a(281) = 7. This is the first case where not all terms in some shortest chain are the sum or product of the immediately preceding term and one more preceding term. In other words, 281 is the smallest of the analog of non-Brauer numbers (A349044) for addition-multiplication chains. The next ones are 913, 941, 996, 997, 998, 1012, 1077, 1079, 1542, 1572, 1575, 1589, 1706, 1792, 1795, 1816, 1864, ... . - _Pontus von Brömssen_, May 02 2025

Jinyuan Wang, Table of n, a(n) for n = 1..10000
H. M. Bahig, On a generalization of addition chains: Addition-multiplication chains, Discrete Mathematics 308 (2008), 611-616.
Gleb Ivanov, Python program.

Cf. A003313, A005245, A128998, A173419, A349044, A354914, A383001, A383002.

A383001 Smallest number with shortest addition-multiplication chain of length n.

Original entry on oeis.org

1, 2, 3, 5, 7, 13, 23, 59, 211, 619, 4282, 25819

Offset: 0

Pontus von Brömssen, Apr 12 2025

Indices of records in A230697.

Cf. A003064, A230697, A383002.

A230697(a(n)) = n.

A384386 Number of integers with a shortest addition-multiplication-composition chain of length n, starting with 1 and x, i.e., number of integers k with A384384(k) = n.

Original entry on oeis.org

1, 1, 2, 5, 16, 82, 907

Offset: 0

Pontus von Brömssen, Jun 01 2025

See A384383 and A384384 for details.

Cf. A383002 (addition and multiplication), A384383, A384384, A384385, A384485 (addition and composition).

A384485 Number of integers with a shortest addition-composition chain of length n, starting with 1 and x, i.e., number of integers k with A384483(k) = n.

Original entry on oeis.org

1, 1, 2, 3, 5, 20, 104, 700, 6779, 95596

Offset: 0

Pontus von Brömssen, Jun 02 2025

See A384480 and A384483 for details.

Cf. A003065 (addition only), A383002 (addition and multiplication), A384386 (addition, multiplication, and composition), A384480, A384482, A384483, A384484.

A383143 Number of positive integers with a shortest addition-subtraction chain of length n.

Original entry on oeis.org

1, 1, 2, 3, 5, 9, 16, 28, 49, 88, 156, 280, 499, 904, 1639, 2986, 5442, 9936, 18134

Offset: 0

Jinyuan Wang, Apr 17 2025

			a(6) = 16 because the number of occurrences of 6 in A128998 is 16. These numbers are 19, 21, 22, 23, 25, 26, 27, 28, 30, 31, 33, 34, 36, 40, 48, 64.

Neill Clift, Addition Subtraction Chains.
Index to sequences related to the complexity of n

Cf. A003065, A128998, A383002, A383142.

a(n) >= A003065(n).

A383337 Number of integers with a shortest addition-multiplication-exponentiation chain of length n.

Original entry on oeis.org

1, 1, 2, 7, 45, 485

Offset: 0

Pontus von Brömssen, Apr 27 2025

			Only 1 has an addition-multiplication-exponentiation chain of length 0, so a(0) = 1.
Only 2 has a shortest chain of length 1, so a(1) = 1.
3 and 4 have shortest chains of length 2, so a(2) = 2.
5, 6, 8, 9, 16, 27, and 256 have shortest chains of length 3, so a(3) = 7.

Cf. A003065, A383002, A383143, A383335, A383336.

A384382 Number of polynomials with a shortest addition-multiplication chain of length n, starting with 1 and x.

Original entry on oeis.org

2, 4, 14, 62, 350, 2517, 22918, 259325

Offset: 0

Pontus von Brömssen, Jun 01 2025

An addition-multiplication chain for the polynomial p(x) is a finite sequence of polynomials, starting with 1, x and ending with p(x), in which each element except 1 and x equals q(x)+r(x) or q(x)*r(x) for two preceding, not necessarily distinct, elements q(x) and r(x) in the chain. The length of the chain is the number of elements in the chain, excluding 1 and x.

			a(0) = 2 because 1 and x are considered to have chains of length 0.
a(1) = 4 because the 4 polynomials 2, x+1, 2*x, and x^2 have chains of length 1.
a(2) = 14 because the 14 polynomials 3, 4, x+2, 2*x+1, 2*x+2, 3*x, 4*x, x^2+1, x^2+x, x^2+2*x+1, 2*x^2, 4*x^2, x^3, and x^4 have chains of length 2.

Cf. A382928, A383002, A383331 (addition only), A384383 (addition, multiplication, and composition), A384482 (addition and composition).

cp's OEIS Frontend

A230697 Length of shortest addition-multiplication chain for n.

Views

Author

Keywords

Examples

Links

Crossrefs

A383001 Smallest number with shortest addition-multiplication chain of length n.

Views

Author

Keywords

Comments

Crossrefs

Formula

A384386 Number of integers with a shortest addition-multiplication-composition chain of length n, starting with 1 and x, i.e., number of integers k with A384384(k) = n.

Views

Author

Keywords

Comments

Crossrefs

A384485 Number of integers with a shortest addition-composition chain of length n, starting with 1 and x, i.e., number of integers k with A384483(k) = n.

Views

Author

Keywords

Comments

Crossrefs

A383143 Number of positive integers with a shortest addition-subtraction chain of length n.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A383337 Number of integers with a shortest addition-multiplication-exponentiation chain of length n.

Views

Author

Keywords

Examples

Crossrefs

A384382 Number of polynomials with a shortest addition-multiplication chain of length n, starting with 1 and x.

Views

Author

Keywords

Comments

Examples

Crossrefs