A002326 -id:A002326 - cp's OEIS frontend

A053451 Multiplicative order of 8 mod 2n+1.

1, 2, 4, 1, 2, 10, 4, 4, 8, 6, 2, 11, 20, 6, 28, 5, 10, 4, 12, 4, 20, 14, 4, 23, 7, 8, 52, 20, 6, 58, 20, 2, 4, 22, 22, 35, 3, 20, 10, 13, 18, 82, 8, 28, 11, 4, 10, 12, 16, 10, 100, 17, 4, 106, 12, 12, 28, 44, 4, 8, 110, 20, 100, 7, 14, 130, 6, 12, 68, 46, 46, 20, 28, 14, 148, 5

Offset: 0

David W. Wilson

nonn

In the case n=2 and any other case where a(n)=A000010(2n+1), the multiplicative group of units modulo 2n+1 is cyclic and thus 8 (and any other unit) is a generator. These moduli are A167796, so this occurs whenever 2n+1 (caution: not n) is a member of A167796. - Kellen Myers, Feb 06 2015

			The third term a(2) is 4 because 4 is the smallest integer such that 8^4 is congruent to 1 modulo 2*2+1=5. The orbit of 8 modulo 5 is {3, 4, 2, 1}. - _Kellen Myers_, Feb 06 2015

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Eric Weisstein's World of Mathematics, Multiplicative Order

Cf. A050980, A070667-A070675, A002326, A070676, A053447, A070677, A070681, A070678, A070679, A070682, A070680, A070683.

List([0..80],n->OrderMod(8,2*n+1)); # Muniru A Asiru, Feb 26 2019

[1] cat [Modorder(8, 2*n+1): n in [1..100]]; // Vincenzo Librandi, Apr 01 2014

Table[MultiplicativeOrder[8, n], {n, 1, 150, 2}] (* Robert G. Wilson v, Apr 05 2011 *)

vector(80, n, n--; znorder(Mod(8, 2*n+1))) \\ Michel Marcus, Feb 05 2015

A143663 a(n) is the least prime such that the multiplicative order of 3 mod a(n) equals n, or a(n)=1 if no such prime exists.

Original entry on oeis.org

2, 1, 13, 5, 11, 7, 1093, 41, 757, 61, 23, 73, 797161, 547, 4561, 17, 1871, 19, 1597, 1181, 368089, 67, 47, 6481, 8951, 398581, 109, 29, 59, 31, 683, 21523361, 2413941289, 103, 71, 530713, 13097927, 2851, 313, 42521761, 83, 43, 431, 5501, 181, 23535794707

Offset: 1

Vladimir Shevelev, Aug 28 2008

nonn

If a(n) differs from 1, then a(n) is the minimal prime divisor of A064079(n).

Max Alekseyev, Table of n, a(n) for n = 1..730 (first 153 terms from Robert G. Wilson v)

Cf. A002326, A064079, A112092, A218356, A057958, A074477.

Cf. A112927 (base 2), A143663 (base 3), A112092 (base 4), A143665 (base 5), A379639 (base 6), A379640 (base 7), A379641 (base 8), A379642 (base 9), A007138 (base 10), A379644 (base 11), A252170 (base 12).

a:= proc(n) local f,p;
f:= numtheory:-factorset(3^n - 1);
for  p in f do
   if numtheory:-order(3,p) = n then return p fi
od:
1
end proc:
seq(a(n),n=1..100); # Robert Israel, Oct 13 2014

p = 2; t = Table[0, {100}]; While[p < 100000001, a = MultiplicativeOrder[3, p]; If[0 < a < 101 && t[[a]] == 0, t[[a]] = p; Print[{a, p}]];  p = NextPrime@ p]; t (* Robert G. Wilson v, Oct 13 2014 *)

More terms from Robert G. Wilson v, Dec 11 2013

A201908 Irregular triangle of 2^k mod (2n-1).

Original entry on oeis.org

0, 1, 2, 1, 2, 4, 3, 1, 2, 4, 1, 2, 4, 8, 7, 5, 1, 2, 4, 8, 5, 10, 9, 7, 3, 6, 1, 2, 4, 8, 3, 6, 12, 11, 9, 5, 10, 7, 1, 2, 4, 8, 1, 2, 4, 8, 16, 15, 13, 9, 1, 2, 4, 8, 16, 13, 7, 14, 9, 18, 17, 15, 11, 3, 6, 12, 5, 10, 1, 2, 4, 8, 16, 11, 1, 2, 4, 8, 16, 9

