A216838 -id:A216838 - cp's OEIS frontend

A002326 Multiplicative order of 2 mod 2n+1.

1, 2, 4, 3, 6, 10, 12, 4, 8, 18, 6, 11, 20, 18, 28, 5, 10, 12, 36, 12, 20, 14, 12, 23, 21, 8, 52, 20, 18, 58, 60, 6, 12, 66, 22, 35, 9, 20, 30, 39, 54, 82, 8, 28, 11, 12, 10, 36, 48, 30, 100, 51, 12, 106, 36, 36, 28, 44, 12, 24, 110, 20, 100, 7, 14, 130, 18, 36, 68, 138, 46, 60, 28

Offset: 0

N. J. A. Sloane

In other words, least m > 0 such that 2n+1 divides 2^m-1.
Number of riffle shuffles of 2n+2 cards required to return a deck to initial state. A riffle shuffle replaces a list s(1), s(2), ..., s(m) with s(1), s((i/2)+1), s(2), s((i/2)+2), ... a(1) = 2 because a riffle shuffle of [1, 2, 3, 4] requires 2 iterations [1, 2, 3, 4] -> [1, 3, 2, 4] -> [1, 2, 3, 4] to restore the original order.
Concerning the complexity of computing this sequence, see for example Bach and Shallit, p. 115, exercise 8.
It is not difficult to prove that if 2n+1 is a prime then 2n is a multiple of a(n). But the converse is not true. Indeed, one can prove that a(2^(2t-1))=4t. Thus if n=2^(2t-1), where, for any m > 0, t=2^(m-1) then 2n is a multiple of a(n) while 2n+1 is a Fermat number which, as is well known, is not always a prime. It is an interesting problem to describe all composite numbers for which 2n is divisible by a(n). - Vladimir Shevelev, May 09 2008
For an algorithm of calculation of a(n) see author's comment in A179680. - Vladimir Shevelev, Jul 21 2010
From V. Raman, Sep 18 2012, Dec 10 2012: (Start)
If 2n+1 is prime, then the polynomial (x^(2n+1)+1)/(x+1) factors into 2n/a(n) polynomials of the same degree a(n) over GF(2).
If (x^(2n+1)+1)/(x+1) is irreducible over GF(2), then 2n+1 is prime, and 2 is a primitive root (mod 2n+1) (cf. A001122).
For all n > 0, a(n) is the degree of the largest irreducible polynomial factor for the polynomial (x^(2n+1)+1)/(x+1) over GF(2). (End)
a(n) is a factor of phi(2n+1) (A000010(2n+1)). - Douglas Boffey, Oct 21 2013
Conjecture: if p is an odd prime then a((p^3-1)/2) = p * a((p^2-1)/2). Because otherwise a((p^3-1)/2) < p * a((p^2-1)/2) iff a((p^3-1)/2) = a((p-1)/2) for a prime p. Equivalently p^3 divides 2^(p-1)-1, but no such prime p is known. - Thomas Ordowski, Feb 10 2014
A generalization of the previous conjecture: For each k>=2, if p is an odd prime then a(((p^(k+1))-1)/2) = p * a((p^k-1)/2). Computer testing of this generalized conjecture shows that there is no counterexample for k and p both up to 1000. - Ahmad J. Masad, Oct 17 2020
a(n) = a((N-1)/2), with odd N = 2*n+1 >= 3 (n >= 1), is also the primitive period length of (1/N) in binary notation: (1/N)2 = 0.repeat(a[1]a[2]...a[P(N)]), and P(N) = a((N-1)/2). E.g., N = 11 (n = 5), (1/11)_2 = 0.repeat(0001011101), with P(11) = 10 = a(5). Proof: Use a cyclic shift operation sigma (1 step to the left) on the cycle: sigma((1/N)_2) = .repeat(a[2]...a[P(N)]a[1]). Then one can prove for the composition sigma^[k] (k=0 is the identity map) written back in decimal notation the result (sigma^[k]((1/N)_2))_10 = (1/N)*2^k (mod N). E.g. N = 11, sigma^[2]((1/11)_2) = .repeat(0101110100), written in base 10 as 4/11, etc. Hence P(N) and the order of 2 modulo N coincide. - _Gary W. Adamson and Wolfdieter Lang, Oct 14 2020

			From _Vladimir Shevelev_, Oct 03 2017: (Start)
