A307616 a(n) is the smallest k with the property that i / gcd(i, k) is a prime power (or 1) for i = 1..n.

1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 4, 4, 4, 6, 6, 6, 6, 6, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 120, 120, 120, 120, 120, 120, 120, 360, 360, 360, 360, 360, 360, 360

Offset

1,6

Comments

Conjecture: For n >= 20, a(n) = a(n-1)*A284600(a(n-1)/gcd(a(n-1),n)). - Charlie Neder, Jun 10 2019

Links

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

ACM ICPC World Finals 2019, Problem K: Traffic Blights (see p. 8, using n=100 and n=200 as examples).

Mathematica

A307616[x_]:=(For[i=1, Length[Select[PrimeNu[Range[x]/GCD[Range[x], i]], #>1&]]>0, i++]; i)
Map[A307616, Range[100]]

Prog

(PARI) ispp(k) = (k==1) || isprimepower(k);
isok(k, n) = {for (i=1, n, if (! ispp(i/gcd(i, k)), return (0); )); return (1); }
a(n) = my(k=1); while (! isok(k, n), k++); k; \\ Michel Marcus, Jun 11 2019

Crossrefs

Cf. A284600.

Sequence in context: A172008 A100825 A216452 * A202709 A279611 A008767

Adjacent sequences: A307613 A307614 A307615 * A307617 A307618 A307619

Keyword

nonn

Author

Jack Zhang, Apr 18 2019

Status

approved