cp's OEIS Frontend

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.

%I A307616 #33 Aug 23 2019 00:21:14
%S A307616 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 A307616 12,12,12,12,12,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,
%U A307616 60,60,60,120,120,120,120,120,120,120,360,360,360,360,360,360,360
%N 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.
%C A307616 Conjecture: For n >= 20, a(n) = a(n-1)*A284600(a(n-1)/gcd(a(n-1),n)). - _Charlie Neder_, Jun 10 2019
%H A307616 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 A307616[x_]:=(For[i=1,Length[Select[PrimeNu[Range[x]/GCD[Range[x],i]],#>1&]]>0,i++];i)
%t A307616 Map[A307616,Range[100]]
%o A307616 (PARI) ispp(k) = (k==1) || isprimepower(k);
%o A307616 isok(k, n) = {for (i=1, n, if (! ispp(i/gcd(i, k)), return (0); )); return (1); }
%o A307616 a(n) = my(k=1); while (! isok(k,n), k++); k; \\ _Michel Marcus_, Jun 11 2019
%Y A307616 Cf. A284600.
%K A307616 nonn
%O A307616 1,6
%A A307616 _Jack Zhang_, Apr 18 2019