A036391 -id:A036391 - cp's OEIS frontend

A139366 Table with the order r=r(N,n) of n modulo N, for given N and n, with gcd(N,n)=1.

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

Offset: 1

Wolfdieter Lang, May 21 2008

In the table a 0 appears for 1 <= n <= N if gcd(N,n) is not 1. In particular, this is the case for the main diagonal with N > 1. Also for N=n=1 one sets r=0 because 1^m congruent to 0 (mod 1) for all m.
For given N and n with gcd(N,n)=1 the function F(N,n;a):=n^a (mod N) has period r=r(N,n): F(N,n;a+r) congruent F(N,n;a) (mod N).
The period r is used for factoring integers in quantum computing. See e.g. the Ekert and Jozsa reference.

			Triangle begins:
  [0];
  [1,0];
  [1,2,0];
  [1,0,2,0];
  [1,4,4,2,0];
  ...
For N=5, the order r of 3 (mod 5) is 4 because 3^1 == 3 (mod 5), 3^2 == 4 (mod 5), 3^3 == 2 (mod 5), 3^4 == 1 (mod 5). Hence F(5,3;a+4) == F(5,3;a) (mod 5).

Reinhard Zumkeller, Rows n = 1..120 of triangle, flattened
A. Ekert and R. Josza, Quantum computation and Shor's factoring algorithm, Rev. Mod. Phys. 68 (1996) 733-753, sect. IV and Appendix A.
Wolfdieter Lang, First 15 rows and more.

Cf. A036391 (row sums).

See A250211 for another version.

a139366 1 1               = 0
a139366 n k | gcd n k > 1 = 0
            | otherwise   = head [r | r <- [1..], k ^ r `mod` n == 1]
a139366_row n = map (a139366 n) [1..n]
a139366_tabl = map a139366_row [1..]
-- Reinhard Zumkeller, May 01 2013

r[n_, k_] := If[ CoprimeQ[k, n], MultiplicativeOrder[k, n], 0]; Table[r[n, k], {n, 1, 14}, {k, 1, n}] // Flatten (* Jean-François Alcover, Aug 19 2013 *)

r(N,n)=if(N<2||gcd(n,N)>1,0,znorder(Mod(n,N)))
for(N=1,9,for(n=1,N,print1(r(N,n)", "))) \\ Charles R Greathouse IV, Feb 18 2013

r(N,n) is the smallest positive number with n^r == 1 (mod N), n=1..N, if gcd(N,n)=1, otherwise 0. This r is called the order of n (mod N) if gcd(N,n)=1.

A218342 Decimal expansion of e^-gamma * Product_(1 - 1/(p^3 - p^2 - p + 1)) where the product is over all primes p.

Original entry on oeis.org

3, 4, 5, 3, 7, 2, 0, 6, 4, 1, 0, 2, 9, 8, 6, 4, 8, 7, 6, 7, 3, 4, 9, 6, 8, 2, 7, 8, 9, 1, 0, 3, 3, 7, 1, 0, 7, 2, 0, 6, 6, 5, 6, 2, 5, 3, 8, 0, 4, 1, 5, 8, 7, 2, 0, 5, 6, 0, 0, 4, 8, 9, 6, 6, 2, 5, 2, 6, 5, 3, 1, 9, 5, 0, 2, 2, 5, 1, 8, 6, 6, 9, 4, 7, 9, 0, 9, 1, 1, 6, 1, 3, 9, 2, 2, 7, 6, 3, 9, 6, 9, 6, 4, 4, 7

Offset: 0

Charles R Greathouse IV, Oct 26 2012

The average order of Carmichael's lambda function is x/log x * exp(B log log x/log log log x (1 + o(1))), where B is this constant. Under the GRH, the same applies to A036391(n)/n, the sum of the orders mod n of the numbers coprime to n divided by n.

			0.34537206410298648767349682789103371072066562538041...

Paul Erdős, Carl Pomerance, and Eric Schmutz, Carmichael's lambda function, Acta Arithmetica 58 (1991), pp. 363-385.
Steven R. Finch, Mathematical Constants II, Encyclopedia of Mathematics and Its Applications, Cambridge University Press, Cambridge, 2018, p. 156 (constant C9).
Sungjin Kim, On the order of 'a' modulo 'n' on average, International Journal of Number Theory, Vol. 12, No. 8 (2016), pp. 2073-2080; arXiv preprint, arXiv:1509.03768 [math.NT], 2015-2016.
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; arXiv preprint, arXiv:1108.5209 [math.NT], 2012.
R. J. Mathar, Hardy-Littlewood constants embedded into infinite products over all positive integers, arXiv:0903.2514 [math.NT], 2009-2011; Eq. (106) page 17.

Cf. A002322, A036391, A080130, A162578.

