A057237 Maximum k <= n such that 1, 2, ..., k are all relatively prime to n.

1, 1, 2, 1, 4, 1, 6, 1, 2, 1, 10, 1, 12, 1, 2, 1, 16, 1, 18, 1, 2, 1, 22, 1, 4, 1, 2, 1, 28, 1, 30, 1, 2, 1, 4, 1, 36, 1, 2, 1, 40, 1, 42, 1, 2, 1, 46, 1, 6, 1, 2, 1, 52, 1, 4, 1, 2, 1, 58, 1, 60, 1, 2, 1, 4, 1, 66, 1, 2, 1, 70, 1, 72, 1, 2, 1, 6, 1, 78, 1, 2, 1, 82, 1, 4, 1, 2, 1, 88, 1, 6, 1, 2, 1

Offset: 1

Author

Leroy Quet, Sep 20 2000

Keywords

• nonn

Comments

In reduced residue system for n [=RRS(n)] the [initial] segment of consecutive integers, i.e. of which no number is missing is {1,2,....,a[n]}. The first missing term from RRS(n) is 1+a(n), the least prime divisor.. E.g. n=121 : RRS[121] = {1,2,3,4,5,6,7,8,9,10,lag,12,..}, i.e. no 11 is in RRS; a[n] is the length of longest lag-free number segment consisting of consecutive integers, since A020639[n] divides n. - Labos Elemer, May 14 2003

a(n) is also the difference between the smallest two divisors of n, (the column 1 of A193829), if n >= 2. - Omar E. Pol, Aug 31 2011

Examples

			a(25) = 4 because 1, 2, 3 and 4 are relatively prime to 25.
		

Links

• Antti Karttunen, Table of n, a(n) for n = 1..65537

Crossrefs

Cf. A020639, A083218.

Cf. A066169.

Programs

Mathematica

Join[{1},Table[Length[Split[Boole[CoprimeQ[n,Range[n-1]]]][[1]]],{n,2,100}]] (* Harvey P. Dale, Dec 28 2021 *)

PARI

a(n) = if (n==1, 1, factor(n)[1,1] - 1); \\ Michel Marcus, May 29 2015

Formula

For n >= 2, a(n) = (smallest prime dividing n) - 1 = A020639(n) - 1.

For n >= 2, a(n) = (n-1) mod (smallest prime dividing n); cf. A083218. - Reinhard Zumkeller, Apr 22 2003