A002326 -id:A002326 - cp's OEIS frontend

A057764 Triangle T(n,k) = number of nonzero elements of multiplicative order k in Galois field GF(2^n) (n >= 1, 1 <= k <= 2^n-1).

1, 1, 0, 2, 1, 0, 0, 0, 0, 0, 6, 1, 0, 2, 0, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 30, 1, 0, 2, 0, 0, 0, 6, 0, 6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 12, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 36

Offset: 1

N. J. A. Sloane, Nov 01 2000

			Table begins:
  1;
  1, 0, 2;
  1, 0, 0, 0, 0, 0, 6;
  ...

Robert Israel, Table of n, a(n) for n = 1..16369 (rows 1 to 13, flattened)

Cf. A000010, A000225, A002326, A053287.

Magma
```
{* Order(g) : g in GF(2^6) | g ne 0 *};
```

f:= proc(n,k) if 2^n-1 mod k = 0 then numtheory:-phi(k) else 0 fi end proc:
seq(seq(f(n,k),k=1..2^n-1), n=1..10); # Robert Israel, Jul 21 2016

T[n_, k_] := If[Divisible[2^n - 1, k], EulerPhi[k], 0];
Table[T[n, k], {n, 1, 10}, {k, 1, 2^n - 1}] // Flatten (* Jean-François Alcover, Feb 07 2023, after Robert Israel *)

From Robert Israel, Jul 21 2016: (Start)
T(n,k) = A000010(k) if k is a divisor of 2^n-1, otherwise 0.
Sum_{k=1..2^n-1} T(n,k) = 2^n-1 = A000225(n).
G.f. as triangle: g(x,y) = Sum_{j>=0} x^A002326(j)*A000010(2j+1)*y^(2j+1)/(1-x^A002326(j)). (End)

T(6,21) corrected by Robert Israel, Jul 21 2016

A059909 a(n) = |{m : multiplicative order of n mod m = 4}|.

Original entry on oeis.org

0, 2, 6, 4, 12, 4, 26, 18, 14, 6, 24, 12, 64, 8, 16, 8, 66, 20, 36, 8, 64, 24, 76, 6, 28, 12, 64, 24, 48, 12, 100, 40, 50, 48, 36, 8, 96, 40, 28, 8, 104, 12, 208, 36, 24, 36, 200, 18, 48, 36, 36, 24, 128, 8, 152, 16, 172, 24, 48, 12, 48, 36, 56, 72, 40, 8, 128, 56, 48, 40

Offset: 1

Vladeta Jovovic, Feb 08 2001

The multiplicative order of a mod m, gcd(a,m) = 1, is the smallest natural number d for which a^d = 1 (mod m).

			a(2) = |{5, 15}| = 2, a(3) = |{5, 10, 16, 20, 40, 80}| = 6, a(4) = |{17, 51, 85, 255}| = 4, a(5) = |{13, 16, 26, 39, 48, 52, 78, 104, 156, 208, 312, 624}| = 12, ...

Cf. A059907, A059908, A059910-A059911, A059499, A059885-A059892, A002326, A053446-A053452, A002329, A055205, A048691, A048785.

Table[DivisorSigma[0,n^4-1]-DivisorSigma[0,n^2-1],{n,70}] (* Harvey P. Dale, Nov 30 2011 *)

a(n) = if(n == 1, 0, numdiv(n^4-1) - numdiv(n^2-1)); \\ Amiram Eldar, Jan 25 2025

a(n) = tau(n^4-1)-tau(n^2-1), where tau(n) = number of divisors of n A000005. More generally, if b(n, r) = |{m : multiplicative order of n mod m = r}| then b(n, r) = Sum_{d|r} mu(d)*tau(n^(r/d)-1), where mu(n) = Moebius function A008683.

A059910 a(n) = |{m : multiplicative order of n mod m = 5}|.

Original entry on oeis.org

