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