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

Table of n, a(n) for n=1..28.

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

Adjacent sequences: A333351 A333352 A333353 * A333355 A333356 A333357

Keyword

nonn,hard,more

Author

Richard S. Chang, May 04 2020

Extensions

a(21)-a(28) from Bert Dobbelaere, Aug 22 2020

Status

approved