A051265 Maximal value of prime divisors of numbers in reduced residue system for n.

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

Offset: 1

Author

Labos Elemer

Keywords

• nonn
• easy

Comments

The smallest number for which a(n)=k is the n-th Euclid number (A006862=A002110 + 1).

Largest value of A001221(k) for 1 <= k <= n such that gcd(k, n) = 1. - Michael De Vlieger, Aug 10 2017

Examples

			For n=60 a(n)=1 since in RRS[ 60 ] only 1 and prime powers occur (see A051250).
		

Links

• Michael De Vlieger, Table of n, a(n) for n = 1..10000
• Z. Abel, E. Demaine, M. Demaine, H. Matsui and G. Rote, Common Developments of Several Different Orthogonal Boxes, CCCG 2011, Toronto ON, August 10-12, 2011.

Crossrefs

Records are A006862.

Cf. A001221, A002110, A051250, A051266, A051267, A051268.

Programs

Mathematica

Table[Max@ Map[PrimeNu, Cases[Range[n - 1], k_ /; CoprimeQ[n, k]]] /. k_ /; ! IntegerQ@ k -> 0, {n, 105}] (* Michael De Vlieger, Aug 10 2017 *)

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

Formula

a(n) << log n/log log n. - Charles R Greathouse IV, Aug 10 2017