login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A002322 Reduced totient function psi(n): least k such that x^k == 1 (mod n) for all x prime to n; also known as the Carmichael lambda function (exponent of unit group mod n); also called the universal exponent of n.
(Formerly M0298 N0110)
294
1, 1, 2, 2, 4, 2, 6, 2, 6, 4, 10, 2, 12, 6, 4, 4, 16, 6, 18, 4, 6, 10, 22, 2, 20, 12, 18, 6, 28, 4, 30, 8, 10, 16, 12, 6, 36, 18, 12, 4, 40, 6, 42, 10, 12, 22, 46, 4, 42, 20, 16, 12, 52, 18, 20, 6, 18, 28, 58, 4, 60, 30, 6, 16, 12, 10, 66, 16, 22, 12, 70, 6, 72, 36, 20, 18, 30, 12, 78, 4, 54 (list; graph; refs; listen; history; text; internal format)
OFFSET
1,3
COMMENTS
a(n) is the largest order of any element in the multiplicative group modulo n. - Joerg Arndt, Mar 19 2016
Largest period of repeating digits of 1/n written in different bases (i.e., largest value in each row of square array A066799 and least common multiple of each row). - Henry Bottomley, Dec 20 2001
REFERENCES
D. H. Lehmer, Guide to Tables in the Theory of Numbers. Bulletin No. 105, National Research Council, Washington, DC, 1941, pp. 7-10.
W. J. LeVeque, Topics in Number Theory. Addison-Wesley, Reading, MA, 2 vols., 1956, Vol. 1, p. 53.
Kenneth H. Rosen, Elementary Number Theory and Its Applications, Addison-Wesley, 1984, page 269.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
LINKS
L. Blum, M. Blum, and M. Shub, A simple unpredictable pseudorandom number generator, SIAM J. Comput. 15 (1986), no. 2, 364-383. see p. 377.
P. J. Cameron and D. A. Preece, Notes on primitive lambda-roots
R. D. Carmichael, Note on a new number theory function, Bull. Amer. Math. Soc. 16 (1909-10), 232-238.
A. Cauchy, Mémoire sur la résolution des équations indéterminées du premier degré en nombres entiers, Oeuvres Complètes. Gauthier-Villars, Paris, 1882-1938, Series (2), Vol. 12, pp. 9-47.
Paul Erdős, Carl Pomerance, and Eric Schmutz, Carmichael's lambda function, Acta Arithmetica 58 (1991), pp. 363-385.
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.
J. M. Grau and A. M. Oller-Marcén, On the congruence sum_{j=1}^{n-1} j^{k(n-1)} == -1 (mod n); k-strong Giuga and k-Carmichael numbers, arXiv preprint arXiv:1311.3522 [math.NT], 2013.
Romeo Meštrović, Generalizations of Carmichael numbers I, arXiv:1305.1867v1 [math.NT], May 04 2013.
P. Pollack, Analytic and Combinatorial Number Theory Course Notes, p. 80.
Eric Weisstein's World of Mathematics, Carmichael Function
FORMULA
If M = 2^e*P1^e1*P2^e2*...*Pk^ek, lambda(2^e) = 2^(e-1) if e=1 or 2, = 2^(e-2) if e > 2; lambda(M) = lcm(lambda(2^e), (P1-1)*P1^(e1-1), (P2-1)*P2^(e2-1), ..., (Pk-1)*Pk^(ek-1)).
a(n) = lcm_{k=1..A001221(n)} A207193(A095874(A027748(n,k)^A124010(n,k))). - Reinhard Zumkeller, Feb 16 2012
MAPLE
with(numtheory); A002322 := lambda; [seq(lambda(n), n=1..100)];
MATHEMATICA
Table[CarmichaelLambda[k], {k, 50}] (* Artur Jasinski, Apr 05 2008 *)
PROG
(Magma) [1] cat [ CarmichaelLambda(n) : n in [2..100]];
(PARI) A002322(n)= lcm( apply( f -> (f[1]-1)*f[1]^(f[2]-1-(f[1]==2 && f[2]>2)), Vec(factor(n)~))) \\ M. F. Hasler, Jul 05 2009
(PARI) a(n)=lcm(znstar(n)[2]) \\ Charles R Greathouse IV, Aug 04 2012
(Haskell)
a002322 n = foldl lcm 1 $ map (a207193 . a095874) $
zipWith (^) (a027748_row n) (a124010_row n)
-- Reinhard Zumkeller, Feb 16 2012
(Python)
from sympy import reduced_totient
def A002322(n): return reduced_totient(n) # Chai Wah Wu, Feb 24 2021
CROSSREFS
Sequence in context: A283465 A283466 A270492 * A127835 A117004 A128982
KEYWORD
nonn,core,easy,nice
AUTHOR
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 18 22:56 EDT 2024. Contains 370952 sequences. (Running on oeis4.)