A076618 Least x>1 such that x^d == 1 (mod d) for each divisor d of n.

2, 3, 4, 3, 6, 7, 8, 3, 4, 11, 12, 7, 14, 15, 16, 3, 18, 7, 20, 11, 22, 23, 24, 7, 6, 27, 4, 15, 30, 31, 32, 3, 34, 35, 36, 7, 38, 39, 40, 11, 42, 43, 44, 23, 16, 47, 48, 7, 8, 11, 52, 27, 54, 7, 56, 15, 58, 59, 60, 31, 62, 63, 22, 3, 66, 67, 68, 35, 70, 71, 72, 7, 74, 75, 16, 39

Offset: 1

Author

Benoit Cloitre, Oct 22 2002

Keywords

• nonn

Links

• Amiram Eldar, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A000469, A007947, A065463.

Programs

Mathematica

a[n_] := 1 + Times @@ FactorInteger[n][[;; , 1]]; Array[a, 100] (* Amiram Eldar, Feb 01 2024 *)

PARI

a(n)=if(n<0,0,x=2; while(sumdiv(n,d,(x^d-1)%d)>0,x++); x)

PARI

a(n) = 1 + vecprod(factor(n)[, 1]); \\ Amiram Eldar, Feb 01 2024

Formula

If n is prime a(n) = n+1.

For any k a(A000469(k)) = A000469(k)+1.

Sum_{k=1..n} a(k) seems to be asymptotic to c*n^2 with c=0.35... [c = A065463/2 = 0.352221100499... . - Amiram Eldar, Feb 01 2024]

a(n) = SquareFreeKernel(n) + 1 = A007947(n) + 1. - Reinhard Zumkeller, Aug 10 2004