Our algorithm for the calculation of a(n) in the author's comment in A179680 (see also the Sage program below) could be represented in the form of a "finite continued fraction". For example let n = 8, 2*n+1 = 17. We have
    1 + 17
    ------- + 17
       2
    ------------- + 17
           2
    ------------------- + 17
              2
    -------------------------- = 1
                 32
Here the denominators are the A006519 of the numerators: A006519(1+17) = 2, A006519(9+17) = 2, A006519(13+17) = 2, A006519(15+17) = 32. Summing the exponents of these powers of 2, we obtain the required result: a(8) = 1 + 1 + 1 + 5 = 8. Indeed, we have (((1*32 - 17)*2 - 17)*2 - 17)*2 - 17 = 1. So 32*2*2*2 - 1 == 0 (mod 17), 2^8 - 1 == 0 (mod 17). In the general case, note that all "partial fractions" (which indeed are integers) are odd residues modulo 2*n+1 in the interval [1, 2*n-1]. It is easy to prove that the first 1 appears not later than in the n-th step. (End)

E. Bach and Jeffrey Shallit, Algorithmic Number Theory, I.
T. Folger, "Shuffling Into Hyperspace," Discover, 1991 (vol 12, no 1), pages 66-67.
M. Gardner, "Card Shuffles," Mathematical Carnival chapter 10, pages 123-138. New York: Vintage Books, 1977.
L. Lunelli and M. Lunelli, Tavola di congruenza a^n == 1 mod K per a=2,5,10, Atti Sem. Mat. Fis. Univ. Modena 10 (1960/61), 219-236 (1961).
J. H. Silverman, A Friendly Introduction to Number Theory, 3rd ed., Pearson Education, Inc, 2006, p. 146, Exer. 21.3
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 = 0..10000
Jean-Paul Allouche, Manon Stipulanti, and Jia-Yan Yao, Doubling modulo odd integers, generalizations, and unexpected occurrences, arXiv:2504.17564 [math.NT], 2025.
M. Baake, U. Grimm and J. Nilsson, Scaling of the Thue-Morse diffraction measure, arXiv preprint arXiv:1311.4371 [math-ph], 2013.
D. Bayer and P. Diaconis, Trailing the dovetail shuffle to its lair, Ann. Appl. Prob. 2 (2) (1992) 294-313.
Matthew Brand, Choosing 1 of N with and without lucky numbers, arXiv:1808.07994 [math.NT], 2018.
J. Brillhart, J. S. Lomont and P. Morton, Cyclotomic properties of the Rudin-Shapiro polynomials, J. Reine Angew. Math.288 (1976), 37--65. See Table 2. MR0498479 (58 #16589).
Steve Butler, Persi Diaconis and R. L. Graham, The mathematics of the flip and horseshoe shuffles, arXiv:1412.8533 [math.CO], 2014.
Steve Butler, Persi Diaconis and R. L. Graham, The mathematics of the flip and horseshoe shuffles, The American Mathematical Monthly 123.6 (2016): 542-556.
A. J. C. Cunningham, On Binal Fractions, Math. Gaz., 4 (71) (1908), circa p. 266.
P. Diaconis, R. L. Graham, and W. M. Kantor, The mathematics of perfect shuffles, Adv. Appl. Math. 4 (2) (1983) 175-196
M. J. Gardner and C. A. McMahan, Riffling casino checks, Math. Mag., 50 (1) (1977), 38-41.
S. W. Golomb, Permutations by cutting and shuffling, SIAM Rev., 3 (1961), 293-297.
Jonas Kaiser, On the relationship between the Collatz conjecture and Mersenne prime numbers, arXiv preprint arXiv:1608.00862 [math.GM], 2016.
Torleiv Klove, On covering sets for limited-magnitude errors, Cryptogr. Commun. 8 (3) (2016) 415-433
V. I. Levenshtein, Conflict-avoiding codes and cyclic triple systems [in Russian], Problemy Peredachi Informatsii, 43 (No. 3, 2007), 39-53.
V. I. Levenshtein, Conflict-avoiding codes and cyclic triple systems, Problems of Information Transmission, September 2007, Volume 43, Issue 3, pp 199-212 (translated from Russian)
Yuan-Hsun Lo, Kenneth W. Shum, Wing Shing Wong and Yijin Zhang, Multichannel Conflict-Avoiding Codes of Weights Three and Four, arXiv:2009.11754 [cs.IT], 2020.
Jarkko Peltomäki and Aleksi Saarela, Standard words and solutions of the word equation X_1^2 ... X_n^2 = (X_1 ... X_n)^2, Journal of Combinatorial Theory, Series A (2021) Vol. 178, 105340. See also arXiv:2004.14657 [cs.FL], 2020.
Vladimir Shevelev, Gilberto Garcia-Pulgarin, Juan Miguel Velasquez-Soto and John H. Castillo, Overpseudoprimes, and Mersenne and Fermat numbers as primover numbers, arXiv preprint arXiv:1206:0606 [math.NT], 2012.
Vladimir Shevelev, G. Garcia-Pulgarin, J. M. Velasquez and J. H. Castillo, Overpseudoprimes, and Mersenne and Fermat Numbers as Primover Numbers, J. Integer Seq. 15 (2012) Article 12.7.7.
Eric Weisstein's World of Mathematics, Riffle Shuffle
Eric Weisstein's World of Mathematics, In-Shuffle
Eric Weisstein's World of Mathematics, Out-Shuffle
Eric Weisstein's World of Mathematics, Multiplicative Order
Wikipedia, Riffle Shuffle

Cf. A003571, A003573, A217469, A070667-A070683, A053447, A053451, A292239, A292265.
Cf. A024222, A006694 (number of cyclotomic cosets).
Cf. A014664 (order of 2 mod n-th prime).
Cf. A001122 (primes for which 2 is a primitive root).
Cf. A216838 (primes for which 2 is not a primitive root).
Cf. A000010, A000225, A005420, A006519, A007733, A025192, A048675, A056239, A179680.
Bisections give A274298, A274299.
Partial sums: A359147.

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

import Data.List (findIndex)
import Data.Maybe (fromJust)
a002326 n = (+ 1) $ fromJust $
            findIndex ((== 0) . (`mod` (2 * n + 1))) $ tail a000225_list
-- Reinhard Zumkeller, Apr 22 2013

[ 1 ] cat [ Modorder(2, 2*n+1): n in [1..72] ]; // Klaus Brockhaus, Dec 03 2008

a := n -> `if`(n=0, 1, numtheory:-order(2, 2*n+1)):
seq(a(n), n=0..72);

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

a(n)=if(n<0,0,znorder(Mod(2,2*n+1))) /* Michael Somos, Mar 31 2005 */

from sympy import n_order
[n_order(2, 2*n+1) for n in range(73)] # Hermann Stamm-Wilbrandt, Jul 27 2021

# From Peter Luschny, Oct 06 2017: (Start)
[Mod(2,n).multiplicative_order() for n in (0..145) if gcd(n,2) == 1]
# Algorithm from Vladimir Shevelev as described in A179680 and presented in Example.
def A002326VS(n):
    s, m, N = 0, 1, 2*n + 1
    while True:
        k = N + m
        v = valuation(k, 2)
        s += v
        m = k >> v
        if m == 1: break
    return s
[A002326VS(n) for n in (0..72)] # (End)

a((3^n-1)/2) = A025192(n). - Vladimir Shevelev, May 09 2008
Bisection of A007733: a(n) = A007733(2*n+1). - Max Alekseyev, Jun 11 2009
a((b(n)-1)/2) = n for odd n and even n such that b(n/2) != b(n), where b(n) = A005420(n). - Thomas Ordowski, Jan 11 2014
Note that a(2^n-1) = n+1 and a(2^n) = 2*(n+1). - Thomas Ordowski, Jan 16 2014
a(n) = A056239(A292239(n)) = A048675(A292265(n)). - Antti Karttunen, Oct 04 2017

More terms from David W. Wilson, Jan 13 2000

More terms from Benoit Cloitre, Apr 11 2003

A001122 Primes with primitive root 2.

Original entry on oeis.org

3, 5, 11, 13, 19, 29, 37, 53, 59, 61, 67, 83, 101, 107, 131, 139, 149, 163, 173, 179, 181, 197, 211, 227, 269, 293, 317, 347, 349, 373, 379, 389, 419, 421, 443, 461, 467, 491, 509, 523, 541, 547, 557, 563, 587, 613, 619, 653, 659, 661, 677, 701, 709, 757, 773, 787, 797

Offset: 1

N. J. A. Sloane

Artin conjectured that this sequence is infinite.
Conjecture: sequence contains infinitely many pairs of twin primes. - Benoit Cloitre, May 08 2003
Pieter Moree writes (Oct 20 2004): Assuming the Generalized Riemann Hypothesis, it can be shown that the density of primes p such that a prescribed integer g has order (p-1)/t, with t fixed, exists and, moreover, it can be computed. This density will be a rational number times the so-called Artin constant. For 2 and 10 the density of primitive roots is A, the Artin constant itself.
It seems that this sequence consists of A050229 \ {1,2}.
Primes p such that 1/p, when written in base 2, has period p-1, which is the greatest period possible for any integer.
Positive integer 2*m-1 is in the sequence iff A179382(m)=m-1. - Vladimir Shevelev, Jul 14 2010
These are the odd primes p for which the polynomial 1+x+x^2+...+x^(p-1) is irreducible over GF(2). - V. Raman, Sep 17 2012 [Corrected by N. J. A. Sloane, Oct 17 2012]
Prime(n) is in the sequence if (and conjecturally only if) A133954(n) = prime(n). - Vladimir Shevelev, Aug 30 2013
Pollack shows that, on the GRH, that there is some C such that a(n+1) - a(n) < C infinitely often (in fact, 1 can be replaced by any positive integer). Further, for any m, a(n), a(n+1), ..., a(n+m) are consecutive primes infinitely often. - Charles R Greathouse IV, Jan 05 2015
From Jianing Song, Apr 27 2019: (Start)
All terms are congruent to 3 or 5 modulo 8. If we define
  Pi(N,b) = # {p prime, p <= N, p == b (mod 8)};
     Q(N) = # {p prime, p <= N, p in this sequence},
then by Artin's conjecture, Q(N) ~ C*N/log(N) ~ 2*C*(Pi(N,3) + Pi(N,5)), where C = A005596 is Artin's constant.
Conjecture: if we further define
   Q(N,b) = # {p prime, p <= N, p == b (mod 8), p in this sequence},
then we have:
   Q(N,3) ~ (1/2)*Q(N) ~ C*Pi(N,3);
   Q(N,5) ~ (1/2)*Q(N) ~ C*Pi(N,5). (End)
Conjecture: for a prime p > 5, p has primitive root 2 iff p == +-3 (mod 8) divides 2^k + 3 for some k < p - 1 and divides 2^m + 5 for some m < p - 1. It seems that all primes of the form 2^k + 3 for k <> 2 (A057732) have primitive root 2. - Thomas Ordowski, Nov 27 2023

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 864.
E. Bach and Jeffrey Shallit, Algorithmic Number Theory, I; see p. 221.
J. H. Conway and R. K. Guy, The Book of Numbers, Copernicus Press, New York, 1996; see p. 169.
M. Kraitchik, Recherches sur la Théorie des Nombres. Gauthiers-Villars, Paris, Vol. 1, 1924, Vol. 2, 1929, see Vol. 1, p. 56.
Lehmer, D. H. and Lehmer, Emma; Heuristics, anyone? in Studies in mathematical analysis and related topics, pp. 202-210, Stanford Univ. Press, Stanford, Calif., 1962.
Paulo Ribenboim, The Little Book of Bigger Primes, Springer-Verlag NY 2004. See p. 20.
D. Shanks, Solved and Unsolved Problems in Number Theory, 2nd. ed., Chelsea, 1978, p. 81.
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).

