|
%I #24 Jun 20 2022 04:46:43
%S 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,
%T 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,
%U 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
%N The least cost to reach n using additions and multiplications, where multiplication is free.
%C 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.
%C 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.
%H Stan Wagon, <a href="/A354914/b354914.txt">Table of n, a(n) for n = 1..5000</a>
%H H. M. Bahig, <a href="http://dx.doi.org/10.1016/j.disc.2007.04.015">On a generalization of addition chains: Addition-multiplication chains</a>, Discrete Mathematics 308 (2008), 611-616.
%H Stan Wagon, <a href="/A354914/a354914.txt">Optimal paths for n up to 100</a>
%e For n = 23, the least cost a(23) is 4, via the sequence 1, 2, 3, 4, 8, 16, 19, 23.
%Y Cf. A355015, A230697.
%K nonn,hard
%O 1,3
%A _Stan Wagon_, Jun 11 2022
|
