A001122 -id:A001122 - cp's OEIS frontend

A071642 Numbers n such that x^n + x^(n-1) + x^(n-2) + ... + x + 1 is irreducible over GF(2).

0, 1, 2, 4, 10, 12, 18, 28, 36, 52, 58, 60, 66, 82, 100, 106, 130, 138, 148, 162, 172, 178, 180, 196, 210, 226, 268, 292, 316, 346, 348, 372, 378, 388, 418, 420, 442, 460, 466, 490, 508, 522, 540, 546, 556, 562, 586, 612, 618, 652, 658, 660, 676, 700, 708, 756, 772

Offset: 1

N. J. A. Sloane, Jun 22 2002

All such polynomials of odd degree > 1 are reducible over GF(2).
For n >= 2, a(n) = A001122(n-2) - 1 due to the relationship between cycles and irreducibility. - T. D. Noe, Sep 09 2003
n such that a type-1 optimal normal basis of GF(2^n) (over GF(2)) exists. The corresponding field polynomial is the all-ones polynomial x^n+x^(n-1)+...+1. - Joerg Arndt, Feb 25 2008
From Peter R. J. Asveld, Aug 13 2009: (Start)
a(n) is also the n-th S-prime (Shuffle prime)
For N>=2, the family of shuffle permutations is defined by
p(m,N) = 2m (mod N+1) if N is even,
p(m,N) = 2m (mod N) if N is odd and 1<=mp(N,N) = N if N is odd.
N is S-prime if p(m,N) consists of a single cycle of length N.
So all S-primes are even.
N is S-prime iff p=N+1 is an odd prime number and +2 generates Z_p^* (the multiplicative group of Z_p).
a(n)/2 results in the Josephus_2-primes (A163782). Considered as sets a(n)/2 is the union of A163777 and A163779. If b(n) denotes the dual shuffle primes (A163776), then the union of a(n)/2 and b(n)/2 is equal to the Twist-primes or Queneau numbers (A054639); their intersection is equal to the Archimedes_0-primes (A163777). (End)
Conjecture: Terms >= 2 are numbers n such that P^n + P^(n-1) + P^(n-2) + ... + P + 1 is irreducible over GF(2), where P=x^2+x+1. - Luis H. Gallardo, Dec 23 2019

			For n=4 and n=6 we obtain the permutations (1 2 4 3) and (1 2 4)(3 6 5): 4 is S-prime, but 6 is not. [_Peter R. J. Asveld_, Aug 13 2009]

P. R. J. Asveld, Table of n, a(n) for n = 1..3605
Joerg Arndt, Matters Computational (The Fxtbook), section 42.9 "Gaussian normal bases", pp.914-920
P. R. J. Asveld, Permuting operations on strings and their relation to prime numbers, Discrete Applied Mathematics 159 (2011) 1915-1932.
P. R. J. Asveld, Permuting operations on strings and the distribution of their prime numbers, (2011), TR-CTIT-11-24, Dept. of CS, Twente University of Technology, Enschede, The Netherlands.
P. R. J. Asveld, Some Families of Permutations and Their Primes (2009), TR-CTIT-09-27, Dept. of CS, Twente University of Technology, Enschede, The Netherlands.
P. R. J. Asveld, Permuting Operations on Strings-Their Permutations and Their Primes, Twente University of Technology, 2014.
Hélianthe Caure, Canons rythmiques et pavages modulaires, Thesis Université Pierre et Marie Curie - Paris VI, 2016. See page 108. In French.
H. Caure, C. Agon, and M. Andreatta, Modulus p Rhythmic Tiling Canons and some implementations in Open Music visual programming language, in Proceedings ICMC|SMC|2014 14-20 September 2014, Athens, Greece.
M. Olofsson, VLSI Aspects on Inversion in Finite Fields, Dissertation No. 731, Dept. Elect. Engin., Linkoping, Sweden, 2002.
Eric Weisstein's World of Mathematics, Irreducible Polynomial
Index entries for sequences related to the Josephus Problem

Cf. A001122 (primes with primitive root 2).

