login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001122 Primes with primitive root 2.
(Formerly M2473 N0981)
140

%I M2473 N0981 #263 Jan 20 2024 09:05:23

%S 3,5,11,13,19,29,37,53,59,61,67,83,101,107,131,139,149,163,173,179,

%T 181,197,211,227,269,293,317,347,349,373,379,389,419,421,443,461,467,

%U 491,509,523,541,547,557,563,587,613,619,653,659,661,677,701,709,757,773,787,797

%N Primes with primitive root 2.

%C Artin conjectured that this sequence is infinite.

%C Conjecture: sequence contains infinitely many pairs of twin primes. - _Benoit Cloitre_, May 08 2003

%C 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.

%C It seems that this sequence consists of A050229 \ {1,2}.

%C Primes p such that 1/p, when written in base 2, has period p-1, which is the greatest period possible for any integer.

%C Positive integer 2*m-1 is in the sequence iff A179382(m)=m-1. - _Vladimir Shevelev_, Jul 14 2010

%C 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]

%C Prime(n) is in the sequence if (and conjecturally only if) A133954(n) = prime(n). - _Vladimir Shevelev_, Aug 30 2013

%C 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

%C From _Jianing Song_, Apr 27 2019: (Start)

%C All terms are congruent to 3 or 5 modulo 8. If we define

%C Pi(N,b) = # {p prime, p <= N, p == b (mod 8)};

%C Q(N) = # {p prime, p <= N, p in this sequence},

%C 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.

%C Conjecture: if we further define

%C Q(N,b) = # {p prime, p <= N, p == b (mod 8), p in this sequence},

%C then we have:

%C Q(N,3) ~ (1/2)*Q(N) ~ C*Pi(N,3);

%C Q(N,5) ~ (1/2)*Q(N) ~ C*Pi(N,5). (End)

%C 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

%D 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.

%D E. Bach and Jeffrey Shallit, Algorithmic Number Theory, I; see p. 221.

%D J. H. Conway and R. K. Guy, The Book of Numbers, Copernicus Press, New York, 1996; see p. 169.

%D M. Kraitchik, Recherches sur la Théorie des Nombres. Gauthiers-Villars, Paris, Vol. 1, 1924, Vol. 2, 1929, see Vol. 1, p. 56.

%D 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.

%D D. Shanks, Solved and Unsolved Problems in Number Theory, 2nd. ed., Chelsea, 1978, p. 81.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Antti Karttunen, <a href="/A001122/b001122.txt">Table of n, a(n) for n = 1..10000</a> (first 1000 terms from T. D. Noe)

%H M. Abramowitz and I. A. Stegun, eds., <a href="http://www.convertit.com/Go/ConvertIt/Reference/AMS55.ASP">Handbook of Mathematical Functions</a>, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].

%H Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, pp. 876-878.

%H Richard Bartels, <a href="https://arxiv.org/abs/2308.14932">Generalized Loewy Length of Cohen-Macaulay Local and Graded Rings</a>, arXiv:2308.14932 [math.AC], 2023. See p. 10.

%H J. Conde, M. Miller, J. M. Miret, and K. Saurav, <a href="https://doi.org/10.1007/s11786-015-0219-z">On the Nonexistence of Almost Moore Digraphs of Degree Four and Five</a>, Mathematics in Computer Science, 9(2) (2015), 145-149.

%H Jonathan Detchart and Jérôme Lacan, <a href="https://arxiv.org/abs/1709.00178">Improving the coding speed of erasure codes with polynomial ring transforms</a>, arXiv:1709.00178 [cs.IT], 2017.

%H K. Dilcher and L. Ericksen, <a href="https://dml.cz/handle/10338.dmlcz/143908">Reducibility and irreducibility of Stern (0, 1)-polynomials</a>, Communications in Mathematics, 22 (2014), 77-102.

%H R. Gupta and M. R. Murty, <a href="http://www.mast.queensu.ca/~murty/gupta-murty.pdf">A remark on Artin's conjecture</a>, Invent. Math. 78 (1984), 127-230.

