A053447 -id:A053447 - cp's OEIS frontend

A002326 Multiplicative order of 2 mod 2n+1.

1, 2, 4, 3, 6, 10, 12, 4, 8, 18, 6, 11, 20, 18, 28, 5, 10, 12, 36, 12, 20, 14, 12, 23, 21, 8, 52, 20, 18, 58, 60, 6, 12, 66, 22, 35, 9, 20, 30, 39, 54, 82, 8, 28, 11, 12, 10, 36, 48, 30, 100, 51, 12, 106, 36, 36, 28, 44, 12, 24, 110, 20, 100, 7, 14, 130, 18, 36, 68, 138, 46, 60, 28

Offset: 0

N. J. A. Sloane

In other words, least m > 0 such that 2n+1 divides 2^m-1.
Number of riffle shuffles of 2n+2 cards required to return a deck to initial state. A riffle shuffle replaces a list s(1), s(2), ..., s(m) with s(1), s((i/2)+1), s(2), s((i/2)+2), ... a(1) = 2 because a riffle shuffle of [1, 2, 3, 4] requires 2 iterations [1, 2, 3, 4] -> [1, 3, 2, 4] -> [1, 2, 3, 4] to restore the original order.
Concerning the complexity of computing this sequence, see for example Bach and Shallit, p. 115, exercise 8.
It is not difficult to prove that if 2n+1 is a prime then 2n is a multiple of a(n). But the converse is not true. Indeed, one can prove that a(2^(2t-1))=4t. Thus if n=2^(2t-1), where, for any m > 0, t=2^(m-1) then 2n is a multiple of a(n) while 2n+1 is a Fermat number which, as is well known, is not always a prime. It is an interesting problem to describe all composite numbers for which 2n is divisible by a(n). - Vladimir Shevelev, May 09 2008
For an algorithm of calculation of a(n) see author's comment in A179680. - Vladimir Shevelev, Jul 21 2010
From V. Raman, Sep 18 2012, Dec 10 2012: (Start)
If 2n+1 is prime, then the polynomial (x^(2n+1)+1)/(x+1) factors into 2n/a(n) polynomials of the same degree a(n) over GF(2).
If (x^(2n+1)+1)/(x+1) is irreducible over GF(2), then 2n+1 is prime, and 2 is a primitive root (mod 2n+1) (cf. A001122).
For all n > 0, a(n) is the degree of the largest irreducible polynomial factor for the polynomial (x^(2n+1)+1)/(x+1) over GF(2). (End)
a(n) is a factor of phi(2n+1) (A000010(2n+1)). - Douglas Boffey, Oct 21 2013
Conjecture: if p is an odd prime then a((p^3-1)/2) = p * a((p^2-1)/2). Because otherwise a((p^3-1)/2) < p * a((p^2-1)/2) iff a((p^3-1)/2) = a((p-1)/2) for a prime p. Equivalently p^3 divides 2^(p-1)-1, but no such prime p is known. - Thomas Ordowski, Feb 10 2014
A generalization of the previous conjecture: For each k>=2, if p is an odd prime then a(((p^(k+1))-1)/2) = p * a((p^k-1)/2). Computer testing of this generalized conjecture shows that there is no counterexample for k and p both up to 1000. - Ahmad J. Masad, Oct 17 2020
a(n) = a((N-1)/2), with odd N = 2*n+1 >= 3 (n >= 1), is also the primitive period length of (1/N) in binary notation: (1/N)2 = 0.repeat(a[1]a[2]...a[P(N)]), and P(N) = a((N-1)/2). E.g., N = 11 (n = 5), (1/11)_2 = 0.repeat(0001011101), with P(11) = 10 = a(5). Proof: Use a cyclic shift operation sigma (1 step to the left) on the cycle: sigma((1/N)_2) = .repeat(a[2]...a[P(N)]a[1]). Then one can prove for the composition sigma^[k] (k=0 is the identity map) written back in decimal notation the result (sigma^[k]((1/N)_2))_10 = (1/N)*2^k (mod N). E.g. N = 11, sigma^[2]((1/11)_2) = .repeat(0101110100), written in base 10 as 4/11, etc. Hence P(N) and the order of 2 modulo N coincide. - _Gary W. Adamson and Wolfdieter Lang, Oct 14 2020

			From _Vladimir Shevelev_, Oct 03 2017: (Start)