Join[{0, 1}, Reap[For[p = 2, p < 10^3, p = NextPrime[p], If[ MultiplicativeOrder[2, p] == p-1, Sow[p-1]]]][[2, 1]]] (* Jean-François Alcover, Dec 10 2015, adapted from PARI *)

forprime(p=3,1000,if(znorder(Mod(2,p))==p-1,print1(p-1,", "))) /* Joerg Arndt, Jul 05 2011 */

Extended by Robert G. Wilson v, Jun 24 2002

Initial terms of b-file corrected by N. J. A. Sloane, Aug 31 2009

A090866 Primes p == 1 (mod 4) such that (p-1)/4 is prime.

Original entry on oeis.org

13, 29, 53, 149, 173, 269, 293, 317, 389, 509, 557, 653, 773, 797, 1109, 1229, 1493, 1637, 1733, 1949, 1997, 2309, 2477, 2693, 2837, 2909, 2957, 3413, 3533, 3677, 3989, 4133, 4157, 4253, 4349, 4373, 4493, 4517, 5189, 5309, 5693, 5717, 5813, 6173, 6197

Offset: 1

Benoit Cloitre, Feb 12 2004

nonn

Same as Chebyshev's subsequence of the primes with primitive root 2, because Chebyshev showed that 2 is a primitive root of all primes p = 4*q+1 with q prime. If the sequence is infinite, then Artin's conjecture ("every nonsquare positive integer n is a primitive root of infinitely many primes q") is true for n = 2. - Jonathan Sondow, Feb 04 2013

Albert H. Beiler: Recreations in the theory of numbers. New York: Dover, (2nd ed.) 1966, p. 102, nr. 5.
P. L. Chebyshev, Theory of congruences. Elements of number theory, Chelsea, 1972, p. 306.

G. C. Greubel, Table of n, a(n) for n = 1..10000
Index entries for sequences related to Artin's conjecture

Cf. A001122, A005385, A005596, A023212, A221981, A222008.

f:=[n: n in [1..2000] | IsPrime(n) and IsPrime(4*n+1)]; [4*f[n] + 1: n in [1..50]]; // G. C. Greubel, Feb 08 2019

