A066799 -id:A066799 - 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

A007732 Period of decimal representation of 1/n.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 6, 1, 1, 1, 2, 1, 6, 6, 1, 1, 16, 1, 18, 1, 6, 2, 22, 1, 1, 6, 3, 6, 28, 1, 15, 1, 2, 16, 6, 1, 3, 18, 6, 1, 5, 6, 21, 2, 1, 22, 46, 1, 42, 1, 16, 6, 13, 3, 2, 6, 18, 28, 58, 1, 60, 15, 6, 1, 6, 2, 33, 16, 22, 6, 35, 1, 8, 3, 1, 18, 6, 6, 13, 1, 9, 5, 41, 6, 16, 21, 28, 2, 44, 1

Offset: 1

N. J. A. Sloane, Hal Sampson [ hals(AT)easynet.com ]

Appears to be a divisor of A007733*A007736. - Henry Bottomley, Dec 20 2001
Primes p such that a(p) = p-1 are in A001913. - Dmitry Kamenetsky, Nov 13 2008
When 1/n has a finite decimal expansion (namely, when n = 2^a*5^b), a(n) = 1 while A051626(n) = 0. - M. F. Hasler, Dec 14 2015
a(n.n) >= a(n) where n.n is A020338(n). - Davide Rotondo, Jun 13 2024

J. H. Conway and R. K. Guy, The Book of Numbers, Copernicus Press, NY, 1996, pp. 159 etc.

Jon E. Schoenfield, Table of n, a(n) for n = 1..10000 (first 1000 terms from T. D. Noe)
Project Euler, Reciprocal cycles: Problem 26
Index entries for sequences related to decimal expansion of 1/n

Cf. A121341, A066799, A121090, A001913, A084680.

A007732 := proc(n)
    a132740 := 1 ;
    for pe in ifactors(n)[2] do
        if not op(1,pe) in {2,5} then
            a132740 := a132740*op(1,pe)^op(2,pe) ;
        end if;
    end do:
    if a132740 = 1 then
        1 ;
    else
        numtheory[order](10,a132740) ;
    end if;
end proc:
seq(A007732(n),n=1..50) ; # R. J. Mathar, May 05 2023

Table[r = n/2^IntegerExponent[n, 2]/5^IntegerExponent[n, 5]; MultiplicativeOrder[10, r], {n, 100}] (* T. D. Noe, Oct 17 2012 *)

a(n)=znorder(Mod(10,n/2^valuation(n,2)/5^valuation(n,5))) \\ Charles R Greathouse IV, Jan 14 2013

