|
%I M0298 N0110 #125 Feb 07 2024 01:13:54
%S 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,
%T 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,
%U 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
%N 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.
%C a(n) is the largest order of any element in the multiplicative group modulo n. - _Joerg Arndt_, Mar 19 2016
%C 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
%D D. H. Lehmer, Guide to Tables in the Theory of Numbers. Bulletin No. 105, National Research Council, Washington, DC, 1941, pp. 7-10.
%D W. J. LeVeque, Topics in Number Theory. Addison-Wesley, Reading, MA, 2 vols., 1956, Vol. 1, p. 53.
%D Kenneth H. Rosen, Elementary Number Theory and Its Applications, Addison-Wesley, 1984, page 269.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H T. D. Noe, <a href="/A002322/b002322.txt">Table of n, a(n) for n = 1..10000</a>
%H L. Blum, M. Blum, and M. Shub, <a href="http://dx.doi.org/10.1137/0215025">A simple unpredictable pseudorandom number generator</a>, SIAM J. Comput. 15 (1986), no. 2, 364-383. see p. 377.
%H P. J. Cameron and D. A. Preece, <a href="http://www.maths.qmul.ac.uk/~pjc/csgnotes/lambda.pdf">Notes on primitive lambda-roots</a>
%H R. D. Carmichael, <a href="http://dx.doi.org/10.1090/S0002-9904-1910-01892-9">Note on a new number theory function</a>, Bull. Amer. Math. Soc. 16 (1909-10), 232-238.
%H A. Cauchy, Mémoire sur la résolution des équations indéterminées du premier degré en nombres entiers, <a href="http://gallica.bnf.fr/ark:/12148/bpt6k90204r/f12.image.r">Oeuvres Complètes</a>. Gauthier-Villars, Paris, 1882-1938, Series (2), Vol. 12, pp. 9-47.
%H A. de Vries, <a href="http://math-it.org/Mathematik/Zahlentheorie/Zahl/ZahlApplet.html">The prime factors of an integer(along with Euler's phi and Carmichael's lambda functions)</a>, Applet
%H Paul Erdős, Carl Pomerance, and Eric Schmutz, <a href="http://www.math.dartmouth.edu/~carlp/PDF/lambda.pdf">Carmichael's lambda function</a>, Acta Arithmetica 58 (1991), pp. 363-385.
%H J.-H. Evertse and E. van Heyst, <a href="http://dx.doi.org/10.1007/3-540-46877-3_8">Which new RSA signatures can be computed from some given RSA signatures?</a>, Proceedings of Eurocrypt '90, Lect. Notes Comput. Sci., 473, Springer-Verlag, pp. 84-97, see page 86.
%H J. M. Grau and A. M. Oller-Marcén, <a href="http://arxiv.org/abs/1311.3522">On the congruence sum_{j=1}^{n-1} j^{k(n-1)} == -1 (mod n); k-strong Giuga and k-Carmichael numbers</a>, arXiv preprint arXiv:1311.3522 [math.NT], 2013.
%H Romeo Meštrović, <a href="http://arxiv.org/abs/1305.1867">Generalizations of Carmichael numbers I,</a> arXiv:1305.1867v1 [math.NT], May 04 2013.
%H P. Pollack, <a href="https://web.archive.org/web/20130509125813/http://alpha01.dm.unito.it/personalpages/cerruti/ac/notes.pdf">Analytic and Combinatorial Number Theory</a> Course Notes, p. 80.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/CarmichaelFunction.html">Carmichael Function</a>
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Carmichael_function">Carmichael function</a>
%H Wolfram Research, <a href="http://functions.wolfram.com/NumberTheoryFunctions/CarmichaelLambda/03/02">First 50 values of Carmichael lambda(n)</a>
%H <a href="/index/Cor#core">Index entries for "core" sequences</a>
%F 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)).
%F a(n) = lcm_{k=1..A001221(n)} A207193(A095874(A027748(n,k)^A124010(n,k))). - _Reinhard Zumkeller_, Feb 16 2012
%p with(numtheory); A002322 := lambda; [seq(lambda(n), n=1..100)];
%t Table[CarmichaelLambda[k], {k, 50}] (* _Artur Jasinski_, Apr 05 2008 *)
%o (Magma) [1] cat [ CarmichaelLambda(n) : n in [2..100]];
%o (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
%o (PARI) a(n)=lcm(znstar(n)[2]) \\ _Charles R Greathouse IV_, Aug 04 2012
%o (Haskell)
%o a002322 n = foldl lcm 1 $ map (a207193 . a095874) $
%o zipWith (^) (a027748_row n) (a124010_row n)
%o -- _Reinhard Zumkeller_, Feb 16 2012
%o (Python)
%o from sympy import reduced_totient
%o def A002322(n): return reduced_totient(n) # _Chai Wah Wu_, Feb 24 2021
%Y Cf. A011773, A002174, A002616, A034380, A061258, A062373, A141258, A162578 (partial sums), A218342.
%K nonn,core,easy,nice
%O 1,3
%A _N. J. A. Sloane_
|