Antti Karttunen, Table of n, a(n) for n = 1..10000 (first 1000 terms from T. D. Noe)
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
Joerg Arndt, Matters Computational (The Fxtbook), pp. 876-878.
Richard Bartels, Generalized Loewy Length of Cohen-Macaulay Local and Graded Rings, arXiv:2308.14932 [math.AC], 2023. See p. 10.
J. Conde, M. Miller, J. M. Miret, and K. Saurav, On the Nonexistence of Almost Moore Digraphs of Degree Four and Five, Mathematics in Computer Science, 9(2) (2015), 145-149.
Jonathan Detchart and Jérôme Lacan, Improving the coding speed of erasure codes with polynomial ring transforms, arXiv:1709.00178 [cs.IT], 2017.
K. Dilcher and L. Ericksen, Reducibility and irreducibility of Stern (0, 1)-polynomials, Communications in Mathematics, 22 (2014), 77-102.
Gabriele Fici and Estéban Gabory, Generalized De Bruijn Words, Invertible Necklaces, and the Burrows-Wheeler Transform, arXiv:2502.12844 [math.CO], 2025. See p. 12.
R. Gupta and M. R. Murty, A remark on Artin's conjecture, Invent. Math. 78 (1984), 127-230.
C. Hooley, On Artin's conjecture, J. Reine Angewandte Math., 225 (1967), 209-220.
Florian Ingels, Anaïs Denis, and Bastien Cazaux, Decomposing Words for Enhanced Compression: Exploring the Number of Runs in the Extended Burrows-Wheeler Transform, arXiv:2506.04926 [cs.DS], 2025. See p. 15.
Robert Jackson, Dmitriy Rumynin and Oleg V. Zaboronski, An approach to RAID-6 based on cyclic groups, Applied Mathematics & Information Sciences, 5(2) (2011), 148-170.
Jonas Kaiser, On the relationship between the Collatz conjecture and Mersenne prime numbers, arXiv:1608.00862 [math.GM], 2016.
Sihem Mesnager and Jean-Pierre Flori, A note on hyper-bent functions via Dillon-like exponents, IACR, Report 2012/033, 2012.
F. Pillichshammer, Bounds for the quality parameter of digital shift nets over Z_2, Finite Fields Applic., 8 (2002), 444-454.
Pieter Moree, Artin's primitive root conjecture-a survey, arXiv:math/0412262 [math.NT], 2004-2012.
Paul Pollack, Bounded gaps between primes with a given primitive root, arXiv:1404.4007 [math.NT], 2014.
Vladimir Shevelev, On the Newman sum over multiples of a prime with a primitive or semiprimitive root 2, arXiv:0710.1354 [math.NT], 2007.
Stephan Tornier, Groups Acting on Trees With Prescribed Local Action, arXiv:2002.09876 [math.GR], 2020.
Qifu Tyler Sun, Hanqi Tang, Zongpeng Li, Xiaolong Yang, and Keping Long, Circular-shift Linear Network Codes with Arbitrary Odd Block Lengths, arXiv:1806.04635 [cs.IT], 2018.
Eric Weisstein's World of Mathematics, Artin's constant.
Wikipedia, Artin's conjecture on primitive roots.
Index entries for sequences related to Artin's conjecture
Index entries for primes by primitive root