0, 1, 4, 6, 9, 4, 4, 6, 20, 9, 8, 2, 6, 6, 12, 44, 5, 6, 18, 14, 12, 4, 4, 2, 56, 13, 20, 4, 6, 2, 40, 6, 18, 12, 12, 44, 63, 6, 28, 4, 16, 14, 8, 2, 18, 12, 28, 14, 70, 3, 42, 12, 42, 6, 24, 8, 56, 44, 60, 6, 60, 2, 4, 90, 21, 20, 24, 2, 18, 60, 88, 6, 12, 2, 28, 26, 6, 28, 8, 14, 170

Offset: 1

Vladeta Jovovic, Feb 08 2001

The multiplicative order of a mod m, gcd(a,m) = 1, is the smallest natural number d for which a^d = 1 (mod m).

Cf. A059907-A059909, A059911, A059499, A059885-A059892, A002326, A053446-A053452, A002329, A055205, A048691, A048785.

a[n_] := Subtract @@ DivisorSigma[0, {n^5-1, n-1}]; a[1] = 0; Array[a, 100] (* Amiram Eldar, Jan 25 2025 *)

a(n) = if(n == 1, 0, numdiv(n^5-1) - numdiv(n-1)); \\ Amiram Eldar, Jan 25 2025

a(n) = tau(n^5-1)-tau(n-1), where tau(n) = number of divisors of n A000005. Generally, if b(n, r) = |{m : multiplicative order of n mod m = r}| then b(n, r) = Sum_{d|r} mu(d)*tau(n^(r/d)-1), where mu(n) = Moebius function A008683.

A141216 a(n) = A137576((N-1)/2) - N, where N = A001567(n).

Original entry on oeis.org

30, 320, 224, 240, 72, 360, 728, 0, 672, 216, 1320, 0, 0, 16, 5060, 60, 126, 10560, 216, 0, 3360, 2574, 150, 5040, 2808, 3600, 3600, 232, 400, 420, 22, 2700, 2784, 224, 96, 70, 1640, 240, 9200, 3600, 2760, 58344, 616, 504, 102, 5600, 8064, 264, 11880, 1440, 7488, 252

Offset: 1

Vladimir Shevelev, Jun 14 2008, Jul 13 2008

nonn

The zero terms are of a special interest. Indeed, since for any odd prime p, A137576((p-1)/2)=p, then it is natural to call "overpseudoprimes" those Poulet pseudoprimes A001567(n) for which a(n)=0.
Theorem. A squarefree composite number m = p_1*p_2*...*p_k is an overpseudoprime if and only if A002326((p_1-1)/2) = A002326((p_2-1)/2) = ... = A002326((p_k-1)/2). Moreover, every overpseudoprime is in A001262.
Note that in A001262 there exist terms which are not squarefree. The first is A001262(52) = 1194649 = 1093^2.
It can be shown that if an overpseudoprime is not a multiple of the square of a Wieferich prime (see A001220) then it is squarefree. Also all squares of Wieferich primes are overpseudoprimes.

Amiram Eldar, Table of n, a(n) for n = 1..10000
V. Shevelev, Overpseudoprimes, Mersenne Numbers and Wieferich Primes, arxiv:0806.3412 [math.NT], 2008-2012.

Cf. A137576, A001567, A001262, A002326, A006694.

