A354914 The least cost to reach n using additions and multiplications, where multiplication is free.

0, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 3, 1, 2, 2, 3, 2, 3, 3, 4, 2, 2, 3, 2, 3, 3, 3, 3, 1, 2, 2, 3, 2, 3, 3, 3, 2, 3, 3, 3, 3, 3, 4, 4, 2, 3, 2, 3, 3, 4, 2, 3, 3, 3, 3, 3, 3, 4, 3, 3, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 3, 3, 4, 3, 4, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 3, 4, 4, 2, 3, 3, 3, 2

Offset

1,3

Comments

Start with 1. Apply multiplication or addition to any values (not necessarily distinct) already attained to get a finite sequence of integers ending in n. The cost of addition is one unit, but multiplication is free. Then a(n) is the cost of the least expensive path to n.

The problem is folklore. It is not hard to prove that the cost function is unbounded. The values given were produced by Joseph DeVincentis, Stan Wagon, and Al Zimmermann.

Links

Stan Wagon, Table of n, a(n) for n = 1..5000

H. M. Bahig, On a generalization of addition chains: Addition-multiplication chains, Discrete Mathematics 308 (2008), 611-616.

Stan Wagon, Optimal paths for n up to 100

Example

For n = 23, the least cost a(23) is 4, via the sequence 1, 2, 3, 4, 8, 16, 19, 23.

Crossrefs

Cf. A355015, A230697.

Sequence in context: A072086 A180094 A333870 * A366927 A103748 A104231

Adjacent sequences: A354911 A354912 A354913 * A354915 A354916 A354917

Keyword

nonn,hard

Author

Stan Wagon, Jun 11 2022

Status

approved