Cf. A001123, A001913, A001917, A005596 (Artin's constant), A050229, A071642, A127209, A163782, A292270.
Cf. A002326 for the multiplicative order of 2 mod 2n+1. (Alternatively, the least positive value of m such that 2n+1 divides 2^m-1).
Cf. A216838 (Odd primes for which 2 is not a primitive root).

Select[ Prime@Range@200, PrimitiveRoot@# == 2 &] (* Robert G. Wilson v, May 11 2001 *)
pr = 2; Select[Prime[Range[200]], MultiplicativeOrder[pr, # ] == # - 1 &] (* N. J. A. Sloane, Jun 01 2010 *)

forprime(p=3, 1000, if(znorder(Mod(2, p))==(p-1), print1(p,", "))); \\ [corrected by Michel Marcus, Oct 08 2014]

from itertools import islice
from sympy import nextprime, is_primitive_root
def A001122_gen(): # generator of terms
    p = 2
    while (p:=nextprime(p)):
        if is_primitive_root(2,p):
            yield p
A001122_list = list(islice(A001122_gen(),30)) # Chai Wah Wu, Feb 13 2023

Delta(a(n),2^a(n)*x) = a(n)*Delta(a(n),2*x), where Delta(k,x) is the difference between numbers of evil(A001969) and odious(A000069) integers divisible by k in interval [0,x). - Vladimir Shevelev, Aug 30 2013

For n >= 2, a(n) = 1 + 2*A163782(n-1). - Antti Karttunen, Oct 07 2017

A115586 Prime moduli p for which 2 is neither a quadratic residue nor a primitive root.

Original entry on oeis.org

43, 109, 157, 229, 251, 277, 283, 307, 331, 397, 499, 571, 643, 683, 691, 733, 739, 811, 971, 997, 1013, 1021, 1051, 1069, 1093, 1163, 1181, 1429, 1459, 1579, 1597, 1613, 1627, 1699, 1709, 1723, 1789, 1811, 1933, 2003, 2011, 2179, 2203, 2251

Offset: 1

Don Reble, Mar 11 2006

nonn

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

Cf. A001122, A001132, A001133, A003629.

Intersection of A216838 and A003629.

select(p -> isprime(p) and numtheory:-order(2,p) <> p-1, [seq(seq(8*i+j,j=[3,5]),i=1..1000)]); # Robert Israel, Apr 02 2018

Select[Prime[Range[400]], MultiplicativeOrder[2, #] != # - 1 && JacobiSymbol[2, #] == -1 &] (* Alonso del Arte, Jun 08 2014 *)

is(n)=n>2&&isprime(n)&&kronecker(2,n)!=1&&znprimroot(n)!=2 \\ Lear Young, Mar 26 2014

A108989 Composite numbers k with primitive root 2; i.e., the order of 2 modulo k is phi(k).

Original entry on oeis.org

9, 25, 27, 81, 121, 125, 169, 243, 361, 625, 729, 841, 1331, 1369, 2187, 2197, 2809, 3125, 3481, 3721, 4489, 6561, 6859, 6889, 10201, 11449, 14641, 15625, 17161, 19321, 19683, 22201, 24389, 26569, 28561, 29929, 32041, 32761, 38809, 44521, 50653

Offset: 1

Douglas Stones (dssto1(AT)student.monash.edu.au), Jul 28 2005

nonn

There exist no even numbers with primitive root 2. All entries are odd. They are all the powers of odd primes. - V. Raman, Nov 20 2012

			Modulo 9: 2^1 == 2, 2^2 == 4, 2^3 == 8, 2^4 == 7, 2^5 == 5, 2^6 == 1 and phi(9) == 6.

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..100 from Alois P. Heinz)

Intersection of A002808 and A167791.

Cf. A000010, A001122, A002326, A216838, A216848, A219030.

for i in [2..100000] do if not IsPrime(i) then if IsPrimitiveRootMod(2,i) then Display(i); fi; fi; od;

nn=51000; Select[Complement[Range[2, nn], Prime[Range[PrimePi[nn]]]], PrimitiveRoot[#] == 2&] (* Harvey P. Dale, Jul 25 2011 *)
seq[max_] := Module[{ps = Select[Range[2, Floor[Sqrt[max]]], PrimeQ], s = {}}, Do[s = Join[s, Select[p^Range[2, Floor[Log[p, max]]], PrimitiveRoot[#] == 2 &]], {p, ps}]; Sort[s]]; seq[10^5] (* Amiram Eldar, Nov 10 2023 *)

for(n=3,100000,if(n%2==1&&isprime(n)==0&&znorder(Mod(2,n))==eulerphi(n),print1(n","))) /* V. Raman, Nov 20 2012 */

A216848 Odd numbers for which 2 is not a primitive root.

Original entry on oeis.org

7, 15, 17, 21, 23, 31, 33, 35, 39, 41, 43, 45, 47, 49, 51, 55, 57, 63, 65, 69, 71, 73, 75, 77, 79, 85, 87, 89, 91, 93, 95, 97, 99, 103, 105, 109, 111, 113, 115, 117, 119, 123, 127, 129, 133, 135, 137, 141, 143, 145, 147, 151, 153, 155, 157, 159, 161, 165, 167

Offset: 1

V. Raman, Sep 17 2012

nonn

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

Cf. A002326, A001122, A216838.

nn = 200; Select[Range[3, nn, 2], PrimitiveRoot[#] =!= 2 &] (* T. D. Noe, Sep 19 2012 *)

forstep(p=3, 200, 2, if(znorder(Mod(2, p))!=eulerphi(p), print(p)))

A091669 a(n) = (2^(n-1)/n!) * Product_{k=1..n-1} (2^k-1).

Original entry on oeis.org

1, 1, 2, 7, 42, 434, 7812, 248031, 14055090, 1436430198, 267176016828, 91151551074486, 57425477176926180, 67196011936600334340, 146782968474309770332296, 601204690999713530559792879

Offset: 1

Karol A. Penson, Jan 27 2004

nonn

Primes p such that 2^p-2 divides a(p) are A216838. - Amiram Eldar and Thomas Ordowski, Jan 16 2020
For odd n > 1, if a(n-1) divides a(n) and n does not divide a(n), then n is a prime (for which 2 is a primitive root, A001122). Composite numbers m such that a(m-1) divides a(m) are the pseudoprimes A001567 and A006935. Numbers n > 1 such that a(m) divides a(n) for all m < n are primes 2, 3, 5, 7, and 13. These are the primes p for which gpf(2^p-2) = p. - Thomas Ordowski, Jan 17 2020
If p is a prime with primitive root 2, A001122, then p | a(p-1) + 2^(p-2). Conjecture: (for n > 2), if n | a(n-1) + 2^(n-2), then n is a prime (A001122). Note that if p is an odd prime for which 2 is not a primitive root, A216838, then p | a(p-1). - Amiram Eldar and Thomas Ordowski, Jan 19 2020

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

Cf. A000142, A001122, A001567, A005329, A006935, A159353, A216838, A225101.

[1] cat [2^(n-1)/Factorial(n)*&*[(2^k-1):k in [1..n-1]]:n in [2..16]]; // Marius A. Burtea, Jan 16 2020

seq( (2^(n-1)/n!)*mul(2^j-1, j=1..n-1), n=1..20); # G. C. Greubel, Feb 05 2020

Table[QFactorial[n-1, 2] 2^(n-1)/n!, {n, 20}]

a(n) = (2^(n-1)/n!) * prod(k=1, n-1, 2^k-1); \\ Michel Marcus, Jan 16 2020

from sage.combinat.q_analogues import q_factorial
[2^(n-1)*q_factorial(n-1, 2)/factorial(n) for n in (1..20)] # G. C. Greubel, Feb 05 2020

a(n) = 2^(n-1)*A005329(n-1)/n!.

a(n) = Product_{k=2..n} (2^k-2)/k = Product_{k=2..n} A225101(k)/A159353(k). - Thomas Ordowski, Jan 16 2020

Corrected and edited by Thomas Ordowski, Jan 16 2020

A217460 Odd values of n such that the polynomial 1+x+x^2+...+x^(n-1) is reducible over GF(2).

Original entry on oeis.org

7, 9, 15, 17, 21, 23, 25, 27, 31, 33, 35, 39, 41, 43, 45, 47, 49, 51, 55, 57, 63, 65, 69, 71, 73, 75, 77, 79, 81, 85, 87, 89, 91, 93, 95, 97, 99, 103, 105, 109, 111, 113, 115, 117, 119, 121, 123, 125, 127, 129, 133, 135, 137, 141, 143, 145, 147, 151, 153, 155, 157, 159, 161, 165, 167, 169, 171, 175, 177, 183, 185, 187, 189, 191, 193, 195, 199

Offset: 1

V. Raman, Oct 04 2012

nonn

This sequence is the union of the odd composite numbers and the primes for which 2 is not a primitive root.

Vincenzo Librandi, Table of n, a(n) for n = 1..1000

Cf. A002326, A001122, A216838.

nn = 200; Union[Select[Range[3, nn, 2], ! PrimeQ[#] &], Select[Prime[Range[2, PrimePi[nn]]], PrimitiveRoot[#] =!= 2 &]] (* T. D. Noe, Sep 19 2012 *)

for(i=4, 200, if(isprime(i), if(znorder(Mod(2,i))!=(i-1), print(i)), if(i%2==1, print(i))))

for(i=0, 200, i++; if(matsize(factormod((x^i+1)/(x+1), 2, 1))[1]>1, print(i)))

A242595 a(n) is the primitive period length for the sequence 2^k (mod n), k = 1, 2, ...

Original entry on oeis.org

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

Offset: 1

Wolfdieter Lang, May 18 2014

The computation of this sequence was inspired by Gary Detlefs's May 15 2014 comment on A050229.
It is clear that 2^k (mod 4*m), for k >= 1 is not periodic because otherwise 4*m would divide 2^k*(2^P - 1) for all k >= 1, with P >= 1 the period length. But this is false for k = 1. Therefore, a(4*m) = 0.
a(2*(2*m+1)) = a(2*m+1), m = (0), 1, 2, ... because 2*(2*m+1) has to divide 2^k*(2^a(2*(2*m+1) - 1) for each k >= 1, which means that (2*m+1) has to divide (2^a(2*(2*m+1)) - 1), and a(2*(2*m+1)) has to be the smallest such number. But the smallest number P such that (2*m+1) divides (2^P - 1) is P = a(2*m+1).
a(prime) = phi(prime) = prime - 1 (phi is given in A000010) is equivalent to: prime divides 2^k*(2^(prime-1) - 1), for all k >= 1, and prime-1 is the smallest exponent. For the even prime 2 this is trivial, and for an odd prime p this means that p divides 2^phi(prime) - 1, but not with a smaller exponent; that is 2 is a primitive root modulo this odd p. See A001122 for the primes with primitive root 2. This means that a(prime) = prime - 1 exactly for 2 and the odd primes of A001122. The odd primes with no primitive root 2 are given in A216838.
For composite odd numbers m one has: m divides (2^a(m) - 1) with the smallest such a(m).

			a(1) = 1 because 2^1 == 0 == 1 (mod 1), therefore 2^k (mod 1) is the 0-sequence with primitive period length 1.
a(2) = 1 because 2^k == 0 (mod 2) for k >= 1, hence also the 0-sequence with primitive period length 1. Note that 2 is not a primitive root of 2 even though a(2) = 2-1 = 1 (see the comment above).
a(3) = 3-1 = 2 because 3 is odd and 2 is a primitive root modulo 3. See A001122(1).
a(7) = 3 because the sequence 2^k (mod 7) starts 2, 4, 1, ... therefore the primitive period is 2, 4, 1 of length 3, because 2^(k+3) = 2^k*8 == 2^k*1 (mod 7) == 2^k (mod 7) for all k >= 1. The prime 7 belongs to A216838.
a(4) = 0 because a(4*m) = 0 for all m >= 1 (see the comment above).
a(6) = 2 because the sequence starts with 2, 4, 2, ... and
  6 = 2*3 divides 2^k*(2^2 - 1) = 2^k*3 for all k >= 1. That is a(6) = a(3); see a comment above.
a(9) = 6 from the sequence start 2, 4, 8, 7, 5, 1,... Note that a(3^2) = (3-1)*3. a(5^2) = 20 = (4-1)*5. But a(7^2) = 21 = (7-1)*7/2.

Cf. A000010, A050229, A060749, A001122, A216838.

a(n) is the primitive (smallest) period length of the sequence 2^k (mod n), for k >=1, and n >= 1.

cp's OEIS Frontend

A002326 Multiplicative order of 2 mod 2n+1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Haskell

Magma

Maple

Mathematica

PARI

Python

Sage

Formula

Extensions

A001122 Primes with primitive root 2.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A115586 Prime moduli p for which 2 is neither a quadratic residue nor a primitive root.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A108989 Composite numbers k with primitive root 2; i.e., the order of 2 modulo k is phi(k).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Mathematica

PARI

A216848 Odd numbers for which 2 is not a primitive root.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

A091669 a(n) = (2^(n-1)/n!) * Product_{k=1..n-1} (2^k-1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Formula

Extensions