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