fppQ[n_]:=PowerMod[2,n,n]==2;f[n_] := (t = MultiplicativeOrder[2, 2n+1])*DivisorSum[2n+1, EulerPhi[#] / MultiplicativeOrder[2, #]&]-t+1; s={}; Do[If[fppQ[n] && CompositeQ[n],AppendTo[s,f[(n-1)/2 ]-n]],{n,1,10000}]; s (* Amiram Eldar, Dec 09 2018 after Jean-François Alcover at A137576 *)

f(n) = my(t); sumdiv(2*n+1, d, eulerphi(d)/(t=znorder(Mod(2, d))))*t-t+1; \\ A137576
isfpp(n) = {Mod(2, n)^n==2 & !isprime(n) & n>1}; \\ A001567
lista(nn) = {for (n=1, nn, if (isfpp(n), print1(f((n-1)/2) - n, ", ");););} \\ Michel Marcus, Dec 09 2018

More terms via b137576.txt from R. J. Mathar, Jun 12 2010

More terms from Michel Marcus, Dec 09 2018

A141229 Odd numbers k for which A006694((k-1)/2) = 3.

Original entry on oeis.org

27, 43, 109, 125, 157, 229, 277, 283, 307, 499, 643, 691, 733, 739, 811, 997, 1021, 1051, 1069, 1093, 1331, 1459, 1579, 1597, 1627, 1699, 1723, 1789, 1933, 2179, 2197, 2203, 2251, 2341, 2347, 2749, 2917, 3163, 3181, 3229, 3259, 3373, 4027, 4339, 4549, 4597, 4651, 4909

Offset: 1

Vladimir Shevelev, Jun 15 2008

nonn

Conjecture. The terms of the sequence have only one prime divisor; moreover, p^3 is in the sequence if and only if p is in A001122.

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A006694, A002326, A001122, A001133.

r[n_] := EulerPhi[n]/MultiplicativeOrder[2, n]; Select[Range[5000], Total@(r /@ Divisors[#]) - 1 == 3 &] (* Amiram Eldar, Sep 12 2019 *)

a006694(n)=sumdiv(2*n+1, d, eulerphi(d)/znorder(Mod(2, d))) - 1;
isok(n) = (n % 2) && (a006694((n-1)/2) == 3); \\ Michel Marcus, Feb 08 2016

More terms from Michel Marcus, Feb 08 2016

A161135 Triangular array T(m,n), 1<=n<=m, giving the minimum positive number of deals of m cards into n piles required to collect all cards in the first pile. Each deal tosses all cards from a pile, the last dealt card indicates a pile to deal next, each deal tosses one card consecutively to the first, 2nd, ..., n-th, first, 2nd, ... pile.

Original entry on oeis.org

1, 1, 2, 1, 4, 5, 1, 3, 8, 9, 1, 6, 24, 36, 37, 1, 10, 9, 47, 85, 86, 1, 12, 55, 125, 144, 231, 232, 1, 4, 45, 181, 384, 511, 747, 748, 1, 8, 22, 214, 613, 1097, 183, 931, 932, 1, 18, 28, 54, 373, 837, 993, 1931, 2864, 2865, 1, 6, 141, 591, 1642, 3211, 8451, 1836, 14891

Offset: 1

Max Alekseyev, Jun 02 2009

Formatted as a triangular array:
m=1: 1
m=2: 1, 2
m=3: 1, 4, 5
m=4: 1, 3, 8, 9
m=5: 1, 6, 24, 36, 37
m=6: 1, 10, 9, 47, 85, 86
m=7: 1, 12, 55, 125, 144, 231, 232
m=8: 1, 4, 45, 181, 384, 511, 747, 748
m=9: 1, 8, 22, 214, 613, 1097, 183, 931, 932
m=10: 1, 18, 28, 54, 373, 837, 993, 1931, 2864, 2865
m=11: 1, 6, 141, 591, 1642, 3211, 8451, 1836, 14891, 17760, 17761
m=12: 1, 11, 47, 206, 964, 3274, 14079, 14738, 55459, 92010, 109779, 109780

			For m=n=3, deals result in a sequence of configurations (listing number of cards in the piles):
3* 0 0
1 1 1*
2* 1 0
1 2* 0
2 1* 0
3* 0 0
where * indicate a pile to deal next. The total number of deals here is T(3,3)=5.

A002326 (second column), A161136 (the total number of tossed cards)

{ T(m,n) = local(v,r,k,t); v=vector(n); v[1]=m; r=0; k=1; until( vecmax(v)==m, r++; t=v[k]; v[k]=0; k=0; while(t, k++; if(k>n, k=1); v[k]++; t--) ); r }

T(m,2)=A002326(m-1); T(m,m)=T(m,m-1)+1

A163956 Multiplicative order of 2 in Z/mZ with m = A002997(n).

Original entry on oeis.org

40, 24, 36, 56, 60, 660, 198, 252, 45, 180, 60, 144, 153, 1012, 36, 120, 300, 72, 36, 1160, 60, 36, 300, 56, 36, 660, 4284, 264, 420, 3060, 2268, 180, 540, 1680, 120, 4900, 1080, 396, 72, 72, 60, 60, 144, 2970, 612, 396, 324, 210, 180, 540, 504, 792, 198, 180

Offset: 1

A.K. Devaraj, Aug 28 2009

nonn

Related sequence: A162990. - A.K. Devaraj, Aug 31 2009

A. K. Devaraj, "Minimum universal exponent generalisation of Fermat's theorem" (ISSN 1550-3747)

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A002326, A002997, A007733, A104016, A162990, A165139.

MultiplicativeOrder[2, #] & /@ Select[Range[1, 10^6, 2], CompositeQ[#] && Divisible[# - 1, CarmichaelLambda[#]] &] (* Amiram Eldar, Jul 30 2020 *)

a(n) = A002326((A002997(n)-1)/2) = A007733(A002997(n)). - Amiram Eldar, Jul 30 2020

Corrected and extended by M. F. Hasler, Sep 23 2009
Edited by N. J. A. Sloane, Sep 23 2009, following suggestions from M. F. Hasler
More terms from Amiram Eldar, Jul 30 2020

A186522 Smallest prime factor of 2^n - 1 having the form k*n + 1.

Original entry on oeis.org

3, 7, 5, 31, 7, 127, 17, 73, 11, 23, 13, 8191, 43, 31, 17, 131071, 19, 524287, 41, 127, 23, 47, 241, 601, 2731, 262657, 29, 233, 31, 2147483647, 257, 599479, 43691, 71, 37, 223, 174763, 79, 41, 13367, 43, 431, 89, 631, 47, 2351, 97, 4432676798593, 251, 103, 53, 6361, 87211, 881, 113, 32377, 59, 179951, 61

Offset: 2

T. D. Noe, Feb 23 2011

nonn

The values of k are in A186283.
From Zhi-Wei Sun, Dec 27 2016: (Start)
For any odd prime p, by Fermat's little theorem p = (p-1) + 1 divides 2^(p-1) - 1, and it is well-known that any prime divisor q of 2^p - 1 must be congruent to 1 modulo p.
Conjecture: a(n) exists for any integer n > 1 (verified for n = 2..300). (End)
Proof of the above conjecture: By Bang's theorem, for each n > 1 except 6 there exists an odd prime p such that the multiplicative order of 2 modulo p is n, and therefore n must divide p-1. Note that a(n) <= p. - Robert Israel and Thomas Ordowski, Sep 08 2017
For prime p, a(p) = 2p + 1 if and only if p is a Lucasian prime (A002515). - Thomas Ordowski, Sep 08 2017

			For n = 4, the prime factors of 2^n - 1 are 3 and 5, but only 5 has the form k * n + 1. Hence a(4) = 5.
a(254) = 56713727820156410577229101238628035243 since this prime number is equal to (2^127+1)/3 and congruent to 1 modulo 127, and 2^127 - 1 is a Mersenne prime.
a(257) = 535006138814359 since this is a prime congruent to 1 modulo 257 and 2^257 - 1 = 535006138814359*p*q with p = 1155685395246619182673033 and q = 374550598501810936581776630096313181393 both prime. - _Zhi-Wei Sun_, Dec 27 2016

Table of n, a(n) for n = 2..1236
GIMPS (Prime95), Mersenne exponent cofactor probable prime PRP.

Cf. A000040, A000225, A060443 (all prime factors of 2^n-1).

Table[p = First/@FactorInteger[2^n - 1]; Select[p, Mod[#1, n] == 1 &, 1][[1]], {n, 2, 60}]

a(n)=my(s=if(n%2,2*n,n));forstep(p=s+1,2^n-1,s, if(Mod(2,p)^n==1&&isprime(p), return(p))) \\ Charles R Greathouse IV, Sep 07 2017

a(n)=my(f=factor(2^n-1)[,1]); for(i=1,#f, if(f[i]%n==1, return(f[i]))) \\ Charles R Greathouse IV, Sep 07 2017

a(p - 1) = p for odd prime p. - Thomas Ordowski, Sep 04 2017
A002326((a(n)-1)/2) divides n for all n > 1. - Thomas Ordowski, Sep 07 2017
a(n) = A186283(n) * n + 1. - Max Alekseyev, Apr 27 2022

Terms to a(300) in b-file from Zhi-Wei Sun, Dec 27 2016
a(301)-a(1200) in b-file from Charles R Greathouse IV, Sep 07 2017
a(1201)-a(1236) in b-file from Max Alekseyev, Apr 27 2022

A216829 2a(n) is the multiplicative order of 2 mod 3(2n-1).

Original entry on oeis.org

1, 3, 2, 3, 9, 5, 6, 6, 4, 9, 3, 11, 10, 27, 14, 5, 15, 6, 18, 6, 10, 7, 18, 23, 21, 12, 26, 10, 9, 29, 30, 9, 6, 33, 33, 35, 9, 30, 15, 39, 81, 41, 4, 42, 11, 6, 15, 18, 24, 45, 50, 51, 6, 53, 18, 18, 14, 22, 18, 12, 55, 30, 50, 7, 21, 65, 9, 54, 34, 69, 69

Offset: 1

V. Raman, Sep 17 2012

nonn

2*a(n) is the smallest m such that 3*(2n-1) | (2^m+1).

a(n) is the least k such that 2*n-1 is a factor of A002450(k). - Ali Sada, Apr 02 2025

Muniru A Asiru, Table of n, a(n) for n = 1..10000

Cf. A003558, A002326, A216469, A216833, A002450.

List([1..70],n->OrderMod(2,3*(2*n-1))/2); # Muniru A Asiru, Feb 26 2019

Table[MultiplicativeOrder[2, 3*(2*n-1)], {n, 100}]/2 (* T. D. Noe, Sep 19 2012 *)

vector(100,n,znorder(Mod(2,3*(2*n-1)))/2) \\ Joerg Arndt, Sep 14 2012.

a(n) = A216833(n)/2.

A216833 Multiplicative order of 2 mod 3*(2n-1).

Original entry on oeis.org

2, 6, 4, 6, 18, 10, 12, 12, 8, 18, 6, 22, 20, 54, 28, 10, 30, 12, 36, 12, 20, 14, 36, 46, 42, 24, 52, 20, 18, 58, 60, 18, 12, 66, 66, 70, 18, 60, 30, 78, 162, 82, 8, 84, 22, 12, 30, 36, 48, 90, 100, 102, 12, 106, 36, 36, 28, 44, 36, 24, 110, 60, 100, 14, 42

Offset: 1

V. Raman, Sep 17 2012

nonn

a(n) is the smallest m such that 3*(2n-1) | (2^m+1).

Muniru A Asiru, Table of n, a(n) for n = 1..10000

Cf. A003558, A002326, A216469, A216829.

List([1..70],n->OrderMod(2,3*(2*n-1))); # Muniru A Asiru, Feb 25 2019

Table[MultiplicativeOrder[2, 3*(2*n-1)], {n, 100}] (* T. D. Noe, Sep 19 2012 *)

vector(100,n,znorder(Mod(2,3*(2*n-1)))) \\ Joerg Arndt, Sep 14 2012.

a(n) = 2*A216829(n).

cp's OEIS Frontend

A057764 Triangle T(n,k) = number of nonzero elements of multiplicative order k in Galois field GF(2^n) (n >= 1, 1 <= k <= 2^n-1).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Formula

Extensions

A059909 a(n) = |{m : multiplicative order of n mod m = 4}|.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

Formula

A059910 a(n) = |{m : multiplicative order of n mod m = 5}|.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

PARI

Formula

A141216 a(n) = A137576((N-1)/2) - N, where N = A001567(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A141229 Odd numbers k for which A006694((k-1)/2) = 3.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

A163956 Multiplicative order of 2 in Z/mZ with m = A002997(n).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A186522 Smallest prime factor of 2^n - 1 having the form k*n + 1.

Views

A216829 2a(n) is the multiplicative order of 2 mod 3(2n-1).