A001917 -id:A001917 - cp's OEIS frontend

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

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

A139035 Primes of the form 4*k+3 with primitive root -2.

Original entry on oeis.org

7, 23, 47, 71, 79, 103, 167, 191, 199, 239, 263, 271, 311, 359, 367, 383, 463, 479, 487, 503, 599, 607, 647, 719, 743, 751, 823, 839, 863, 887, 967, 983, 991, 1031, 1039, 1063, 1087, 1151, 1223, 1231, 1279, 1303, 1319, 1367, 1439, 1447, 1487, 1511, 1543, 1559

Offset: 1

Vladimir Shevelev, May 31 2008, Jun 06 2008

nonn

Original name: Primes with semiprimitive root 2.
If p is a prime, then we call r a semiprimitive root if it has order (p-1)/2 and there is no x for which a^x is congruent to -1 (mod p).  So +/- r^k, 0 <= k <= (p-3)/2 is a complete set of nonzero residues (mod p).
If r=2, then (-1/p)=-1 and, consequently, a(n)==-1(mod 4).
Besides, (2/a(n))=1. Indeed, since 2^((p-1)/2)=1 (mod p), then 2==2^((p+1)/2)=(2^((p+1)/4))^2. Therefore, (a(n))^2==1(mod 16) and thus a(n)==-1(mod 8). This yields that residues 1,2,...,2^((p-3)/2) are quadratic residues modulo a(n), while -1,-2,...,-2^((p-3)/2) are quadratic nonresidues modulo a(n). Primitive root of a(n) is greater than or equal to 3. All terms are in A115591.
Conjecture: primes that have both primitive root -2 and -4. - Davide Rotondo, Dec 20 2024

Amiram Eldar, Table of n, a(n) for n = 1..10000
Christian Elsholtz, Almost all primes have a multiple of small Hamming weight, arXiv:1602.05974 [math.NT], 2016. See p. 6.
Jonas Kaiser, On the relationship between the Collatz conjecture and Mersenne prime numbers, arXiv preprint arXiv:1608.00862 [math.GM], 2016.
Vladimir Shevelev, On the Newman sum over multiples of a prime with a primitive or semiprimitive root 2, arXiv:0710.1354 [math.NT], 2007.
Vladimir Shevelev Exact exponent in the remainder term of Gelfond's digit theorem in the binary case, Acta Arithm. 136 (2009) 91-100, eq. (10).

Cf. A006694, A002326, A064287, A001917, A001122, A133954, A115591.

Reap[For[p = 3, p <= 10^4, p = NextPrime[p], rp = MultiplicativeOrder[2, p]; rm = MultiplicativeOrder[-2, p]; If[rp != p-1 && rm == p-1, Sow[p]]] ][[2, 1]] (* Jean-François Alcover, Sep 03 2016, after Joerg Arndt *)

{ forprime (p=3, 10^4,
    rp = znorder(Mod(+2,p));
    rm = znorder(Mod(-2,p));
    if ( (rp!=p-1) && (rm==p-1), print1(p,", ") );
);}
/* Joerg Arndt, Jun 03 2012 */

is(n)=n%8==7 && isprime(n) && znorder(Mod(-2,n))==n-1 \\ Charles R Greathouse IV, Nov 30 2017

Prime p is in the sequence iff p==-1(mod 8) and A002326((p-1)/2)=(p-1)/2. A sufficient condition: if p==-1 (mod 8) and (p-1)/2 is prime, then p is in the sequence (the converse statement, generally speaking, is not true).

A006694((a(n)-1)/2)=2 and A064287((a(n)-1)/2)=1.

New name from Joerg Arndt, Jun 03 2012

A211450 (p-1)/x, where p = prime(n) and x = ord(5,p), the smallest positive integer such that 5^x == 1 mod p.

Original entry on oeis.org

1, 1, 0, 1, 2, 3, 1, 2, 1, 2, 10, 1, 2, 1, 1, 1, 2, 2, 3, 14, 1, 2, 1, 2, 1, 4, 1, 1, 4, 1, 3, 2, 1, 2, 4, 2, 1, 3, 1, 1, 2, 12, 10, 1, 1, 6, 6, 1, 1, 2, 1, 2, 6, 10, 1, 1, 4, 10, 1, 2, 1, 1, 1, 2, 39, 1, 2, 3, 1, 2, 1, 2, 3, 1, 18, 1, 4, 1, 16, 24, 2, 2, 2, 1

Offset: 1

T. D. Noe, Apr 11 2012

nonn

T. D. Noe, Table of n, a(n) for n = 1..1000

Cf. A001917, A094593, A211449, A211451, A211452, A211453, A211454, A006556.

nn = 5; Table[If[Mod[nn, p] == 0, 0, (p-1)/MultiplicativeOrder[nn, p]], {p, Prime[Range[100]]}]

A211449 (p-1)/x, where p = prime(n) and x = ord(4,p), the smallest positive integer such that 4^x == 1 mod p.

Original entry on oeis.org

