A307616 - OEIS

%I #33 Aug 23 2019 00:21:14

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

%T 12,12,12,12,12,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,

%U 60,60,60,120,120,120,120,120,120,120,360,360,360,360,360,360,360

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

%C Conjecture: For n >= 20, a(n) = a(n-1)*A284600(a(n-1)/gcd(a(n-1),n)). - _Charlie Neder_, Jun 10 2019

%H ACM ICPC World Finals 2019, <a href="http://www.csc.kth.se/~austrin/icpc/finals2019solutions.pdf">Problem K: Traffic Blights</a> (see p. 8, using n=100 and n=200 as examples).

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

%t Map[A307616,Range[100]]

%o (PARI) ispp(k) = (k==1) || isprimepower(k);

%o isok(k, n) = {for (i=1, n, if (! ispp(i/gcd(i, k)), return (0); )); return (1); }

%o a(n) = my(k=1); while (! isok(k,n), k++); k; \\ _Michel Marcus_, Jun 11 2019

%Y Cf. A284600.

%K nonn

%O 1,6

%A _Jack Zhang_, Apr 18 2019