Offset: 1

T. D. Noe, Dec 07 2011

The length of the rows is given by A002326. For n > 1, the first term of row n is 1 and the last term is n. Many sequences are in this one: starting at A036117 (mod 11) and A070335 (mod 23).

Row n, for n >= 2, divided elementwise by (2*n-1) gives the cycles of iterations of the doubling function D(x) = 2*x or 2*x-1 if 0 <= x < 1/2 or , 1/2 <= x < 1, respectively, with seed 1/(2*n-1). See the Devaney reference, pp. 25-26. D^[k](x) = frac(2^k/(2*n-1)), for k = 0, 1, ..., A002326(n-1) - 1. E.g., n = 3: 1/5, 2/5, 4/5, 3/5. - Gary W. Adamson and Wolfdieter Lang, Jul 29 2020.

			The irregular triangle T(n, k) begins:
n\k  0 1 2 3  4  5  6  7 8  9 10 11 12 13 14 15 16 17 ...
---------------------------------------------------------
1:   0
2:   1 2
3:   1 2 4 3
4:   1 2 4
5:   1 2 4 8  7  5
6:   1 2 4 8  5 10  9  7 3  6
7:   1 2 4 8  3  6 12 11 9  5 10  7
8:   1 2 4 8
9:   1 2 4 8 16 15 13  9
10:  1 2 4 8 16 13  7 14 9 18 17 15 11  3  6 12  5 10
... reformatted by _Wolfdieter Lang_, Jul 29 2020.

Robert L. Devaney, A First Course in Chaotic Dynamical Systems, Addison-Wesley., 1992. pp. 24-25

T. D. Noe, Rows n = 1..100, flattened

Cf. A002326, A201909 (3^k), A201910 (5^k), A201911 (7^k).

Cf. A000034 (3), A070402 (5), A069705 (7), A036117 (11), A036118 (13), A062116 (17), A036120 (19), A070347 (21), A070335 (23), A070336 (25), A070337 (27), A036122 (29), A070338 (33), A070339 (35), A036124 (37), A070340 (39), A070348 (41), A070349 (43), A070350 (45), A070351 (47), A036128 (53), A036129 (59), A036130 (61), A036131 (67), A036135 (83), A036138 (101), A036140 (107), A201920 (125), A036144 (131), A036146 (139), A036147 (149), A036150 (163), A036152 (173), A036153 (179), A036154 (181), A036157 (197), A036159 (211), A036161 (227).

R:=List([0..72],n->OrderMod(2,2*n+1));;
Flat(Concatenation([0],List([2..11],n->List([0..R[n]-1],k->PowerMod(2,k,2*n-1))))); # Muniru A Asiru, Feb 02 2019

nn = 30; p = 2; t = p^Range[0, nn]; Flatten[Table[If[IntegerQ[Log[p, n]], {0}, tm = Mod[t, n]; len = Position[tm, 1, 1, 2][[-1,1]]; Take[tm, len-1]], {n, 1, nn, 2}]]

T(n, k) = 2^k mod (2*n-1), n >= 1, k = 0, 1, ..., A002326(n-1) - 1.

T(n, k) = (2*n-1)*frac(2^k/(2*n-1)), n >= 1, k = 0, 1, ..., A002326(n-1) - 1, with the fractional part frac(x) = x - floor(x). - Wolfdieter Lang, Jul 29 2020

A216838 Odd primes for which 2 is not a primitive root.

Original entry on oeis.org

7, 17, 23, 31, 41, 43, 47, 71, 73, 79, 89, 97, 103, 109, 113, 127, 137, 151, 157, 167, 191, 193, 199, 223, 229, 233, 239, 241, 251, 257, 263, 271, 277, 281, 283, 307, 311, 313, 331, 337, 353, 359, 367, 383, 397, 401, 409, 431, 433, 439, 449, 457, 463, 479

Offset: 1

V. Raman, Sep 17 2012

nonn

Alternately, for these primes p, the polynomial (x^p+1)/(x+1) is reducible over GF(2).
The prime p belongs to this sequence if and only if A002326((p-1)/2) != (p-1). If A002326((p-1)/2) = (p-1), then the prime p belongs to the sequence A001122. - V. Raman, Dec 01 2012
The only primitive root modulo 2 is 1. See A060749. Hence 2 should be added to this sequence in order to obtain the complement of A001122. - Wolfdieter Lang, May 19 2014

