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

Author

Jack Zhang, Apr 18 2019

Keywords

• nonn

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

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

Crossrefs

Cf. A284600.

Programs

Mathematica

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

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