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,3

Links

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.

Example

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

Crossrefs

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

Sequence in context: A099053 A383335 A384384 * A322163 A075167 A253555

Adjacent sequences: A230694 A230695 A230696 * A230698 A230699 A230700

Keyword

nonn,nice

Author

Harry Altman, Oct 27 2013

Status

approved