0, 2, 2, 2, 2, 2, 4, 2, 2, 2, 6, 2, 4, 6, 2, 2, 2, 2, 2, 2, 8, 2, 2, 8, 4, 2, 2, 2, 6, 8, 18, 2, 4, 2, 2, 10, 6, 2, 2, 2, 2, 2, 2, 4, 2, 2, 2, 6, 2, 6, 8, 2, 20, 10, 32, 2, 2, 2, 6, 8, 6, 2, 6, 2, 4, 2, 22, 16, 2, 2, 8, 2, 2, 2, 2, 2, 2, 18, 4, 4, 2, 2, 10, 12

Offset: 1

T. D. Noe, Apr 11 2012

nonn

T. D. Noe, Table of n, a(n) for n = 1..1000

Cf. A001917, A094593, A211450, A211451, A211452, A211453, A211454, A006556.

nn = 4; Table[If[Mod[nn, p] == 0, 0, (p-1)/MultiplicativeOrder[nn, p]], {p, Prime[Range[100]]}]

A211451 (p-1)/x, where p = prime(n) and x = ord(6,p), the smallest positive integer such that 6^x == 1 mod p.

Original entry on oeis.org

0, 0, 4, 3, 1, 1, 1, 2, 2, 2, 5, 9, 1, 14, 2, 2, 1, 1, 2, 2, 2, 1, 1, 1, 8, 10, 1, 1, 1, 1, 1, 1, 1, 6, 4, 1, 1, 6, 2, 4, 1, 3, 10, 2, 14, 1, 2, 1, 1, 1, 1, 14, 12, 1, 1, 2, 2, 1, 1, 5, 2, 2, 6, 62, 6, 2, 2, 6, 1, 3, 11, 2, 1, 1, 6, 2, 4, 1, 1, 24, 1, 15, 10

Offset: 1

T. D. Noe, Apr 11 2012

nonn

T. D. Noe, Table of n, a(n) for n = 1..1000

Cf. A001917, A094593, A211449, A211450, A211452, A211453, A211454, A006556.

nn = 6; Table[If[Mod[nn, p] == 0, 0, (p-1)/MultiplicativeOrder[nn, p]], {p, Prime[Range[100]]}]

A211452 (p-1)/x, where p = prime(n) and x = ord(7,p), the smallest positive integer such that 7^x == 1 mod p.

Original entry on oeis.org

1, 2, 1, 0, 1, 1, 1, 6, 1, 4, 2, 4, 1, 7, 2, 2, 2, 1, 1, 1, 3, 1, 2, 1, 1, 1, 2, 1, 4, 8, 1, 2, 2, 2, 2, 1, 3, 1, 2, 1, 1, 15, 19, 8, 2, 2, 1, 6, 2, 1, 2, 1, 1, 2, 1, 1, 1, 2, 2, 14, 2, 1, 2, 10, 3, 2, 3, 6, 1, 1, 11, 1, 6, 6, 1, 2, 4, 1, 2, 17, 22, 6, 1, 1, 6

Offset: 1

T. D. Noe, Apr 11 2012

nonn

T. D. Noe, Table of n, a(n) for n = 1..1000

Cf. A001917, A094593, A211449, A211450, A211451, A211453, A211454, A006556.

nn = 7; Table[If[Mod[nn, p] == 0, 0, (p-1)/MultiplicativeOrder[nn, p]], {p, Prime[Range[100]]}]

A211453 (p-1)/x, where p = prime(n) and x = ord(8,p), the smallest positive integer such that 8^x == 1 mod p.

Original entry on oeis.org

0, 1, 1, 6, 1, 3, 2, 3, 2, 1, 6, 3, 2, 3, 2, 1, 1, 3, 3, 2, 24, 6, 1, 8, 6, 1, 6, 1, 9, 4, 18, 1, 2, 3, 1, 30, 3, 3, 2, 1, 1, 3, 2, 6, 1, 6, 3, 6, 1, 3, 8, 2, 30, 5, 16, 2, 1, 6, 3, 4, 3, 1, 9, 2, 6, 1, 33, 48, 1, 3, 4, 2, 6, 3, 3, 2, 1, 9, 2, 6, 1, 3, 10, 18

Offset: 1

T. D. Noe, Apr 11 2012

nonn

T. D. Noe, Table of n, a(n) for n = 1..1000

Cf. A001917, A094593, A211449, A211450, A211451, A211452, A211454, A006556.

nn = 8; Table[If[Mod[nn, p] == 0, 0, (p-1)/MultiplicativeOrder[nn, p]], {p, Prime[Range[100]]}]

A211454 (p-1)/x, where p = prime(n) and x = ord(9,p), the smallest positive integer such that 9^x == 1 mod p.

Original entry on oeis.org

1, 0, 2, 2, 2, 4, 2, 2, 2, 2, 2, 4, 10, 2, 2, 2, 2, 12, 6, 2, 12, 2, 2, 2, 4, 2, 6, 2, 4, 2, 2, 2, 2, 2, 2, 6, 4, 2, 2, 2, 2, 4, 2, 24, 2, 2, 2, 2, 2, 4, 2, 2, 4, 2, 2, 2, 2, 18, 4, 2, 2, 2, 18, 2, 8, 2, 2, 4, 2, 4, 2, 2, 6, 4, 2, 2, 2, 4, 2, 4, 2, 4, 10, 16