%H C. Hooley, <a href="http://gdz.sub.uni-goettingen.de/dms/resolveppn/?PPN=GDZPPN002182270">On Artin's conjecture</a>, J. Reine Angewandte Math., 225 (1967), 209-220.

%H Robert Jackson, Dmitriy Rumynin and Oleg V. Zaboronski, <a href="http://www.naturalspublishing.com/amis/V5-2/5-2-1.pdf">An approach to RAID-6 based on cyclic groups</a>, Applied Mathematics & Information Sciences, 5(2) (2011), 148-170.

%H Jonas Kaiser, <a href="https://arxiv.org/abs/1608.00862">On the relationship between the Collatz conjecture and Mersenne prime numbers</a>, arXiv:1608.00862 [math.GM], 2016.

%H Sihem Mesnager and Jean-Pierre Flori, <a href="https://ia.cr/2012/033">A note on hyper-bent functions via Dillon-like exponents</a>, IACR, Report 2012/033, 2012.

%H F. Pillichshammer, <a href="http://dx.doi.org/10.1006/ffta.2001.0352">Bounds for the quality parameter of digital shift nets over Z_2</a>, Finite Fields Applic., 8 (2002), 444-454.

%H Pieter Moree, <a href="https://arxiv.org/abs/math/0412262">Artin's primitive root conjecture-a survey</a>, arXiv:math/0412262 [math.NT], 2004-2012.

%H Paul Pollack, <a href="http://arxiv.org/abs/1404.4007">Bounded gaps between primes with a given primitive root</a>, arXiv:1404.4007 [math.NT], 2014.

%H Vladimir Shevelev, <a href="http://arxiv.org/abs/0710.1354">On the Newman sum over multiples of a prime with a primitive or semiprimitive root 2</a>, arXiv:0710.1354 [math.NT], 2007.

%H Stephan Tornier, <a href="https://arxiv.org/abs/2002.09876">Groups Acting on Trees With Prescribed Local Action</a>, arXiv:2002.09876 [math.GR], 2020.

%H Qifu Tyler Sun, Hanqi Tang, Zongpeng Li, Xiaolong Yang, and Keping Long, <a href="https://arxiv.org/abs/1806.04635">Circular-shift Linear Network Codes with Arbitrary Odd Block Lengths</a>, arXiv:1806.04635 [cs.IT], 2018.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/ArtinsConstant.html">Artin's constant</a>.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Artin%27s_conjecture_on_primitive_roots">Artin's conjecture on primitive roots</a>.

%H <a href="/index/Ar#Artin">Index entries for sequences related to Artin's conjecture</a>

%H <a href="/index/Pri#primes_root">Index entries for primes by primitive root</a>

%F 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

%F For n >= 2, a(n) = 1 + 2*A163782(n-1). - _Antti Karttunen_, Oct 07 2017

%t Select[ Prime@Range@200, PrimitiveRoot@# == 2 &] (* _Robert G. Wilson v_, May 11 2001 *)

%t pr = 2; Select[Prime[Range[200]], MultiplicativeOrder[pr, # ] == # - 1 &] (* _N. J. A. Sloane_, Jun 01 2010 *)

%o (PARI) forprime(p=3, 1000, if(znorder(Mod(2, p))==(p-1), print1(p,", "))); \\ [corrected by _Michel Marcus_, Oct 08 2014]

%o (Python)

%o from itertools import islice

%o from sympy import nextprime, is_primitive_root

%o def A001122_gen(): # generator of terms

%o p = 2

%o while (p:=nextprime(p)):

%o if is_primitive_root(2,p):

%o yield p

%o A001122_list = list(islice(A001122_gen(),30)) # _Chai Wah Wu_, Feb 13 2023

%Y Cf. A001123, A001913, A001917, A005596 (Artin's constant), A050229, A071642, A127209, A163782, A292270.

%Y 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).

%Y Cf. A216838 (Odd primes for which 2 is not a primitive root).

%K nonn,easy,nice

%O 1,1

%A _N. J. A. Sloane_

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 14:38 EDT 2024. Contains 371254 sequences. (Running on oeis4.)