A218342 -id:A218342 - cp's OEIS frontend

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.

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

Offset: 1

N. J. A. Sloane

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

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).

T. D. Noe, Table of n, a(n) for n = 1..10000
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.
A. de Vries, The prime factors of an integer(along with Euler's phi and Carmichael's lambda functions), Applet
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.
Benjamin Schreyer, Rigged Horse Numbers and their Modular Periodicity, arXiv:2409.03799 [math.CO], 2024. See p. 12.
Eric Weisstein's World of Mathematics, Carmichael Function
Wikipedia, Carmichael function
Wolfram Research, First 50 values of Carmichael lambda(n)
Index entries for "core" sequences

Cf. A011773, A002174, A002616, A034380, A061258, A062373, A141258, A162578 (partial sums), A218342.

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

[1] cat [ CarmichaelLambda(n) : n in [2..100]];

with(numtheory); A002322 := lambda; [seq(lambda(n), n=1..100)];

Table[CarmichaelLambda[k], {k, 50}] (* Artur Jasinski, Apr 05 2008 *)

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

a(n)=lcm(znstar(n)[2]) \\ Charles R Greathouse IV, Aug 04 2012

from sympy import reduced_totient
def A002322(n): return reduced_totient(n) # Chai Wah Wu, Feb 24 2021

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

A036391 a(n) = sum of order of a mod n, 0 < a < n, gcd(a, n) = 1.

Original entry on oeis.org

0, 1, 3, 3, 11, 3, 21, 7, 21, 11, 63, 7, 77, 21, 23, 23, 171, 21, 183, 23, 49, 63, 333, 15, 231, 77, 183, 49, 473, 23, 441, 87, 147, 171, 161, 49, 671, 183, 161, 47, 903, 49, 903, 147, 161, 333, 1521, 47, 903, 231, 343, 161, 1727, 183, 483, 105, 427, 473, 2439, 47

Offset: 1

David W. Wilson

A162578 Partial sums of A002322.

Original entry on oeis.org

1, 2, 4, 6, 10, 12, 18, 20, 26, 30, 40, 42, 54, 60, 64, 68, 84, 90, 108, 112, 118, 128, 150, 152, 172, 184, 202, 208, 236, 240, 270, 278, 288, 304, 316, 322, 358, 376, 388, 392, 432, 438, 480, 490, 502, 524, 570, 574, 616, 636, 652, 664, 716, 734, 754, 760, 778

Offset: 1

Jonathan Vos Post, Jul 06 2009

G. C. Greubel, Table of n, a(n) for n = 1..10000
Paul Erdős, Carl Pomerance, and Eric Schmutz, Carmichael's lambda function, Acta Arithmetica, Vol. 58, No. 4 (1991), pp. 363-385; alternative link.

Cf. A002322, A218342.

read("transforms3") ; a002322 := BFILETOLIST("b002322.txt") : A162578 :=proc(n) global a002322 ; local i; add(op(i,a002322),i=1..n) ; end: seq(A162578(n),n=1..120) ; # R. J. Mathar, Jul 16 2009

Accumulate[CarmichaelLambda[Range[60]]] (* Harvey P. Dale, Sep 21 2011 *)

a(n) = sum(i=1, n, lcm(znstar(i)[2])) \\ Felix Fröhlich, Jul 04 2018

a(n) = Sum_{k=1..n} A002322(k).

a(n) = (n^2/log(n)) * exp(B * (log(log(n))/log(log(log(n)))) * (1 + o(1))), where B = A218342 (Erdős et al., 1991). - Amiram Eldar, Dec 27 2022

a(13) corrected and more terms added by R. J. Mathar, Jul 16 2009

A359147 Partial sums of A002326.

Original entry on oeis.org

1, 3, 7, 10, 16, 26, 38, 42, 50, 68, 74, 85, 105, 123, 151, 156, 166, 178, 214, 226, 246, 260, 272, 295, 316, 324, 376, 396, 414, 472, 532, 538, 550, 616, 638, 673, 682, 702, 732, 771, 825, 907, 915, 943, 954, 966, 976, 1012, 1060, 1090, 1190, 1241, 1253, 1359, 1395, 1431

Offset: 0

N. J. A. Sloane, Feb 14 2023

nonn

a(n)/n is the average order of 2 mod m, averaged over all odd numbers m from 1 to 2n+1. From Kurlberg-Pomerance (2013), this is of order constant*n/log(n). So the graph of this sequence grows like constant*n^2/log(n). [The asymptotic formula involves the constant B = 0.3453720641..., A218342. - Amiram Eldar, Feb 15 2023]

N. J. A. Sloane, Table of n, a(n) for n = 0..10000
Pär Kurlberg and Carl Pomerance, On a problem of Arnold: the average multiplicative order of a given integer, Algebra & Number Theory, Vol. 7, No. 4 (2013), pp. 981-999.

Cf. A002326, A007733, A218342.

a:= proc(n) option remember;
     `if`(n=0, 1, a(n-1)+numtheory[order](2, 2*n+1))
    end:
seq(a(n), n=0..55);  # Alois P. Heinz, Feb 14 2023

Accumulate[MultiplicativeOrder[2,#]&/@Range[1,151,2]] (* Harvey P. Dale, Jul 08 2023 *)

a(n) = sum(k = 0, n, if(k<0, 0, znorder(Mod(2, 2*k+1)))) \\ Thomas Scheuerle, Feb 14 2023

from sympy import n_order
def A359147(n): return sum(n_order(2,m) for m in range(1,n+1<<1,2)) # Chai Wah Wu, Feb 14 2023

a(n) = Sum_{k = 0..n} A007733(2*k+1). - Thomas Scheuerle, Feb 15 2023

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

Python

Formula

A036391 a(n) = sum of order of a mod n, 0 < a < n, gcd(a, n) = 1.

Views

Author

Keywords

Comments

Links

Programs

Haskell

Maple

Mathematica

Formula

Extensions

A162578 Partial sums of A002322.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A359147 Partial sums of A002326.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula