%I #20 Aug 10 2017 11:11:34
%S 0,0,1,1,1,1,2,1,1,1,2,1,2,1,2,2,2,1,2,1,2,2,2,1,2,2,2,2,2,1,3,2,2,2,
%T 2,2,3,2,2,2,3,1,3,2,2,2,3,2,3,2,2,2,3,2,3,2,2,2,3,1,3,2,2,2,3,2,3,2,
%U 2,2,3,2,3,2,2,2,3,2,3,2,3,2,3,2,3,2,3,2,3,2,3,2,3,2,3,2,3,2,3,2,3,2,3,2,2
%N Maximal value of prime divisors of numbers in reduced residue system for n.
%C The smallest number for which a(n)=k is the n-th Euclid number (A006862=A002110 + 1).
%C Largest value of A001221(k) for 1 <= k <= n such that gcd(k, n) = 1. - _Michael De Vlieger_, Aug 10 2017
%H Michael De Vlieger, <a href="/A051265/b051265.txt">Table of n, a(n) for n = 1..10000</a>
%H Z. Abel, E. Demaine, M. Demaine, H. Matsui and G. Rote, <a href="http://2011.cccg.ca/PDFschedule/papers/paper49.pdf">Common Developments of Several Different Orthogonal Boxes</a>, CCCG 2011, Toronto ON, August 10-12, 2011.
%F a(n) << log n/log log n. - _Charles R Greathouse IV_, Aug 10 2017
%e For n=60 a(n)=1 since in RRS[ 60 ] only 1 and prime powers occur (see A051250).
%t Table[Max@ Map[PrimeNu, Cases[Range[n - 1], k_ /; CoprimeQ[n, k]]] /. k_ /; ! IntegerQ@ k -> 0, {n, 105}] (* _Michael De Vlieger_, Aug 10 2017 *)
%o (PARI) a(n)=my(k=1,s); forprime(p=2,, if(n%p==0, next); k*=p; if(k>n, return(s)); s++) \\ _Charles R Greathouse IV_, Aug 10 2017
%Y Records are A006862.
%Y Cf. A001221, A002110, A051250, A051266, A051267, A051268.
%K nonn,easy
%O 1,7
%A _Labos Elemer_