A051265 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,7

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

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.

FORMULA

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

EXAMPLE

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

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 *)

PROG

(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

CROSSREFS

Records are A006862.

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

Sequence in context: A333145 A335449 A318464 * A008647 A036475 A330746

Adjacent sequences: A051262 A051263 A051264 * A051266 A051267 A051268

KEYWORD

nonn,easy

AUTHOR

Labos Elemer

STATUS

approved