A333354 - OEIS

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).

%I #41 Aug 22 2020 11:33:23

%S 0,2,7,12,21,28,40,51,65,79,100,114,138,158,182,205,238,259,295,324,

%T 358,390,435,463,511,549,593,634

%N 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).

%H A. Catanzaro, J. Feldman, M. Higgins, B. Kimball, H. Kirk, A. C Maravelias, and D. Sinha, <a href="http://girlsangle.org/page/bulletin-archive/GABv13n04E.pdf">LCM Optimal Paths</a>, Girls' Angle Bulletin, Vol. 13, No. 4 (2020), 13-19.

%e For n = 3, the optimal path is 1, 2, 1, 3, which has cost 2 + 2 + 3 = 7.

%e For n = 4, the optimal path is 1, 3, 1, 2, 4, which has cost 3 + 3 + 2 + 4 = 12.

%e 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.

%e 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.

%K nonn,hard,more

%O 1,2

%A _Richard S. Chang_, May 04 2020

%E a(21)-a(28) from _Bert Dobbelaere_, Aug 22 2020