Offset: 1

T. D. Noe, Apr 11 2012

nonn

T. D. Noe, Table of n, a(n) for n = 1..1000

Cf. A001917, A094593, A211449, A211450, A211451, A211452, A211453, A006556.

nn = 9; Table[If[Mod[nn, p] == 0, 0, (p-1)/MultiplicativeOrder[nn, p]], {p, Prime[Range[100]]}]

A226216 Primes p such that (p-1)/ord(2,p) > (q-1)/ord(2,q) for odd primes q < p.

Original entry on oeis.org

3, 7, 31, 73, 127, 601, 683, 1103, 1801, 2731, 5419, 8191, 43691, 61681, 65537, 121369, 122921, 131071, 178481, 262657, 524287, 2099863, 2796203, 6700417, 10567201, 13264529, 20394401, 48544121, 97685839, 112901153, 160465489, 164511353, 420778751, 536903681, 616318177

Offset: 1

Charles R Greathouse IV, May 31 2013

nonn

Essentially records in A001917. Sequence is infinite.

The Mersenne primes (A000668) are a subset. - Jeppe Stig Nielsen, Aug 30 2015

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

Cf. A000668, A001917, A014664, A152597, A152598.

r=0; p=3; L={}; While[Length@L < 20, v = (p-1)/ MultiplicativeOrder[2, p]; If[v > r, r = v; AppendTo[L, p]]; p = NextPrime@ p]; L (* Giovanni Resta, Aug 31 2015 *)

r=0;forprime(p=3,1e9,t=(p-1)/znorder(Mod(2,p));if(t>r,r=t;print1(p", ")))

a(n) = prime(A152597(n)). - Amiram Eldar, Nov 16 2023

A300101 a(n) = (pp-1)/x, where pp = A001567(n) and x = ord(2,pp), the smallest positive integer such that 2^x == 1 (mod pp).

Original entry on oeis.org

34, 14, 23, 46, 77, 48, 68, 186, 44, 75, 47, 117, 112, 273, 19, 312, 390, 10, 221, 160, 106, 45, 342, 42, 157, 64, 229, 237, 699, 345, 714, 352, 348, 668, 195, 285, 575, 487, 56, 163, 502, 9, 357, 439, 310, 296, 208, 803, 151, 684, 217, 2038, 324, 315, 1666, 344, 1973, 319, 607, 2763, 62, 1777, 1122, 1360, 1135, 2603

Offset: 1

Jonas Kaiser, Feb 24 2018

nonn

For primes, this definition has a clear distribution over the natural numbers (see A001917), whereas there is no such distribution for pseudoprimes. Among the first 10^6 pseudoprimes of this sequence, the smallest number is 9. Are there any numbers in this sequence which are smaller than 9?

There is no value smaller than 9 for all the pseudoprimes below 2^64. - Amiram Eldar, Nov 09 2023

Amiram Eldar, Table of n, a(n) for n = 1..10000
Jonas Kaiser, On the relationship between the Collatz conjecture and Mersenne prime numbers, arXiv:1608.00862 [math.GM], 2016.

Cf. A001917, A001567, A306413, A174590.

((# - 1)/MultiplicativeOrder[2, #]) & /@ Select[Range[10^5], CompositeQ[#] && PowerMod[2, # - 1, #] == 1 &] (* Amiram Eldar, Nov 09 2023 *)

is_A001567(n)={Mod(2, n)^n==2 & !isprime(n) & n>1};
lista(nn) = {for (n=1, nn, if (is_A001567(n), print1((n-1)/znorder(Mod(2, n)), ", ");););} \\ Michel Marcus, Feb 25 2018

a(n) = (A001567(n) - 1) / A306413(n). - Jianing Song, Dec 12 2021

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

A139035 Primes of the form 4*k+3 with primitive root -2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A211450 (p-1)/x, where p = prime(n) and x = ord(5,p), the smallest positive integer such that 5^x == 1 mod p.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

A211449 (p-1)/x, where p = prime(n) and x = ord(4,p), the smallest positive integer such that 4^x == 1 mod p.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

A211451 (p-1)/x, where p = prime(n) and x = ord(6,p), the smallest positive integer such that 6^x == 1 mod p.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

A211452 (p-1)/x, where p = prime(n) and x = ord(7,p), the smallest positive integer such that 7^x == 1 mod p.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

A211453 (p-1)/x, where p = prime(n) and x = ord(8,p), the smallest positive integer such that 8^x == 1 mod p.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

A211454 (p-1)/x, where p = prime(n) and x = ord(9,p), the smallest positive integer such that 9^x == 1 mod p.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

A226216 Primes p such that (p-1)/ord(2,p) > (q-1)/ord(2,q) for odd primes q < p.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs