login
A333354
Minimum cost of path that starts at 1 and visits integers from 1 to n, inclusive, each at least once, where the cost to travel from a to b is LCM(a, b).
0
0, 2, 7, 12, 21, 28, 40, 51, 65, 79, 100, 114, 138, 158, 182, 205, 238, 259, 295, 324, 358, 390, 435, 463, 511, 549, 593, 634
OFFSET
1,2
LINKS
A. Catanzaro, J. Feldman, M. Higgins, B. Kimball, H. Kirk, A. C Maravelias, and D. Sinha, LCM Optimal Paths, Girls' Angle Bulletin, Vol. 13, No. 4 (2020), 13-19.
EXAMPLE
For n = 3, the optimal path is 1, 2, 1, 3, which has cost 2 + 2 + 3 = 7.
For n = 4, the optimal path is 1, 3, 1, 2, 4, which has cost 3 + 3 + 2 + 4 = 12.
For n = 7, there are multiple optimal paths of which 1, 3, 6, 2, 4, 1, 5, 1, 7 is one and has cost 3 + 6 + 6 + 4 + 4 + 5 + 5 + 7 = 40.
For n = 20, an optimal path is 1, 11, 1, 13, 1, 17, 1, 19, 1, 7, 14, 2, 16, 8, 4, 12, 6, 18, 9, 3, 15, 5, 10, 20.
CROSSREFS
Sequence in context: A023669 A137401 A309150 * A119713 A213041 A293330
KEYWORD
nonn,hard,more
AUTHOR
Richard S. Chang, May 04 2020
EXTENSIONS
a(21)-a(28) from Bert Dobbelaere, Aug 22 2020
STATUS
approved