Robert Israel, Table of n, a(n) for n = 1..10000
Anand Bhardwaj, Luisa Degen, Radostin Petkov, and Sidney Stanbury, A Study of Cunningham Bounds through Rogue Primes, arXiv:2311.13375 [math.NT], 2023.

Cf. A002326 (multiplicative order of 2 mod 2n+1)
Cf. A001122 (Primes for which 2 is a primitive root)
Cf. A115586 (Primes for which 2 is neither a primitive root nor a quadratic residue).

select(t -> isprime(t) and numtheory[order](2,t) <> t-1, [seq](2*i+1,i=1..1000)); # Robert Israel, May 20 2014

Select[Prime[Range[2, 100]], PrimitiveRoot[#] =!= 2 &] (* T. D. Noe, Sep 19 2012 *)

forprime(p=3, 1000, if(znorder(Mod(2,p))!=p-1, print(p)))

forprime(p=3, 1000, if(factormod((x^p+1)/(x+1), 2, 1)[1, 1]!=(p-1), print(p)))

Name corrected by Wolfdieter Lang, May 19 2014

A036259 Numbers k such that the multiplicative order of 2 modulo k is odd.

Original entry on oeis.org

1, 7, 23, 31, 47, 49, 71, 73, 79, 89, 103, 127, 151, 161, 167, 191, 199, 217, 223, 233, 239, 263, 271, 311, 329, 337, 343, 359, 367, 383, 431, 439, 463, 479, 487, 497, 503, 511, 529, 553, 599, 601, 607, 623, 631, 647, 713, 719, 721, 727, 743, 751

Offset: 1

David W. Wilson

nonn

Odd numbers k such that A007733(k) = A002326((k-1)/2) is odd.

Closed under multiplication. - Emmanuel Vantieghem, May 07 2025

			2^3 = 1 mod 7, 3 is odd, so 7 is in the sequence.

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

Cf. A002326, A007733, A036260, A053006.

Select[Range[1, 999, 2], OddQ[MultiplicativeOrder[2, #]]&] (* Jean-François Alcover, Dec 20 2017 *)

is(n)=n%2 && znorder(Mod(2,n))%2 \\ Charles R Greathouse IV, Jun 24 2015

from sympy import n_order
from itertools import count, islice
def A036259_gen(startvalue=1): # generator of terms >= startvalue
    return filter(lambda n:n_order(2,n)&1,count(max(startvalue,1)|1,2))
A036259_list = list(islice(A036259_gen(),20)) # Chai Wah Wu, Feb 07 2023

A070677 Smallest m in range 1..phi(n) such that 5^m == 1 mod n, or 0 if no such number exists.

Original entry on oeis.org

0, 1, 2, 1, 0, 2, 6, 2, 6, 0, 5, 2, 4, 6, 0, 4, 16, 6, 9, 0, 6, 5, 22, 2, 0, 4, 18, 6, 14, 0, 3, 8, 10, 16, 0, 6, 36, 9, 4, 0, 20, 6, 42, 5, 0, 22, 46, 4, 42, 0, 16, 4, 52, 18, 0, 6, 18, 14, 29, 0, 30, 3, 6, 16, 0, 10, 22, 16, 22, 0, 5, 6, 72, 36, 0, 9, 30, 4, 39, 0

Offset: 1

N. J. A. Sloane and Amarnath Murthy, May 08 2002

nonn

Cf. A070667-A070675, A002326, A070676, A053447, A070681, A070678, A053451, A070679, A070682, A070680, A070683.

[0] cat [Modorder(5, n): n in [2..100]]; // Vincenzo Librandi, Apr 01 2014

Table[SelectFirst[Range[EulerPhi[n]], PowerMod[5, #, n] == 1 &, 0],{n, 80}] (* Paul F. Marrero Romero, Oct 04 2024 *)

from sympy import n_order
def A070677(n): return n_order(5,n) if n%5 and n>1 else 0 # Chai Wah Wu, Feb 23 2023

A070682 Smallest m in range 1..phi(2n+1) such that 10^m == 1 mod 2n+1, or 0 if no such number exists.

Original entry on oeis.org

0, 1, 0, 6, 1, 2, 6, 0, 16, 18, 6, 22, 0, 3, 28, 15, 2, 0, 3, 6, 5, 21, 0, 46, 42, 16, 13, 0, 18, 58, 60, 6, 0, 33, 22, 35, 8, 0, 6, 13, 9, 41, 0, 28, 44, 6, 15, 0, 96, 2, 4, 34, 0, 53, 108, 3, 112, 0, 6, 48, 22, 5, 0, 42, 21, 130, 18, 0, 8, 46, 46, 6, 0, 42, 148

Offset: 0

N. J. A. Sloane and Amarnath Murthy, May 08 2002

nonn

Cf. A070667-A070675, A002326, A070676, A053447, A070677, A070678, A053451, A070679, A070681, A070680, A070683.

a(n) = {for (m = 1, eulerphi(2*n+1), if (10^m % (2*n+1) == 1, return (m));); return (0);} \\ Michel Marcus, Sep 14 2013

A070683 Smallest m in range 1..phi(2n+1) such that 12^m == 1 mod 2n+1, or 0 if no such number exists.

Original entry on oeis.org

0, 0, 4, 6, 0, 1, 2, 0, 16, 6, 0, 11, 20, 0, 4, 30, 0, 12, 9, 0, 40, 42, 0, 23, 42, 0, 52, 4, 0, 29, 15, 0, 4, 66, 0, 35, 36, 0, 6, 26, 0, 41, 16, 0, 8, 6, 0, 12, 16, 0, 100, 102, 0, 53, 54, 0, 112, 44, 0, 48, 11, 0, 100, 126, 0, 65, 6, 0, 136, 138, 0, 2, 4, 0, 148

Offset: 0

N. J. A. Sloane and Amarnath Murthy, May 08 2002

a(n)=2*n if 2*n+1 is in A019340, otherwise a(n)<2*n. - Robert Israel, Apr 17 2019

Robert Israel, Table of n, a(n) for n = 0..10000

Cf. A070667-A070675, A002326, A019340, A070676, A053447, A070677, A070678, A053451, A070679, A070682, A070680, A070681.

f:= proc(n)
  if n mod 3 = 1 then 0 else numtheory:-order(12,2*n+1) fi
end proc:
0, seq(f(n),n=1..100); # Robert Israel, Apr 16 2019

a[n_] := Module[{s}, s = SelectFirst[Range[EulerPhi[2n+1]], PowerMod[12, #, 2n+1] == 1&]; If[s === Missing["NotFound"], 0, s]];
a /@ Range[0, 100] (* Jean-François Alcover, Jun 04 2020 *)

A086251 Number of primitive prime factors of 2^n - 1.

Original entry on oeis.org

0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 2, 3, 1, 1, 1, 1, 1, 2, 2, 2, 1, 2, 1, 2, 1, 3, 2, 2, 1, 3, 2, 1, 2, 3, 3, 3, 1, 3, 1, 2, 2, 2, 2, 1, 1, 2, 2, 1, 2, 2, 3, 1, 2, 3, 2, 3, 2, 2, 3, 1, 1, 3, 1, 3, 2, 2, 2, 1, 1, 2, 2, 1, 1, 3, 4, 1, 2, 3, 2, 2, 1, 3, 3, 2, 3, 2, 2, 3

Offset: 1

T. D. Noe, Jul 14 2003

A prime factor of 2^n - 1 is called primitive if it does not divide 2^r - 1 for any r < n. Equivalently, p is a primitive prime factor of 2^n - 1 if ord(2,p) = n. Zsigmondy's theorem says that there is at least one primitive prime factor for n > 1, except for n=6. See A086252 for those n that have a record number of primitive prime factors.
Number of odd primes p such that A002326((p-1)/2) = n. Number of occurrences of number n in A014664. - Thomas Ordowski, Sep 12 2017
The prime factors are not counted with multiplicity, which matters for a(364)=4 and a(1755)=6. - Jeppe Stig Nielsen, Sep 01 2020

			a(11) = 2 because 2^11 - 1 = 23*89 and both 23 and 89 have order 11.

Table of n, a(n) for n = 1..1206
Eric Weisstein's World of Mathematics, Zsigmondy Theorem

Cf. A046800, A046051 (number of prime factors, with repetition, of 2^n-1), A086252, A002588, A005420, A002184, A046801, A049093, A049094, A059499, A085021, A097406, A112927, A237043.

Join[{0}, Table[cnt=0; f=Transpose[FactorInteger[2^n-1]][[1]]; Do[If[MultiplicativeOrder[2, f[[i]]]==n, cnt++ ], {i, Length[f]}]; cnt, {n, 2, 200}]]

a(n) = sumdiv(n, d, moebius(n/d)*omega(2^d-1)); \\ Michel Marcus, Sep 12 2017

a(n) = my(m=polcyclo(n, 2)); omega(m/gcd(m,n)) \\ Jeppe Stig Nielsen, Sep 01 2020

a(n) = Sum{d|n} mu(n/d) A046800(d), inverse Mobius transform of A046800.
a(n) <= A182590(n). - Thomas Ordowski, Sep 14 2017
a(n) = A001221(A064078(n)). - Thomas Ordowski, Oct 26 2017

Terms to a(500) in b-file from T. D. Noe, Nov 11 2010
Terms a(501)-a(1200) in b-file from Charles R Greathouse IV, Sep 14 2017
Terms a(1201)-a(1206) in b-file from Max Alekseyev, Sep 11 2022

A024222 Number of shuffles (perfect faro shuffles with cut) required to return a deck of size n to its original order.

Original entry on oeis.org

0, 1, 2, 2, 4, 4, 3, 3, 6, 6, 10, 10, 12, 12, 4, 4, 8, 8, 18, 18, 6, 6, 11, 11, 20, 20, 18, 18, 28, 28, 5, 5, 10, 10, 12, 12, 36, 36, 12, 12, 20, 20, 14, 14, 12, 12, 23, 23, 21, 21, 8, 8, 52, 52, 20, 20, 18, 18, 58, 58, 60, 60, 6, 6, 12, 12, 66, 66, 22, 22, 35, 35, 9, 9, 20, 20

Offset: 1

Enoch Haga

			a(52)=8: a deck of size 52 returns to its original order in 8 perfect faro shuffles.

Martin Gardner, "Card Shuffles," Mathematical Carnival chapter 10, pp. 123-138. New York: Vintage Books, 1977.
S. Brent Morris, Magic Tricks, Card Shuffling and Dynamic Computer Memories, Math. Assoc. Am., 1998, p. 107.

Tim Folger, Shuffling Into Hyperspace, Discover, 1991 (vol. 12, no. 1), pp. 66-67.
Roger K. W. Hui, Sixteen APL Amuse-Bouches, Vector (2016) Vol. 26, No. 4, 54-66. Art No. 10501480.

A002326 is really the fundamental sequence for this problem. Cf. A024542.

A002326 := proc(n)
    if n =0 then
        1;
    else
        numtheory[order](2,2*n+1) ;
    end if;
end proc:
A024222 := proc(n)
    if n <= 1 then
        n-1 ;
    else
        A002326(floor((n-1)/2)) ;
    end if;
end proc: # R. J. Mathar, Nov 14 2018

A002326 [n_] := If[n == 0, 1, MultiplicativeOrder[2, 2n+1]];
A024222[n_] := If[n <= 1 , n-1, A002326[Floor[(n-1)/2]]];
Table[A024222[n], {n, 1, 76}] (* Jean-François Alcover, May 05 2023, after R. J. Mathar *)

cp's OEIS Frontend

A053451 Multiplicative order of 8 mod 2n+1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Magma

Mathematica

PARI

A143663 a(n) is the least prime such that the multiplicative order of 3 mod a(n) equals n, or a(n)=1 if no such prime exists.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A201908 Irregular triangle of 2^k mod (2n-1).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Mathematica

Formula

A216838 Odd primes for which 2 is not a primitive root.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Extensions

A036259 Numbers k such that the multiplicative order of 2 modulo k is odd.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

A070677 Smallest m in range 1..phi(n) such that 5^m == 1 mod n, or 0 if no such number exists.

Views

Author

Keywords

Crossrefs

Programs

Magma

Mathematica

Python

A070682 Smallest m in range 1..phi(2n+1) such that 10^m == 1 mod 2n+1, or 0 if no such number exists.

Views

Author

Keywords

Crossrefs

Programs

PARI

A070683 Smallest m in range 1..phi(2n+1) such that 12^m == 1 mod 2n+1, or 0 if no such number exists.