from sympy import n_order, multiplicity
def A007732(n): return n_order(10,n//2**multiplicity(2,n)//5**multiplicity(5,n)) # Chai Wah Wu, Feb 07 2022

def a(n):
    n = ZZ(n)
    rad = 2**n.valuation(2) * 5**n.valuation(5)
    return Zmod(n // rad)(10).multiplicative_order()
[a(n) for n in range(1, 20)]
# F. Chapoton, May 03 2020

Note that if n=r*s where r is a power of 2 and s is odd then a(n)=a(s). Also if n=r*s where r is a power of 5 and s is not divisible by 5 then a(n) = a(s). So we just need a(n) for n not divisible by 2 or 5. This is the smallest number m such that n divides 10^m - 1; m is a divisor of phi(n), where phi = A000010.
phi(n) = n-1 only if n is prime and since a(n) divides phi(n), a(n) can only equal n-1 if n is prime. - Scott Hemphill (hemphill(AT)alumni.caltech.edu), Nov 23 2006
a(n)=a(A132740(n)); a(A132741(n))=a(A003592(n))=1. - Reinhard Zumkeller, Aug 27 2007

More terms from James Sellers, Feb 05 2000

A066800 Number of different eventual period lengths for power sequences mod n; i.e., number of different period lengths of repeating digits of 1/n in different bases.

Original entry on oeis.org

1, 1, 2, 2, 3, 2, 4, 2, 4, 3, 4, 2, 6, 4, 3, 3, 5, 4, 6, 3, 4, 4, 4, 2, 6, 6, 6, 4, 6, 3, 8, 4, 4, 5, 6, 4, 9, 6, 6, 3, 8, 4, 8, 4, 6, 4, 4, 3, 8, 6, 5, 6, 6, 6, 6, 4, 6, 6, 4, 3, 12, 8, 4, 5, 6, 4, 8, 5, 4, 6, 8, 4, 12, 9, 6, 6, 8, 6, 8, 3, 8, 8, 4, 4, 5, 8, 6, 4, 8, 6, 6, 4, 8, 4, 9, 4, 12, 8, 8, 6, 9, 5, 8

Offset: 1

Henry Bottomley, Dec 20 2001

nonn

			Modulo 5, powers of 1,6,11 etc. are 1,1,1,1,1,1,...; of 2,7,12 etc. are 1,2,4,3,1,2,4,3,...; of 3,8,13 etc. are 1,3,4,2,1,3,4,2,...; of 4,9,14 etc. are 1,4,1,4,1,4,...; of 5,10,15 etc. are 1,0,0,0,0,... So the eventual period lengths are 1,4,4,2,1 giving three distinct lengths, so a(5)=3.

Antti Karttunen, Table of n, a(n) for n = 1..10000
Florian Luca and Carl Pomerance, On the average number of divisors of the Euler function, Publicationes Mathematicae Debrecen, Vol. 70, No. 1-2 (2007), pp. 125-148.

This is the number of different values of rows of the square array A066799.
Cf. also A206941.
Cf. A000005, A001620, A002322.

A066800 := proc(n)
    numtheory[tau](numtheory[lambda](n)) ;
end proc:
seq(A066800(n),n=1..100) ; # R. J. Mathar, Oct 01 2017

Array[DivisorSigma[0, CarmichaelLambda@ #] &, 103] (* Michael De Vlieger, Jul 16 2017 *)

A002322(n) = lcm(znstar(n)[2]); \\ This function from Charles R Greathouse IV, Aug 04 2012
A066800(n) = numdiv(A002322(n)); \\ Antti Karttunen, Jul 16 2017

Number of divisors of reduced totient function: a(n) = A000005(A002322(n)).

Sum_{k=1..n} a(k) ~ n * exp(c(n) * (log(n)/log(log(n)))(1/2) * (1 + O(log(log(log(n)))/log(log(n))))), where c(n) is a number in the interval (1/7, 2*sqrt(2))*exp(-gamma/2) and gamma is A001620 (Luca and Pomerance, 2007). - Amiram Eldar, Oct 29 2022

More terms from David Wasserman, Nov 14 2002

A250211 Square array read by antidiagonals: A(m,n) = multiplicative order of m mod n, or 0 if m and n are not coprime.

Original entry on oeis.org

1, 1, 1, 1, 0, 1, 1, 1, 2, 1, 1, 0, 0, 0, 1, 1, 1, 1, 2, 4, 1, 1, 0, 2, 0, 4, 0, 1, 1, 1, 0, 1, 2, 0, 3, 1, 1, 0, 1, 0, 0, 0, 6, 0, 1, 1, 1, 2, 2, 1, 2, 3, 2, 6, 1, 1, 0, 0, 0, 4, 0, 6, 0, 0, 0, 1, 1, 1, 1, 1, 4, 1, 2, 2, 3, 4, 10, 1, 1, 0, 2, 0, 2, 0, 0, 0, 6, 0, 5, 0, 1, 1, 1, 0, 2, 0, 0, 1, 2, 0, 0, 5, 0, 12, 1

Offset: 1

Eric Chen, Dec 29 2014

Read by antidiagonals:
m\n   1    2    3    4    5    6    7    8    9    10    11    12    13
1     1    1    1    1    1    1    1    1    1     1     1     1     1
2     1    0    2    0    4    0    3    0    6     0    10     0    12
3     1    1    0    2    4    0    6    2    0     4     5     0     3
4     1    0    1    0    2    0    3    0    3     0     5     0     6
5     1    1    2    1    0    2    6    2    6     0     5     2     4
6     1    0    0    0    1    0    2    0    0     0    10     0    12
7     1    1    1    2    4    1    0    2    3     4    10     2    12
8     1    0    2    0    4    0    1    0    2     0    10     0     4
9     1    1    0    1    2    0    3    1    0     2     5     0     3
10    1    0    1    0    0    0    6    0    1     0     2     0     6
11    1    1    2    2    1    2    3    2    6     1     0     2    12
12    1    0    0    0    4    0    6    0    0     0     1     0     2
13    1    1    1    1    4    1    2    2    3     4    10     1     0
etc.
A(m,n) = Least k>0 such that m^k=1 (mod n), or 0 if no such k exists.
It is easy to prove that column n has period n.
A(1,n) = 1, A(m,1) =1.
If A(m,n) differs from 0, it is period length of 1/n in base m.
The maximum number in column n is psi(n) (A002322(n)), and all numbers in column n (except 0) divide psi(n), and all factors of psi(n) are in column n.
Except the first row, every row contains all natural numbers.

			A(3,7) = 6 because:
3^0 = 1 (mod 7)
3^1 = 3 (mod 7)
3^2 = 2 (mod 7)
3^3 = 6 (mod 7)
3^4 = 4 (mod 7)
3^5 = 5 (mod 7)
3^6 = 1 (mod 7)
...
And the period is 6, so A(3,7) = 6.

Cf. A002322, A111076, A111725, A001918, A008330, A007733, A002326, A007732, A051626, A066799.

See A139366 for another version.

f:= proc(m,n)
  if igcd(m,n) <> 1 then 0
  elif n=1 then 1
  else numtheory:-order(m,n)
  fi
end proc:
seq(seq(f(t-j,j),j=1..t-1),t=2..65); # Robert Israel, Dec 30 2014

a250211[m_, n_] = If[GCD[m, n] == 1, MultiplicativeOrder[m, n], 0]
Table[a250211[t-j, j], {t, 2, 65}, {j, 1, t-1}]

A249772 Period of the senary (base-6) representation of 1/n, or 0 if 1/n terminates.

Original entry on oeis.org

0, 0, 0, 0, 1, 0, 2, 0, 0, 1, 10, 0, 12, 2, 1, 0, 16, 0, 9, 1, 2, 10, 11, 0, 5, 12, 0, 2, 14, 1, 6, 0, 10, 16, 2, 0, 4, 9, 12, 1, 40, 2, 3, 10, 1, 11, 23, 0, 14, 5, 16, 12, 26, 0, 10, 2, 9, 14, 58, 1, 60, 6, 2, 0, 12, 10, 33, 16, 11, 2, 35, 0, 36, 4, 5, 9, 10, 12, 78, 1, 0, 40, 82, 2, 16

Offset: 1

Michal Kaczmarczyk, Dec 03 2014

			a(7)=2, because 1/7 has senary period 2 (0.0505050505...).

Wikipedia, Senary

Cf. A051626 (base 10), A246004 (base 12).

With ones instead of zeros: A007737, A066799 (all bases as columns).

f[n_] := Length[ RealDigits[1/n, 6][[1, -1]]]; Array[f, 85] (* Robert G. Wilson v, Jan 09 2015 *)

More terms from Robert G. Wilson v, Jan 09 2015

A179195 Triangle array: row n lists the number of repeating digits of 1/2 through 1/(n-1) in base n, or 0 if it terminates.

Original entry on oeis.org

1, 0, 1, 1, 2, 1, 0, 0, 0, 1, 1, 1, 2, 4, 1, 0, 2, 0, 4, 2, 1, 1, 0, 1, 2, 1, 3, 1, 0, 1, 0, 0, 1, 6, 0, 1, 1, 2, 2, 1, 2, 3, 2, 6, 1, 0, 0, 0, 4, 0, 6, 0, 0, 4, 1, 1, 1, 1, 4, 1, 2, 2, 3, 4, 10, 1, 0, 1, 0, 1, 1, 0, 0, 6, 2, 5, 2, 1, 1, 0, 2, 0, 1, 1, 2, 0, 1, 5, 2, 12, 1, 0, 1, 0, 1, 1, 3, 0, 3, 1, 5, 1, 3, 3, 1

Offset: 3

Will Nicholes, Jul 01 2010

			Rows show the number of repeating digits for:
1/2 base 3
1/2 base 4, 1/3 base 4
1/2 base 5, 1/3 base 5, 1/4 base 5

Cf. A066799 (similar table but does not differentiate terminating versus non-terminating values.)

A225488 Murai Chuzen numbers.

Original entry on oeis.org

9, 45, 3, 225, 18, 15, -1, 1125, 1, 99, 495, 33, 2475, 198, 165, -1, 12375, 11, 999, 4995, 333, 24975, 1998, 1665, -1, 124875, 111, 9999, 49995, 3333, 249975, 19998, 16665, -1, 1249875, 1111, 99999, 49995, 33333, 2499975, 199998, 166665, -1, 12499875, 11111, 999999, 4999995, 333333, 24999975, 1999998, 1666665, -1, 124999875, 111111

Offset: 1

Jonathan Sondow, May 10 2013

"Murai Chuzen divides 9 by 1, 2, 3, 4, 5, 6, 7, 8, 9, getting the figures 9, 45, 3, 225, 18, 15, x (not divisible), 1125, 1, -- without reference to the decimal points. Similarly he divides 99 by 1, 2, 3, 4, 5, 6, 7, 8, 9, getting the figures 99, 495, 33, 2475, 198, 165, x, 12375, 11. Next he divides 999 by 1, 2, 3, 4, 5, 6, 7, 8, 9, getting the figures 999, 4995, 333, 24975, 1998, 1665, x, 124875, 111." (Smith and Mikami, expanded and corrected)
Smith and Mikami put "x" whenever a decimal does not terminate. In the data, I put -1 instead of "x".
Murai Chuzen concludes that if 1 is divided by 9, 45, 3, 225, 18, 15, 1125, and 1, the results will have one-digit repetends; if 1 is divided by 99, 495, 33, 2475, 198, 165, 12375, and 11, the results will have two-digit repetends; if 1 is divided by 999, 4995, 333, 24975, 1998, 1665, 124875, and 111, the results will have three-digit repetends; etc.

			9/1 = 9, so a(1) = 9; 9/2 = 4.5, so a(2) = 45; 9/7 does not terminate, so a(7) = -1; 9/8 = 1.125, so a(8) = 1125; 9/9 = 1, so a(9) = 1.
99/1 = 99, so a(10) = 99; 99/2 = 49.5, so a(11) = 495.

Murai Chuzen, Sampo Doshi-mon (Arithmetic for the Young), 1781.

David Eugene Smith and Yoshio Mikami, A history of Japanese mathematics, Open Court, 1914, reprinted by Dover, 2004, p. 176.

Cf. A001913, A007732, A066799, A096688, A121090, A121341, A181431.

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

A007732 Period of decimal representation of 1/n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Sage

Formula

Extensions

A066800 Number of different eventual period lengths for power sequences mod n; i.e., number of different period lengths of repeating digits of 1/n in different bases.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A250211 Square array read by antidiagonals: A(m,n) = multiplicative order of m mod n, or 0 if m and n are not coprime.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

A249772 Period of the senary (base-6) representation of 1/n, or 0 if 1/n terminates.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A179195 Triangle array: row n lists the number of repeating digits of 1/2 through 1/(n-1) in base n, or 0 if it terminates.

Views

Author

Keywords

Examples

Crossrefs

A225488 Murai Chuzen numbers.

Views

Author

Keywords

Comments

Examples

References