$MaxExtraPrecision = 200; m0 = 1000; dm = 200; digits = 105; Clear[f]; f[m_] := f[m] = (slog = Normal[Series[Log[1 - 1/((p - 1)^2*(p + 1))], {p, Infinity, m}]]; Exp[slog] /. Power[p, n_] -> PrimeZetaP[-n] // N[#, digits + 10] &); f[m = m0]; Print[m, " ", f[m]]; f[m = m + dm]; While[Print[m, " ", f[m]]; RealDigits[f[m], 10, digits + 5] !=  RealDigits[f[m - dm], 10, digits + 5], m = m + dm]; B = Exp[-EulerGamma]*f[m]; RealDigits[B, 10, digits] // First (* Jean-François Alcover, Sep 20 2015 *)

exp(-Euler) * prodeulerrat(1-1/((p-1)^2*(p+1))) \\ Amiram Eldar, Mar 09 2021

More digits from Jean-François Alcover, Sep 20 2015

A086147 Sum of the orders of the elements in the group GL(2,Z_n).

Original entry on oeis.org

1, 13, 219, 367, 4891, 1977, 36085, 9791, 46731, 39133, 479157, 37119, 1289911, 243703, 375219, 305599, 6991319, 299913, 11500123, 667219, 2610657, 3723423, 40035651, 781127, 14928331, 8544673, 11297307, 4540153, 129539703, 2739477, 209881105, 9748415

Offset: 1

Yuval Dekel (dekelyuval(AT)hotmail.com), Aug 25 2003

nonn

Eric M. Schmidt, Table of n, a(n) for n = 1..60

Cf. A000252, A036391, A316566.

A086147 := n -> Sum(ConjugacyClasses(GL(2,ZmodnZ(n))), cc->Size(cc) * Order(Representative(cc))); # Eric M. Schmidt, May 18 2013

a(n) = Sum_{k=1..n} k*A316566(n, k). - Andrew Howroyd, Jul 07 2018

Corrected and extended by Eric M. Schmidt, May 18 2013

A359210 Number of m^k == 1 (mod p) for 0 < m,k < p where p is the n-th prime.

Original entry on oeis.org

1, 3, 8, 15, 27, 40, 48, 63, 63, 104, 135, 168, 180, 195, 135, 200, 171, 360, 315, 351, 420, 375, 243, 420, 560, 520, 495, 315, 648, 624, 819, 675, 660, 675, 584, 975, 1000, 891, 495, 680, 531, 1512, 999, 1280, 1064, 1323, 1755, 1095, 675, 1480, 1140, 1287

Offset: 1

Seth A. Troisi, Dec 20 2022

nonn

a(n) is the sum of (p-1) / order(m, p) for all m in Zp for the n-th prime.

			For n=3 the a(3) = 8 numbers with m^k == 1 (mod 5) (the third prime) are (1,1), (1,2), (1,3), (1,4), (2,4), (3,4), (4,2), (4,4).

Cf. A036391, A086145, A174842.

Table[Sum[(p - 1)/MultiplicativeOrder[m, p], {m, 1, p - 1}], {p, Prime[Range[20]]}]

a(n)= my(p=prime(n)); sum(m=1,p-1,(p-1)/znorder(Mod(m,p)))

import sympy
print([sum((p-1) // sympy.ntheory.n_order(m, p) for m in range(1, p)) for p in sympy.primerange(100)])

A372305 a(n) = Product_{k=2..n-1} MultiplicativeOrder(k,n) where gcd(k,n)=1.

Original entry on oeis.org

1, 1, 2, 2, 32, 2, 648, 8, 648, 32, 12500000, 8, 214990848, 648, 2048, 2048, 562949953421312, 648, 11712917736940032, 2048, 3359232, 12500000, 1377791989621882898843648, 128, 5120000000000000000, 214990848, 11712917736940032

Offset: 1

Darío Clavijo, Apr 25 2024

nonn

All terms are even for n>=3.

Cf. A000079, A036391, A249435.

Row products of triangle A216327.

Table[Times @@ Map[MultiplicativeOrder[#, n] &, Select[Range[2, n - 1], CoprimeQ[n, #] &]], {n, 2, 27}] (* Michael De Vlieger, Apr 25 2024 *)

a(n) = prod(k=2, n-1, if (gcd(k,n)==1, znorder(Mod(k,n)), 1)); \\ Michel Marcus, Apr 26 2024

from sympy import n_order, gcd, prod
a = lambda n: prod(n_order(k,n) for k in range(2, n) if gcd(k,n)==1)
print([a(n) for n in range(1, 28)])

cp's OEIS Frontend

A139366 Table with the order r=r(N,n) of n modulo N, for given N and n, with gcd(N,n)=1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Formula

A218342 Decimal expansion of e^-gamma * Product_(1 - 1/(p^3 - p^2 - p + 1)) where the product is over all primes p.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A086147 Sum of the orders of the elements in the group GL(2,Z_n).

Views

Author

Keywords

Links

Crossrefs

Programs

GAP

Formula

Extensions

A359210 Number of m^k == 1 (mod p) for 0 < m,k < p where p is the n-th prime.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

Python

A372305 a(n) = Product_{k=2..n-1} MultiplicativeOrder(k,n) where gcd(k,n)=1.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

PARI

Python