A011773 Variant of Carmichael's lambda function: a(p1^e1*...*pN^eN) = lcm((p1-1)*p1^(e1-1), ..., (pN-1)*pN^(eN-1)).

1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 2, 12, 6, 4, 8, 16, 6, 18, 4, 6, 10, 22, 4, 20, 12, 18, 6, 28, 4, 30, 16, 10, 16, 12, 6, 36, 18, 12, 4, 40, 6, 42, 10, 12, 22, 46, 8, 42, 20, 16, 12, 52, 18, 20, 12, 18, 28, 58, 4, 60, 30, 6, 32, 12, 10, 66, 16, 22, 12

Offset: 1

Author

Thierry Moreau (Thierry.Moreau(AT)connotech.com), Simon Plouffe

Keywords

• nonn
• nice
• easy

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
• L. Blum; M. Blum; M. Shub, A simple unpredictable pseudorandom number generator, SIAM J. Comput. 15 (1986), no. 2, 364-383. see p. 377.
• J.-H. Evertse and E. van Heyst, Which new RSA signatures can be computed from some given RSA signatures?, Proceedings of Eurocrypt'90, Lect. Notes Comput. Sci., 473, Springer-Verlag, pp. 84-97, see page 86.
• Eric Weisstein's World of Mathematics, Carmichael Function.
• Eric Weisstein's World of Mathematics, Modulo Multiplication Group.

Crossrefs

Cf. A002322.

Programs

Haskell

a011773 n = foldl lcm 1 $ map (a085730 . a095874) $
                          zipWith (^) (a027748_row n) (a124010_row n)
-- Reinhard Zumkeller, Feb 16 2012

Mathematica

Table[ If[ n==1, 1, LCM@@Map[ (#1[ [ 1 ] ]-1)*#1[ [ 1 ] ]^(#1[ [ 2 ] ]-1)&, FactorInteger[ n ] ] ], {n, 1, 70} ] (* Olivier Gérard, Aug 1997 *)
a[2] = 1;
a[n_] := CarmichaelLambda[2n];
Array[a, 1000] (* Jean-François Alcover, Sep 19 2020 *)

PARI

a(n)=lcm( apply( f -> (f[1]-1)*f[1]^(f[2]-1), Vec(factor(n)~)))  \\ M. F. Hasler, Oct 23 2011

Formula

a(n) = A002322(2*n), for n != 2. - Vladeta Jovovic, Feb 28 2004

a(n) = lcm_{k=1..A001221(n)} A085730(A095874(A027748(n,k)^A124010(n,k))). - Reinhard Zumkeller, Feb 16 2012

Extensions

Description corrected by Antti Karttunen, Jan 09 2000

Definition made more explicit by M. F. Hasler, Oct 23 2011