Select[Prime[Range[1000]], Mod[#, 4]==1 && PrimeQ[(#-1)/4] &] (* G. C. Greubel, Feb 08 2019 *)

isok(p) = isprime(p) && !frac(q=(p-1)/4) && isprime(q); \\ Michel Marcus, Feb 09 2019

a(n) = 4*A023212(n) + 1.

A216371 Odd primes with one coach: primes p such that A135303((p-1)/2) = 1.

Original entry on oeis.org

3, 5, 7, 11, 13, 19, 23, 29, 37, 47, 53, 59, 61, 67, 71, 79, 83, 101, 103, 107, 131, 139, 149, 163, 167, 173, 179, 181, 191, 197, 199, 211, 227, 239, 263, 269, 271, 293, 311, 317, 347, 349, 359, 367, 373, 379, 383, 389, 419, 421, 443, 461, 463, 467, 479, 487

Offset: 1

Gary W. Adamson, Sep 05 2012

Given that prime p has only one coach, the corresponding value of k in A003558 must be (p-1)/2, and vice versa. Using the Coach theorem of Jean Pedersen et al., phi(b) = 2 * c * k, with b odd. Let b = p, prime. Then phi(p) = (p-1), and k must be (p-1)/2 iff c = 1. Or, phi(p) = (p-1) = 2 * 1 * (p-1)/2.
Conjecture relating to odd integers: iff an integer is in the set A216371 and is either of the form 4q - 1 or 4q + 1, (q>0); then the top row of its coach (cf. A003558) is composed of a permutation of the first q odd integers. Examples: 11 is of the form 4q - 1, q = 3; with the top row of its coach [1, 5, 3]. 13 is of the form 4q + 1, q = 3; so has a coach of [1, 3, 5]. 37 is of the form 4q + 1, q = 9; so has a coach with the top row composed of a permutation of the first 9 odd integers: [1, 9, 7, 15, 11, 13, 3, 17, 5]. - Gary W. Adamson, Sep 08 2012
Odd primes p such that 2^m is not congruent to 1 or -1 (mod p) for 0 < m < (p-1)/2. - Charles R Greathouse IV, Sep 15 2012
These are also the odd primes a(n) for which there is only one periodic Schick sequence (see the reference, and also the Brändli and Beyne link, eq. (2) for the recurrence but using various inputs. See also a comment in A332439). This sequence has primitive period length (named pes in Schick's book) A003558((a(n)-1)/2) = A005034(a(n)) = A000010(a(n))/2 = (a(n) - 1)/2, for n >= 1. - Wolfdieter Lang, Apr 09 2020
From Jianing Song, Dec 24 2022: (Start)
Primes p such that the multiplicative order of 4 modulo p is (p-1)/2. Proof of equivalence: let ord(a,k) be the multiplicative of a modulo k.
If 2^m is not 1 or -1 (mod p) for 0 < m < (p-1)/2, then ord(2,p) is either p-1 or (p-1)/2. If ord(2,p) = p-1, then ord(4,p) = (p-1)/2. If ord(2,p) = (p-1)/2, then p == 3 (mod 4), otherwise 2^((p-1)/4) == -1 (mod p), so ord(4,p) = (p-1)/2.
Conversely, if ord(4,p) = (p-1)/2, then ord(2,p) = p-1, or ord(2,p) = (p-1)/2 and p == 3 (mod 4) (otherwise ord(4,p) = (p-1)/4). In the first case, (p-1)/2 is the smallest m > 0 such that 2^m == +-1 (mod p); in the second case, since (p-1)/2 is odd, 2^m == -1 (mod p) has no solution. In either case, so 2^m is not 1 or -1 (mod p) for 0 < m < (p-1)/2.
{(a(n)-1)/2} is the sequence of indices of fixed points of A053447.
A prime p is a term if and only if one of the two following conditions holds: (a) 2 is a primitive root modulo p; (b) p == 3 (mod 4), and the multiplicative order of 2 modulo p is (p-1)/2 (in this case, we have p == 7 (mod 8) since 2 is a quadratic residue modulo p). (End)
From Jianing Song, Aug 11 2023: (Start)
Primes p such that 2 or -2 (or both) is a primitive root modulo p. Proof of equivalence: if ord(2,p) = p-1, then clearly ord(4,p) = (p-1)/2. If ord(-2,p) = p-1, then we also have ord(4,p) = (p-1)/2. Conversely, suppose that ord(4,p) = (p-1)/2, then ord(2,p) = p-1 or (p-1)/2, and ord(-2,p) = p-1 or (p-1)/2. If ord(2,p) = ord(-2,p) = (p-1)/2, then we have that (p-1)/2 is odd and (-1)^((p-1)/2) == 1 (mod p), a contradiction.
A prime p is a term if and only if one of the two following conditions holds: (a) -2 is a primitive root modulo p; (b) p == 3 (mod 4), and the multiplicative order of -2 modulo p is (p-1)/2 (in this case, we have p == 3 (mod 8) since -2 is a quadratic residue modulo p). (End)
No terms are congruent to 1 modulo 8, since otherwise we would have 4^((p-1)/4) = (+-2)^((p-1)/2) == 1 (mod p). - Jianing Song, May 14 2024
The n-th prime A000040(n) is a term iff A376010(n) = 2. - Max Alekseyev, Sep 05 2024

			Prime 23 has a k value of 11 = (23 - 1)/2 (Cf. A003558(11)). It follows that 23 has only one coach (A135303(11) = 1). 23 is thus in the set. On the other hand 31 is not in the set since A135303(15) shows 3 coaches, with A003558(15) = 5.
13 is in the set since A135303(6) = 1; but 17 isn't since A135303(8) = 2.

P. Hilton and J. Pedersen, A Mathematical Tapestry, Demonstrating the Beautiful Unity of Mathematics, 2010, Cambridge University Press, pages 260-264.
Carl Schick, Trigonometrie und unterhaltsame Zahlentheorie, Bokos Druck, Zürich, 2003 (ISBN 3-9522917-0-6). Tables 3.1 to 3.10, for odd p = 3..113 (with gaps), pp. 158-166.

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000 (first 1000 terms from T. D. Noe)
Gerold Brändli and Tim Beyne, Modified Congruence Modulo n with Half the Amount of Residues, arXiv:1504.02757 [math.NT], 2016.
Marcelo E. Coniglio, Francesc Esteva, Tommaso Flaminio, and Lluis Godo, On the expressive power of Lukasiewicz's square operator, arXiv:2103.07548 [math.LO], 2021.

Union of A001122 and A105874.
A105876 is the subsequence of terms congruent to 3 modulo 4.
Complement of A268923 in the set of odd primes.
Cf. A082654 (order of 4 mod n-th prime), A000010, A000040, A003558, A005034, A053447, A054639, A135303, A364867, A376010.

isA216371 := proc(n)
    if isprime(n) then
        if A135303((n-1)/2) = 1 then
            true;
        else
            false;
        end if;
    else
        false;
    end if;
end proc:
A216371 := proc(n)
    local p;
    if n = 1 then
        3;
    else
        p := nextprime(procname(n-1)) ;
        while true do
            if isA216371(p) then
                return p;
            end if;
            p := nextprime(p) ;
        end do:
    end if;
end proc:
seq(A216371(n),n=1..40) ; # R. J. Mathar, Dec 01 2014

Suborder[a_, n_] := If[n > 1 && GCD[a, n] == 1, Min[MultiplicativeOrder[a, n, {-1, 1}]], 0]; nn = 150; Select[Prime[Range[2, nn]], EulerPhi[#]/(2*Suborder[2, #]) == 1 &] (* T. D. Noe, Sep 18 2012 *)
f[p_] := Sum[Cos[2^n Pi/((2 p + 1))], {n, p}]; 1 + 2 * Select[Range[500], Reduce[f[#] == -1/2, Rationals] &]; (* Gerry Martens, May 01 2016 *)

is(p)=for(m=1,p\2-1, if(abs(centerlift(Mod(2,p)^m))==1, return(0))); p>2 && isprime(p) \\ Charles R Greathouse IV, Sep 18 2012

is(p) = isprime(p) && (p>2) && znorder(Mod(4,p)) == (p-1)/2 \\ Jianing Song, Dec 24 2022

a(n) = 2*A054639(n) + 1. - L. Edson Jeffery, Dec 18 2012

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

A001123 Primes with 3 as smallest primitive root.

Original entry on oeis.org

7, 17, 31, 43, 79, 89, 113, 127, 137, 199, 223, 233, 257, 281, 283, 331, 353, 401, 449, 463, 487, 521, 569, 571, 593, 607, 617, 631, 641, 691, 739, 751, 809, 811, 823, 857, 881, 929, 953, 977, 1013, 1039, 1049, 1063, 1087, 1097, 1193, 1217

Offset: 1

N. J. A. Sloane

nonn

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.
M. Kraitchik, Recherches sur la Théorie des Nombres. Gauthiers-Villars, Paris, Vol. 1, 1924, Vol. 2, 1929, see Vol. 1, p. 57.
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 = 1..1000
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].
Index entries for primes by primitive root

Cf. A001122, A001124, etc.

Cf. A019334.

Prime[ Select[ Range[200], PrimitiveRoot[ Prime[ # ]] == 3 & ]]
(* or *)
Select[ Prime@Range@200, PrimitiveRoot@# == 3 &] (* Robert G. Wilson v, May 11 2001 *)

forprime(p=3, 1000, if(znorder(Mod(2, p))!=p-1&&znorder(Mod(3, p))==p-1, print1(p,", ")));

{ n=0; forprime (p=3, 99999, if (znorder(Mod(2,p))!=p-1 && znorder(Mod(3,p))==p-1, n++; write("b001123.txt", n, " ", p); if (n>=1000, break) ) ) } \\ Harry J. Smith, Jun 14 2009

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

More terms from Robert G. Wilson v, May 10 2001

A023048 Smallest prime having least positive primitive root n, or 0 if no such prime exists.

Original entry on oeis.org

2, 3, 7, 0, 23, 41, 71, 0, 0, 313, 643, 4111, 457, 1031, 439, 0, 311, 53173, 191, 107227, 409, 3361, 2161, 533821, 0, 12391, 0, 133321, 15791, 124153, 5881, 0, 268969, 48889, 64609, 0, 36721, 55441, 166031, 1373989, 156601, 2494381, 95471, 71761, 95525767

Offset: 1

David W. Wilson

nonn

a(n) = 0 iff n is a perfect power m^k, m >= 1, k >= 2 (i.e., a member of A001597).

Of course if n is a perfect power then a(n) = 0, but it seems that the other direction is true only assuming the generalized Artin's conjecture. See the link from Tomás Oliveira e Silva below. - Jianing Song, Jan 22 2019

			a(2) = 3, since 3 has 2 as smallest positive primitive root and no prime p < 3 has 2 as smallest positive primitive root.
a(24) = 533821, since prime 533821 has 24 as smallest positive primitive root and no prime p < 533821 has 24 as smallest positive primitive root.

A. E. Western and J. C. P. Miller, Tables of Indices and Primitive Roots. Royal Society Mathematical Tables, Vol. 9, Cambridge Univ. Press, 1968, p. XLIV.

N. J. A. Sloane, Table of n, a(n) for n = 1..107 (from the web page of Tomás Oliveira e Silva)
Wouter Meeussen, Smallest Primes with Specified Least Primitive Root
Tomás Oliveira e Silva, Least primitive root of prime numbers
Index entries for primes by primitive root

Cf. A001122-A001126, A061323-A061335, A061730-A061741.
Indices of the primes: A066529.
For records see A133433. See A133432 for a version without the 0's.

t = Table[0, {100}]; Do[a = PrimitiveRoot@Prime@n; If[a < 101 && t[[a]] == 0, t[[a]] = n], {n, 10^6}]; Unprotect[Prime]; Prime[0] = 0; Prime@t; Clear[Prime]; Protect[Prime] (* Robert G. Wilson v, Dec 15 2005 *)

from sympy import nextprime, perfect_power, primitive_root
def a(n):
    if perfect_power(n): return 0
    p = 2
    while primitive_root(p) != n: p = nextprime(p)
    return p
print([a(n) for n in range(1, 40)]) # Michael S. Branicky, Feb 13 2023

# faster version for initial segment of sequence
from itertools import count, islice
from sympy import nextprime, perfect_power, primitive_root
def agen(): # generator of terms
    p, adict, n = 2, {None: 0}, 1
    for k in count(1):
        v = primitive_root(p)
        if v not in adict:
            adict[v] = p
        if perfect_power(n): adict[n] = 0
        while n in adict: yield adict[n]; n += 1
        p = nextprime(p)
print(list(islice(agen(), 40))) # Michael S. Branicky, Feb 13 2023

a(n) = min { prime(k) | A001918(k) = n } U {0} = A000040(A066529(n)) (or zero). - M. F. Hasler, Jun 01 2018

Comment corrected by Christopher J. Smyth, Oct 16 2013

A292270 Sum of all partial fractions in the algorithm used for calculation of A002326(n).

Original entry on oeis.org

1, 1, 4, 1, 13, 25, 36, 1, 38, 81, 12, 26, 124, 121, 196, 1, 103, 73, 324, 42, 224, 175, 91, 147, 232, 14, 676, 170, 303, 841, 900, 1, 264, 1089, 385, 364, 93, 301, 585, 563, 1093, 1681, 44, 355, 152, 118, 83, 484, 1254, 763, 2500, 1043, 156, 2809, 996, 564, 952, 931, 71, 387, 3325, 176, 3124, 1, 649, 4225, 554, 1081

Offset: 0

Vladimir Shevelev and Antti Karttunen, Oct 05 2017

nonn

This sequence gives important additional insight into the algorithm for the calculation of A002326 (see A179680 for its description). Let us estimate how many steps are required before (the first) 1 will appear. Note that all partial fractions (which are indeed, integers) are odd residues modulo 2*n+1 from the interval [1,2*n-1]. So, if there is no repetition, then the number of steps does not exceed n. Suppose then that there is a repetition before the appearance of 1. Then for an odd residue k from [1, 2*n-1], 2^m_1 == 2^m_2 == k (mod 2*n+1) such that m_2 > m_1. But then 2^(m_2-m_1) == 1 (mod 2*n+1). So, since m_2 - m_1 < m_2, it means that 1 should appear earlier than the repetition of k, which is a contradiction. So the number of steps <= n. For example, for n=9, 2*n+1 = 19, we have exactly 9 steps with all other odd residues <= 17 modulo 19 appearing before the final 1: 5, 3, 11, 15, 17, 9, 7, 13, 1.

A001122 gives the odd numbers k such that a((k-1)/2) = A000290((k-1)/2).

			Let n = 9. According to the comment, a(9) = 5 + 3 + 11 + 15 + 17 + 9 + 7 + 13 + 1 = 81.

Antti Karttunen, Table of n, a(n) for n = 0..10001

Cf. A000265, A000290, A001122, A001917, A002326, A006519, A163782, A179382, A179680, A292239, A292265, A292947, A293218, A293219.

Cf. A000225 (gives the positions of ones), A292938 (of squares), A292939 (and the corresponding odd numbers), A292940 (odd numbers corresponding to squares larger than one), A292379 (odd numbers corresponding to squares less than n^2).

A000265(n) = (n >> valuation(n, 2));
A006519(n) = 2^valuation(n, 2);
A292270(n) = { my(x = n+n+1, z = ((1+x)/A006519(1+x)), m = A000265(1+x)); while(m!=1, z += ((x+m)/A006519(x+m)); m = A000265(x+m)); z; };

(define (A292270 n) (let ((x (+ n n 1))) (let loop ((z (/ (+ 1 x) (A006519 (+ 1 x)))) (k 1)) (let ((m (A000265 (+ x k)))) (if (= 1 m) z (loop (+ z (/ (+ x m) (A006519 (+ x m)))) m))))))

For all n >= 1, A000196(a((A001122(1+n)-1)/2)) = (A001122(1+n)-1)/2, in other words, a(A163782(n)) = A000290(A163782(n)).

A101208 Smallest odd prime p such that n = (p - 1) / ord_p(2).

Original entry on oeis.org

3, 7, 43, 113, 251, 31, 1163, 73, 397, 151, 331, 1753, 4421, 631, 3061, 257, 1429, 127, 6043, 3121, 29611, 1321, 18539, 601, 15451, 14327, 2971, 2857, 72269, 3391, 683, 2593, 17029, 2687, 42701, 11161, 13099, 1103, 71293, 13121, 17467, 2143, 83077, 25609, 5581

Offset: 1

Leigh Ellison (le(AT)maths.gla.ac.uk), Dec 14 2004

First time n appears is given in A001917.
Smallest p (let it be the k-th prime) such that A001917(k) = n, or the smallest prime which has ratio n in base 2.
First cyclic number (in base 2) of n-th degree (or n-th order): the reciprocals of these numbers belong to one of n different cycles. Each cycle has (a(n) - 1)/n digits.
Conjecture: a(n) is defined for all n.
Recursive by indices: (See A054471)
1, 3, 43, 83077, ...
2, 7, 1163, ...
4, 113, 257189, ...
5, 251, 6846277, ...
6, 31, 683, ...
8, 73, 472019, ...
9, 397, 13619483, ...
10, 151, 349717, ...
...
The records for the ratio in base 2 are: 1, 2, 6, 8, 18, 24, 31, 38, 72, 105, 129, 630, 1285, 1542, 2048, ..., the primes are: 3, 7, 31, 73, 127, 601, 683, 1103, 1801, 2731, 5419, 8191, 43691, 61681, 65537, ...
(Updated by Eric Chen, Jun 01 2015)

Eric Chen, Table of n, a(n) for n = 1..612
V. Papadimitriou, The 1/p ratio of the first hundred million primes

Cf. A001917, A101209, A054471.

Cf. A001122, A115591, A001133, A001134, A001135, A001136, A152307, A152308, A152309, A152310, A152311, which are sequences of primes p where the period of the reciprocal in base 2 is (p-1)/n for n=1 to 11.

f[n_Integer] := Block[{k = 1, p}, While[p = k*n + 1; ! PrimeQ[p] || p != 1 + n*MultiplicativeOrder[2, p] || p = 2, k++]; p]; Array[f, 128] (* Eric Chen, Jun 01 2015 *)

a(n) = {p=3; ok = 0; until(ok, if (n == (p-1)/znorder(Mod(2, p)), ok = 1, p = nextprime(p+1));); return (p);} \\ Michel Marcus, Jun 27 2013

A105874 Primes for which -2 is a primitive root.

Original entry on oeis.org

5, 7, 13, 23, 29, 37, 47, 53, 61, 71, 79, 101, 103, 149, 167, 173, 181, 191, 197, 199, 239, 263, 269, 271, 293, 311, 317, 349, 359, 367, 373, 383, 389, 421, 461, 463, 479, 487, 503, 509, 541, 557, 599, 607, 613, 647, 653, 661, 677, 701, 709, 719, 743, 751, 757, 773, 797

Offset: 1

N. J. A. Sloane, Apr 24 2005

nonn

Also primes for which (p-1)/2 (==-1/2 mod p) is a primitive root. [Joerg Arndt, Jun 27 2011]

Joerg Arndt, Table of n, a(n) for n = 1..10000
L. J. Goldstein, Density questions in algebraic number theory, Amer. Math. Monthly, 78 (1971), 342-349.
Index entries for primes by primitive root

Cf. A001122, A019334-A019338, A001913, A019339-A019367 etc., A105875-A105914.

with(numtheory); f:=proc(n) local t1,i,p; t1:=[]; for i from 1 to 500 do p:=ithprime(i); if order(n,p) = p-1 then t1:=[op(t1),p]; fi; od; t1; end; f(-2);

pr=-2; Select[Prime[Range[200]], MultiplicativeOrder[pr, # ] == #-1 &] (* N. J. A. Sloane, Jun 01 2010 *)
a[p_,q_]:=Sum[2 Cos[2^n Pi/((2 q+1) (2 p+1))], {n,1,2 q p}];
Select[Range[400], Reduce[a[#, 1] == 1, Integers] &];
2 % + 1 (* Gerry Martens, Apr 28 2015 *)

forprime(p=3,10^4,if(p-1==znorder(Mod(-2,p)),print1(p", "))); /* Joerg Arndt, Jun 27 2011 */

from sympy import n_order, nextprime
from itertools import islice
def A105874_gen(startvalue=3): # generator of terms >= startvalue
    p = max(startvalue-1,2)
    while (p:=nextprime(p)):
        if n_order(-2,p) == p-1:
            yield p
A105874_list = list(islice(A105874_gen(),20)) # Chai Wah Wu, Aug 11 2023

Let a(p,q)=sum(n=1,2*p*q,2*cos(2^n*Pi/((2*q+1)*(2*p+1)))). Then 2*p+1 is a prime belonging to this sequence when a(p,1)==1. - Gerry Martens, May 21 2015

Previous Showing 21-30 of 146 results. Next

Let x,y be odd numbers. Denote <+> the following binary operation: x<+>y=A000265(x+y). Let a and d be odd numbers. We call a sequence of the form b, b<+>d, (b<+>d)<+>d,... a pseudo-arithmetic progression with the initial term b and the difference d. It is not difficult to prove that every pseudo-arithmetic progression is periodic sequence. This sequence lists smallest periods of pseudo-arithmetic progressions with initial term 1 and difference 2n-1, n=1,2,...

a(n) is the number of distinct odd residues contained in set {1,2,...,2^(2*n-2)} modulo 2*n-1. Thus 2*n-1 is in A001122 iff a(n)=n-1. - Vladimir Shevelev, Jul 18 2010

cp's OEIS Frontend

A179382 a(n) is the smallest period of pseudo-arithmetic progression with initial term 1 and difference 2n-1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Sage

Formula

Extensions

A071642 Numbers n such that x^n + x^(n-1) + x^(n-2) + ... + x + 1 is irreducible over GF(2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A090866 Primes p == 1 (mod 4) such that (p-1)/4 is prime.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A216371 Odd primes with one coach: primes p such that A135303((p-1)/2) = 1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Extensions

A001123 Primes with 3 as smallest primitive root.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

PARI

PARI