Our algorithm for the calculation of a(n) in the author's comment in A179680 (see also the Sage program below) could be represented in the form of a "finite continued fraction". For example let n = 8, 2*n+1 = 17. We have
    1 + 17
    ------- + 17
       2
    ------------- + 17
           2
    ------------------- + 17
              2
    -------------------------- = 1
                 32
Here the denominators are the A006519 of the numerators: A006519(1+17) = 2, A006519(9+17) = 2, A006519(13+17) = 2, A006519(15+17) = 32. Summing the exponents of these powers of 2, we obtain the required result: a(8) = 1 + 1 + 1 + 5 = 8. Indeed, we have (((1*32 - 17)*2 - 17)*2 - 17)*2 - 17 = 1. So 32*2*2*2 - 1 == 0 (mod 17), 2^8 - 1 == 0 (mod 17). In the general case, note that all "partial fractions" (which indeed are integers) are odd residues modulo 2*n+1 in the interval [1, 2*n-1]. It is easy to prove that the first 1 appears not later than in the n-th step. (End)

E. Bach and Jeffrey Shallit, Algorithmic Number Theory, I.
T. Folger, "Shuffling Into Hyperspace," Discover, 1991 (vol 12, no 1), pages 66-67.
M. Gardner, "Card Shuffles," Mathematical Carnival chapter 10, pages 123-138. New York: Vintage Books, 1977.
L. Lunelli and M. Lunelli, Tavola di congruenza a^n == 1 mod K per a=2,5,10, Atti Sem. Mat. Fis. Univ. Modena 10 (1960/61), 219-236 (1961).
J. H. Silverman, A Friendly Introduction to Number Theory, 3rd ed., Pearson Education, Inc, 2006, p. 146, Exer. 21.3
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 = 0..10000
Jean-Paul Allouche, Manon Stipulanti, and Jia-Yan Yao, Doubling modulo odd integers, generalizations, and unexpected occurrences, arXiv:2504.17564 [math.NT], 2025.
M. Baake, U. Grimm and J. Nilsson, Scaling of the Thue-Morse diffraction measure, arXiv preprint arXiv:1311.4371 [math-ph], 2013.
D. Bayer and P. Diaconis, Trailing the dovetail shuffle to its lair, Ann. Appl. Prob. 2 (2) (1992) 294-313.
Matthew Brand, Choosing 1 of N with and without lucky numbers, arXiv:1808.07994 [math.NT], 2018.
J. Brillhart, J. S. Lomont and P. Morton, Cyclotomic properties of the Rudin-Shapiro polynomials, J. Reine Angew. Math.288 (1976), 37--65. See Table 2. MR0498479 (58 #16589).
Steve Butler, Persi Diaconis and R. L. Graham, The mathematics of the flip and horseshoe shuffles, arXiv:1412.8533 [math.CO], 2014.
Steve Butler, Persi Diaconis and R. L. Graham, The mathematics of the flip and horseshoe shuffles, The American Mathematical Monthly 123.6 (2016): 542-556.
A. J. C. Cunningham, On Binal Fractions, Math. Gaz., 4 (71) (1908), circa p. 266.
P. Diaconis, R. L. Graham, and W. M. Kantor, The mathematics of perfect shuffles, Adv. Appl. Math. 4 (2) (1983) 175-196
M. J. Gardner and C. A. McMahan, Riffling casino checks, Math. Mag., 50 (1) (1977), 38-41.
S. W. Golomb, Permutations by cutting and shuffling, SIAM Rev., 3 (1961), 293-297.
Jonas Kaiser, On the relationship between the Collatz conjecture and Mersenne prime numbers, arXiv preprint arXiv:1608.00862 [math.GM], 2016.
Torleiv Klove, On covering sets for limited-magnitude errors, Cryptogr. Commun. 8 (3) (2016) 415-433
V. I. Levenshtein, Conflict-avoiding codes and cyclic triple systems [in Russian], Problemy Peredachi Informatsii, 43 (No. 3, 2007), 39-53.
V. I. Levenshtein, Conflict-avoiding codes and cyclic triple systems, Problems of Information Transmission, September 2007, Volume 43, Issue 3, pp 199-212 (translated from Russian)
Yuan-Hsun Lo, Kenneth W. Shum, Wing Shing Wong and Yijin Zhang, Multichannel Conflict-Avoiding Codes of Weights Three and Four, arXiv:2009.11754 [cs.IT], 2020.
Jarkko Peltomäki and Aleksi Saarela, Standard words and solutions of the word equation X_1^2 ... X_n^2 = (X_1 ... X_n)^2, Journal of Combinatorial Theory, Series A (2021) Vol. 178, 105340. See also arXiv:2004.14657 [cs.FL], 2020.
Vladimir Shevelev, Gilberto Garcia-Pulgarin, Juan Miguel Velasquez-Soto and John H. Castillo, Overpseudoprimes, and Mersenne and Fermat numbers as primover numbers, arXiv preprint arXiv:1206:0606 [math.NT], 2012.
Vladimir Shevelev, G. Garcia-Pulgarin, J. M. Velasquez and J. H. Castillo, Overpseudoprimes, and Mersenne and Fermat Numbers as Primover Numbers, J. Integer Seq. 15 (2012) Article 12.7.7.
Eric Weisstein's World of Mathematics, Riffle Shuffle
Eric Weisstein's World of Mathematics, In-Shuffle
Eric Weisstein's World of Mathematics, Out-Shuffle
Eric Weisstein's World of Mathematics, Multiplicative Order
Wikipedia, Riffle Shuffle

Cf. A003571, A003573, A217469, A070667-A070683, A053447, A053451, A292239, A292265.
Cf. A024222, A006694 (number of cyclotomic cosets).
Cf. A014664 (order of 2 mod n-th prime).
Cf. A001122 (primes for which 2 is a primitive root).
Cf. A216838 (primes for which 2 is not a primitive root).
Cf. A000010, A000225, A005420, A006519, A007733, A025192, A048675, A056239, A179680.
Bisections give A274298, A274299.
Partial sums: A359147.

List([0..100],n->OrderMod(2,2*n+1)); # Muniru A Asiru, Feb 01 2019

import Data.List (findIndex)
import Data.Maybe (fromJust)
a002326 n = (+ 1) $ fromJust $
            findIndex ((== 0) . (`mod` (2 * n + 1))) $ tail a000225_list
-- Reinhard Zumkeller, Apr 22 2013

[ 1 ] cat [ Modorder(2, 2*n+1): n in [1..72] ]; // Klaus Brockhaus, Dec 03 2008

a := n -> `if`(n=0, 1, numtheory:-order(2, 2*n+1)):
seq(a(n), n=0..72);

Table[MultiplicativeOrder[2, 2*n + 1], {n, 0, 100}] (* Robert G. Wilson v, Apr 05 2011 *)

a(n)=if(n<0,0,znorder(Mod(2,2*n+1))) /* Michael Somos, Mar 31 2005 */

from sympy import n_order
[n_order(2, 2*n+1) for n in range(73)] # Hermann Stamm-Wilbrandt, Jul 27 2021

# From Peter Luschny, Oct 06 2017: (Start)
[Mod(2,n).multiplicative_order() for n in (0..145) if gcd(n,2) == 1]
# Algorithm from Vladimir Shevelev as described in A179680 and presented in Example.
def A002326VS(n):
    s, m, N = 0, 1, 2*n + 1
    while True:
        k = N + m
        v = valuation(k, 2)
        s += v
        m = k >> v
        if m == 1: break
    return s
[A002326VS(n) for n in (0..72)] # (End)

a((3^n-1)/2) = A025192(n). - Vladimir Shevelev, May 09 2008
Bisection of A007733: a(n) = A007733(2*n+1). - Max Alekseyev, Jun 11 2009
a((b(n)-1)/2) = n for odd n and even n such that b(n/2) != b(n), where b(n) = A005420(n). - Thomas Ordowski, Jan 11 2014
Note that a(2^n-1) = n+1 and a(2^n) = 2*(n+1). - Thomas Ordowski, Jan 16 2014
a(n) = A056239(A292239(n)) = A048675(A292265(n)). - Antti Karttunen, Oct 04 2017

More terms from David W. Wilson, Jan 13 2000

More terms from Benoit Cloitre, Apr 11 2003

A082654 Order of 4 mod n-th prime: least k such that prime(n) divides 4^k-1, n >= 2.

Original entry on oeis.org

0, 1, 2, 3, 5, 6, 4, 9, 11, 14, 5, 18, 10, 7, 23, 26, 29, 30, 33, 35, 9, 39, 41, 11, 24, 50, 51, 53, 18, 14, 7, 65, 34, 69, 74, 15, 26, 81, 83, 86, 89, 90, 95, 48, 98, 99, 105, 37, 113, 38, 29, 119, 12, 25, 8, 131, 134, 135, 46, 35, 47, 146, 51, 155, 78, 158

Offset: 1

Gary W. Adamson, May 17 2003

The period of the expansion of 1/p, base N (where N=4), is equivalent to determining for base integer 4, the period of the sequence 1, 4, 4^2, 4^3, ... mod p. Thus the cycle length for base 4, 1/7 = 0.021021021... (cycle length 3).
The cycle length, base 4, mod p, is equivalent to "clock cycles", given angle A, then the algebraic identity for the doubling angle, 2A.
Examples: Given cos A, f(x) for 2A = 2x^2 - 1, seed 2 Pi/7, i.e., (.623489801 == (arrow), -.222520934... == -.900968867...== .623489801...(cycle length 3). Given 2 cos A, the algebraic identity for 2 cos 2A, f(x) = x^2 - 2; e.g., given seed 2 cos A = 2 Pi/7, the 3 cycle is 1.246979604...== .445041867...== -1.801937736...== back to 1.24697... Likewise, the doubling function given sin^2 A, f(x) for sin^2 2A = 4x(1 - x), the logistic equation; getting cycle length of 3 using the seed sin^2 2 Pi/7. Similarly, the doubling function for tan 2A given tan A, where A = 2 Pi/7 gives 2x/(1 - x^2), cycle length of 3. The doubling function for cot 2A given cot A, with A = 2 Pi/7 gives (x^2 - 1)/2x, cycle length of 3. Note that (x^2 - 1)/2x = sinh(log(x)), and is also generated from using Newton's method on x^2 + 1 = 0.
Consider the odd pseudoprimes, composite numbers x such that 2^(x-1) = 1 mod x, that have prime(n) as a factor. It appears that all such x can be factored as prime(n) * (2 a(n) k + 1) for some integer k. For example, the first few pseudoprimes having the factor 31 are 31*11, 31*91, 31*141 and 3*151. The 11th prime is 31 and a(11) = 5. Therefore all the cofactors of 31 should have the form 10k+1, which is clearly true. - T. D. Noe, Jun 10 2003

			4th prime is 7 and mod 7, 4^3 = 1, but not 4^1 or 4^2, so a(4) = 3.
n = 4: prime(4) = 7, 2^6 - 1 = 63 = 3*21 == 0 (mod 21), but not 2^k - 1 for lower exponents k >= 1, therefore ord(2, 3*7) = 6 and a(4) = 3. - _Wolfdieter Lang_, Apr 10 2020

Albert H. Beiler, Recreations in the Theory of Numbers, Dover, 1964; Table 48, pages 98-99.
John H. Conway & R. K. Guy, The Book of Numbers, Springer-Verlag, 1996, pages 207-208, Periodic Points.

T. D. Noe, 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.
G. Vostrov, R. Opiata, Computer modeling of dynamic processes in analytic number theory, Electrical and Computer Systems (Електротехнічні та комп'ютерні системи) 2018, No. 28, Issue 104, 240-247.

Cf. A053447 (order of 4 mod 2n+1), A216371.

In other bases: A014664, A062117, A211241, A211242, A211243, A211244, A211245, A002371, A372801.

A000040:=Filtered([1..350],IsPrime);;
List([1..Length(A000040)],n->OrderMod(4,A000040[n])); # Muniru A Asiru, Feb 07 2019

Join[{0}, Table[MultiplicativeOrder[4, Prime[n]], {n, 2, 100}]]

a(n)=if(n>1, znorder(Mod(4,prime(n))), 0) \\ Charles R Greathouse IV, Sep 07 2016

a(1) = 0, and a(n) = order(4, prime(n)), also used exp_{prime(n)}(4), that is least exponent k >= 1 for which 4^k is congruent to 1 mod prime(n), for n >= 2. prime(n) = A000040(n). [rewritten by Wolfdieter Lang, Apr 10 2020]
From Wolfdieter Lang, Apr 10 2020: (Start)
a(n) = A003558(prime(n)), for n >= 2.
a(n) = (1/2)*order(2, 3*prime(n)), for n >= 3. [Proof uses 4^k - 1 = (1+3)^k - 1 == 0 (mod 3), for k >= 0.] (End)
From Jianing Song, May 13 2024: (Start)
a(n) = A014664(n)/gcd(2, A014664(n)).
a(n) <= (prime(n) - 1)/2. Those prime(n) for which a(n) = (prime(n) - 1)/2 are listed in A216371. (End)

More terms from Reinhard Zumkeller, May 17 2003

A053451 Multiplicative order of 8 mod 2n+1.

Original entry on oeis.org

1, 2, 4, 1, 2, 10, 4, 4, 8, 6, 2, 11, 20, 6, 28, 5, 10, 4, 12, 4, 20, 14, 4, 23, 7, 8, 52, 20, 6, 58, 20, 2, 4, 22, 22, 35, 3, 20, 10, 13, 18, 82, 8, 28, 11, 4, 10, 12, 16, 10, 100, 17, 4, 106, 12, 12, 28, 44, 4, 8, 110, 20, 100, 7, 14, 130, 6, 12, 68, 46, 46, 20, 28, 14, 148, 5

Offset: 0

David W. Wilson

nonn

In the case n=2 and any other case where a(n)=A000010(2n+1), the multiplicative group of units modulo 2n+1 is cyclic and thus 8 (and any other unit) is a generator. These moduli are A167796, so this occurs whenever 2n+1 (caution: not n) is a member of A167796. - Kellen Myers, Feb 06 2015

			The third term a(2) is 4 because 4 is the smallest integer such that 8^4 is congruent to 1 modulo 2*2+1=5. The orbit of 8 modulo 5 is {3, 4, 2, 1}. - _Kellen Myers_, Feb 06 2015

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Eric Weisstein's World of Mathematics, Multiplicative Order

Cf. A050980, A070667-A070675, A002326, A070676, A053447, A070677, A070681, A070678, A070679, A070682, A070680, A070683.

List([0..80],n->OrderMod(8,2*n+1)); # Muniru A Asiru, Feb 26 2019

[1] cat [Modorder(8, 2*n+1): n in [1..100]]; // Vincenzo Librandi, Apr 01 2014

Table[MultiplicativeOrder[8, n], {n, 1, 150, 2}] (* Robert G. Wilson v, Apr 05 2011 *)

vector(80, n, n--; znorder(Mod(8, 2*n+1))) \\ Michel Marcus, Feb 05 2015

A059887 a(n) = |{m : multiplicative order of 5 mod m=n}|.

Original entry on oeis.org

3, 5, 3, 12, 9, 37, 3, 28, 18, 47, 3, 180, 3, 53, 81, 176, 9, 446, 21, 564, 39, 117, 9, 884, 180, 53, 360, 244, 21, 5959, 9, 800, 39, 111, 369, 9536, 21, 483, 39, 5476, 9, 18289, 9, 1140, 2958, 111, 3, 9424, 6, 3852, 177, 884, 21, 81048, 561, 1188, 69, 227, 9

Offset: 1

Vladeta Jovovic, Feb 06 2001

nonn

The multiplicative order of a mod m, gcd(a,m)=1, is the smallest natural number d for which a^d = 1 (mod m). a(n) = number of orders of degree-n monic irreducible polynomials over GF(5).

Also, number of primitive factors of 5^n - 1 (cf. A218357). - Max Alekseyev, May 03 2022

Max Alekseyev, Table of n, a(n) for n = 1..502

Number of primitive factors of b^n - 1: A059499 (b=2), A059885(b=3), A059886 (b=4), this sequence (b=5), A059888 (b=6), A059889 (b=7), A059890 (b=8), A059891 (b=9), A059892 (b=10).
Cf. A000005, A008683, A001692, A053447, A057956, A058945, A074479, A143665, A212485, A218357
Column k=5 of A212957.

with(numtheory):
a:= n-> add(mobius(n/d)*tau(5^d-1), d=divisors(n)):
seq(a(n), n=1..50);  # Alois P. Heinz, Oct 12 2012

a[n_] := Sum[MoebiusMu[n/d]*DivisorSigma[0, 5^d-1], {d, Divisors[n]}];
Table[a[n], {n, 1, 60}] (* Jean-François Alcover, Dec 13 2024, after Alois P. Heinz *)

a(n) = sumdiv(n, d, moebius(n/d)*numdiv(5^d-1)); \\ Michel Marcus, Dec 13 2024

a(n) = Sum_{d|n} mu(n/d)*tau(5^d-1), (mu(n) = Moebius function A008683, tau(n) = number of divisors of n A000005).

A059886 a(n) = |{m : multiplicative order of 4 mod m=n}|.

Original entry on oeis.org

2, 2, 4, 4, 6, 16, 6, 8, 26, 38, 14, 68, 6, 54, 84, 16, 6, 462, 6, 140, 132, 110, 14, 664, 120, 118, 128, 188, 62, 4456, 6, 96, 364, 118, 498, 7608, 30, 118, 180, 568, 30, 9000, 30, 892, 3974, 494, 62, 5360, 24, 8024, 1524, 892, 62, 9600, 3050, 1784, 372, 446

Offset: 1

Vladeta Jovovic, Feb 06 2001

nonn

The multiplicative order of a mod m, GCD(a,m)=1, is the smallest natural number d for which a^d = 1 (mod m).
a(n) is the number of orders of degree-n monic irreducible polynomials over GF(4).
Also, number of primitive factors of 4^n - 1. - Max Alekseyev, May 03 2022

			a(1) = |{1,3}| = 2, a(2) = |{5,15}| =2, a(3) = |{7,9,21,63}| =4, a(4) = |{17,51,85,255}| = 4.

Max Alekseyev, Table of n, a(n) for n = 1..1128 (first 160 terms from Alois P. Heinz)

Number of primitive factors of b^n - 1: A059499 (b=2), A059885(b=3), this sequence (b=4), A059887 (b=5), A059888 (b=6), A059889 (b=7), A059890 (b=8), A059891 (b=9), A059892 (b=10).
Cf. A000005, A008683, A027377, A053447, A057957, A058948, A112092, A274906.
Column k=4 of A212957.

with(numtheory):
a:= n-> add(mobius(n/d)*tau(4^d-1), d=divisors(n)):
seq(a(n), n=1..60);  # Alois P. Heinz, Oct 12 2012

a[n_] := DivisorSum[n, MoebiusMu[n/#]*DivisorSigma[0, 4^# - 1]&]; Array[a, 100] (* Jean-François Alcover, Nov 11 2015 *)

a(n) = sumdiv(n, d, moebius(n/d) * numdiv(4^d-1)); \\ Amiram Eldar, Jan 25 2025

a(n) = Sum_{ d divides n } mu(n/d)*tau(4^d-1), (mu(n) = Moebius function A008683, tau(n) = number of divisors of n A000005).

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

cp's OEIS Frontend

A339049 a(n) = A000010(2*n + 1)/A053447(n), for n >= 0.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

PARI

Formula

A002326 Multiplicative order of 2 mod 2n+1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Haskell

Magma

Maple

Mathematica

PARI

Python

Sage

Formula

Extensions

A082654 Order of 4 mod n-th prime: least k such that prime(n) divides 4^k-1, n >= 2.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Mathematica

PARI

Formula

Extensions

A053451 Multiplicative order of 8 mod 2n+1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Magma

Mathematica

PARI

A059887 a(n) = |{m : multiplicative order of 5 mod m=n}|.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A059886 a(n) = |{m : multiplicative order of 4 mod m=n}|.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs