A105874 -id:A105874 - cp's OEIS frontend

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

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

A337878 a(n) is the smallest m > 0 such that the n-th prime divides Jacobsthal(m).

Original entry on oeis.org

3, 4, 6, 5, 12, 8, 9, 22, 28, 10, 36, 20, 7, 46, 52, 29, 60, 33, 70, 18, 78, 41, 22, 48, 100, 102, 53, 36, 28, 14, 65, 68, 69, 148, 30, 52, 81, 166, 172, 89, 180, 190, 96, 196, 198, 105, 74, 113, 76, 58, 238, 24, 25, 16, 262, 268, 270, 92, 35, 47, 292, 51

Offset: 2

A.H.M. Smeets, Sep 27 2020

nonn

All positive Jacobsthal numbers are odd, so the index starts at n = 2.
The set of primitive prime factors of J_k is given by {A000040(j) | a(j) = k}.
By definition, a(n) is the multiplicative order of -2 modulo the n-th prime for n > 2. - Jianing Song, Jun 20 2025

			The 4th prime number is 7, and 7 divides 21 which is Jacobsthal(6), so a(4) = 6. The second prime number, 3, divides Jacobsthal(6) as well, but it divides also the smaller Jacobsthal(3), i.e., a(2) = 3.

Jianing Song, Table of n, a(n) for n = 2..10000
Eric Weisstein's World of Mathematics, Primitive Prime Factor

Cf. A000040 (primes), A001045 (Jacobsthal numbers), A001602 (similar for Fibonacci numbers), A105874 (primes having primitive root -2), A129738.
Cf. multiplicative orders of 2..10: A014664, A062117, A082654, A211241, A211242, A211243, A211244, A211245, A002371.
Cf. multiplicative orders of -2..-10: this sequence (if first term 1), A380482, A380531, A380532, A380533, A380540, A380541, A380542, A385222.

m = 300; j = LinearRecurrence[{1, 2}, {3, 5}, m]; s = {}; p = 3; While[(ind = Select[Range[m], Divisible[j[[#]], p] &, 1]) != {}, AppendTo[s, ind[[1]] + 2]; p = NextPrime[p]]; s (* Amiram Eldar, Sep 28 2020 *)

J(n) = (2^n - (-1)^n)/3; \\ A001045
a(n) = {my(k=1, p=prime(n)); while (J(k) % p, k++); k;} \\ Michel Marcus, Sep 29 2020

n = 1
while n < 63:
    n, J0, J1, a = n+1, 3, 1, 3
    p = A000040(n)
    J0 = J0%p
    while J0 != 0:
        J0, J1, a = (J0+2*J1)%p, J0, a+1
    print(n,a)

A000040(n) == 1 (mod a(n)) for n > 2.

A268923 All odd primes a(n) such that for all odd primes q smaller than a(n) the order of 2 modulo a(n)q is a proper divisor of phi(a(n)q)/2. The totient function phi is given in A000010.

Original entry on oeis.org

17, 31, 41, 43, 73, 89, 97, 109, 113, 127, 137, 151, 157, 193, 223, 229, 233, 241, 251, 257, 277, 281, 283, 307, 313, 331, 337, 353, 397, 401, 409, 431, 433, 439, 449, 457, 499, 521, 569, 571, 577, 593, 601, 617, 631, 641, 643, 673, 683, 691, 727, 733, 739, 761, 769, 809, 811, 857, 881, 911, 919

Offset: 1

Wolfdieter Lang, Apr 01 2016

nonn

This sequence was inspired by A269454 submitted by Marina Ibrishimova.
It seems that if for an odd prime p > 3 the order(2, p*3) < phi(p*3)/2 = p-1 then p is in this sequence.
Note that 2^(phi(p*q)/2) == 1 (mod p*q) for distinct odd primes p and q, due to Nagell's corollary on Theorem 64, p. 106. The products of distinct primes considered in the present sequence have order of 2 modulo p*q smaller than phi(p*q)/2.
Up to and including prime(100) = 541 the only odd primes p such that for all odd primes q smaller than p the order of 2 modulo p*q equals phi(p*q)/2 are 5, 7, and 11.
Complement of A216371 = A001122 U A105874 in the set of odd primes. Composed of the primes modulo which neither 2 nor -2 is a primitive root. Also, prime(n) is a term iff A376010(n) > 2. - Max Alekseyev, Sep 05 2024

			n=1: Order(2, 17*3) = 8, and 8 is a proper divisor of phi(17*3)/2 = 16;
   order(2, 17*5) =  8, and 8 is a proper divisor of phi(17*5)/2 = 32;
   order(2, 17*7) = 24, and 24 is a proper divisor of phi(17*7)/2 = 48;
   order(2, 17*11) = 40, and 40 is a proper divisor of phi(17*11)/2 = 80;
   order(2, 17*13) = 24, and 24 is a proper divisor of phi(17*13)/2 = 96.

Michael De Vlieger, Table of n, a(n) for n = 1..1000
Wolfdieter Lang, On the Equivalence of Three Complete Cyclic Systems of Integers, arXiv:2008.04300 [math.NT], 2020.

Cf. A000010, A002326, A001122, A105874, A216371, A269454, A376010.

Select[Prime@ Range[3, 157], Function[p, AllTrue[Prime@ Range[2, PrimePi@ p - 1], Function[q, With[{e = EulerPhi[p q]/2}, And[Divisible[e, #], # != e]] &@ MultiplicativeOrder[2, p q]]]]] (* Michael De Vlieger, Apr 01 2016, Version 10 *)

More terms from Michael De Vlieger, Apr 01 2016

A105875 Primes for which -3 is a primitive root.

Original entry on oeis.org

2, 5, 11, 17, 23, 29, 47, 53, 59, 71, 83, 89, 101, 107, 113, 131, 137, 149, 167, 173, 179, 191, 197, 227, 233, 239, 251, 257, 263, 269, 281, 293, 311, 317, 347, 353, 359, 383, 389, 401, 419, 443, 449, 461, 467, 479, 503, 509, 521, 557, 563, 569, 587, 593, 599, 617, 641

Offset: 1

N. J. A. Sloane, Apr 24 2005

nonn

Also, primes for which -27 is a primitive root. Proof: -27 = (-3)^3, so -27 is a primitive root just when -3 is a primitive root and the prime is not 3k+1. Now if -3 is a primitive root, then -3 is not a quadratic residue and so the prime is not 3k+1. - Don Reble, Sep 15 2007

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
Index entries for primes by primitive root

Cf. A105874.

pr=-3; Select[Prime[Range[200]], MultiplicativeOrder[pr, # ] == #-1 &]

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

A105880 Primes for which -8 is a primitive root.

Original entry on oeis.org

5, 23, 29, 47, 53, 71, 101, 149, 167, 173, 191, 197, 239, 263, 269, 293, 311, 317, 359, 383, 389, 461, 479, 503, 509, 557, 599, 647, 653, 677, 701, 719, 743, 773, 797, 821, 839, 863, 887, 941, 983, 1031, 1061, 1109, 1151, 1223, 1229, 1277, 1301, 1319, 1367, 1373, 1439

Offset: 1

N. J. A. Sloane, Apr 24 2005

nonn

From Jianing Song, May 12 2024: (Start)
Members of A105874 that are not congruent to 1 mod 3. Terms are congruent to 5 or 23 modulo 24.
According to Artin's conjecture, the number of terms <= N is roughly ((3/5)*C)*PrimePi(N), where C is the Artin's constant = A005596, PrimePi = A000720. Compare: the number of terms of A001122 that are no greater than N is roughly C*PrimePi(N). (End)

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
Wikipedia, Artin's conjecture on primitive roots
Index entries for primes by primitive root

Cf. A105874, A005596, A000720.

pr=-8; Select[Prime[Range[400]], 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}]
2 Select[Range[800], Rationalize[N[a[#, 9], 20]] == 1 &] + 1
(* Gerry Martens, Apr 28 2015 *)

is(n)=isprime(n) && n>3 && znorder(Mod(-8,n))==n-1 \\ Charles R Greathouse IV, May 21 2015

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 of this sequence when a(p,9)==1. - Gerry Martens , May 21 2015

A137606 Numbers m such that all numbers {1...m} appear in the sequence {b(0) = m, b(n+1) = b(n)/2 if even, m-(b(n)+1)/2 otherwise}.

Original entry on oeis.org

1, 2, 3, 4, 6, 7, 10, 12, 15, 19, 24, 27, 30, 31, 34, 36, 40, 42, 51, 52, 54, 66, 70, 75, 82, 84, 87, 90, 91, 96, 99, 100, 106, 114, 120, 132, 135, 136, 147, 156, 159, 174, 175, 180, 184, 187, 190, 192, 195, 210, 211, 222, 231, 232, 234, 240, 244, 246, 252, 255, 262

Offset: 1

Yasutoshi Kohmoto, Apr 23 2008

nonn

Lemma: A sequence {b(n)} defined as above with m>1 cannot have values outside [1,m]. (For m=1, b=(1,0,0,0....).)
Corollary: Such a sequence {b(n)} is periodic with period <= m (except maybe for some initial terms).
Lemma 2: For any m>1, b(1) = floor( m/2 ) and if b(n)=m-1, then b(n+1)= [ m/2 ].
Proposition: As soon as there is a term b(n)=2^k, the (b-)sequence continues b(n+1)=2^(k-1),...,b(n+k)=1, b(n+k+1)=m-1 and then starts over with b(n+k+2)=b(1).
Corollary 2: Numbers m=2^k, k>2 cannot appear in the present sequence.
Proposition: For any b(0)=m>1, sooner or later the value 1 is reached.
Generate a sequence b(n) by the following rule. If b(n-1) is divisible by 2 then b(n) = b(n-1)/2. If b(n-1) is not divisible by 2 then b(n) = b(0)-(b(n-1)+1)/2. When b(n)=1 it ends. Sequence gives all m such that all numbers k with 1<=k<=m-2 appear in b(n), b(0)=m.
Sequence contains 1 and numbers m>1 such that 2m-1 is prime and -2 or 2 is a primitive root modulo 2m-1. - Max Alekseyev, May 16 2008

			6->3->4->2->1. 1,2,3,4=6-2 appear in b(n), b(0)=6. So 6 is a term of A137606.

Robert G. Wilson v, Table of n, a(n) for n = 1..2354.

Cf. A137607, A096259, A105874, A001122.

f[n_] := Block[{lst = {n}, a}, While[a = Last@ lst; a != 1, AppendTo[lst, If[ EvenQ@ a, a/2, lst[[1]] - (a + 1)/2]]]; Length@ lst - 1]; t = Array[f, 262]; Select[ Range @ 262, t[[ # ]] == # - 2 &] (* Robert G. Wilson v *)

b137606(n)= n=[n]; for( i=1,n[1]-1, n=concat( n, if( n[i]%2, n[1]-(n[i]+1)/2, n[i]/2 )); n[i]>1 || break); n
A137606(Nmax) = for( n=1,Nmax, n==#b137606(n) && print1(n","))

forprime(p=3,10^3, if(znorder(Mod(-2,p))==p-1||znorder(Mod(2,p))==p-1, print1((p+1)/2,", ") )) \\ Max Alekseyev, May 16 2008

This sequence as a set is the union of { 1 }, { (A105874(n)+1)/2 } and { (A001122(n)+1)/2 }. - Max Alekseyev, May 16 2008

Edited & extended by M. F. Hasler, Apr 28 2008

cp's OEIS Frontend

A167798 Numbers with primitive root -2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

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

A337878 a(n) is the smallest m > 0 such that the n-th prime divides Jacobsthal(m).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A268923 All odd primes a(n) such that for all odd primes q smaller than a(n) the order of 2 modulo a(n)*q is a proper divisor of phi(a(n)*q)/2. The totient function phi is given in A000010.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A105875 Primes for which -3 is a primitive root.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Python

A105880 Primes for which -8 is a primitive root.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A137606 Numbers m such that all numbers {1...m} appear in the sequence {b(0) = m, b(n+1) = b(n)/2 if even, m-(b(n)+1)/2 otherwise}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

A268923 All odd primes a(n) such that for all odd primes q smaller than a(n) the order of 2 modulo a(n)q is a proper divisor of phi(a(n)q)/2. The totient function phi is given in A000010.