A155072 -id:A155072 - cp's OEIS frontend

A115591 Primes p such that the multiplicative order of 2 modulo p is (p-1)/2.

7, 17, 23, 41, 47, 71, 79, 97, 103, 137, 167, 191, 193, 199, 239, 263, 271, 311, 313, 359, 367, 383, 401, 409, 449, 463, 479, 487, 503, 521, 569, 599, 607, 647, 719, 743, 751, 761, 769, 809, 823, 839, 857, 863, 887, 929, 967, 977, 983, 991, 1009, 1031

Offset: 1

Don Reble, Mar 11 2006

nonn

It appears that this is also the sequence of values of n for which the sum of terms of one period of the base-2 MR-expansion (see A136042) of 1/n equals (n-1)/2. An example appears in A155072 where one period of the base-2 MR-expansion of 1/17 is shown to be {5,1,1,1} with sum 8=(17-1)/2. - John W. Layman, Jan 19 2009

If p is a term of this sequence, then 2 is a quadratic residue module p, so p == 1, 7 (mod 8). - Jianing Song, Nov 01 2024

Klaus Brockhaus, Table of n, a(n) for n=1..1000

Cf. A001122, A001133.

Cf. A136042, A155072. - John W. Layman, Jan 19 2009

[ p: p in PrimesUpTo(1031) | r eq 1 and Order(R!2) eq q where q,r is Quotrem(p,2) where R is ResidueClassRing(p) ]; // Klaus Brockhaus, Dec 02 2008

fQ[n_] := 1 + 2 MultiplicativeOrder[2, n] == n; Select[ Prime@ Range@ 174, fQ]

r=2;forprime(p=3,1500,z=(p-1)/znorder(Mod(r,p));if(z==2,print1(p,", "))); \\ Joerg Arndt, Jan 12 2011

A225759 Primes p such that A179382((p+1)/2) = (p-1)/16.

Original entry on oeis.org

1217, 1249, 1553, 4049, 4273, 4481, 4993, 5297, 6449, 6481, 6689, 7121, 8081, 8609, 9137, 9281, 10337, 10369, 10433, 11617, 11633, 12577, 13441, 13633, 14321, 14753, 15569, 16417, 16433, 16673, 17137, 18257, 18433, 18481, 19793, 20113, 20353, 23057, 23857

Offset: 1

Lear Young, May 15 2013

nonn

Let n be a natural number coprime to 10 and let c be the "cycle length of n" (defined below).
Conjecture 1: If n-1=2^x*c for some x<5, then n is prime. If x > 4, the relative density of primes in such numbers is 1.
Conjecture 2: If the period of the decimal expansion of 1/n is n-1 or a divisor of n-1, and if n-1=2^x*c or n+1=2^x*c for some x, then n is prime.
- Lear Young, with contributions from Peter Košinár, Giovanni Resta, Charles R Greathouse IV, May 22 2013
To define the "cycle length of n" (using n=73 as an example):
Step 1 : 73 +  1 =  74. Get the odd part of  74, which is 37
Step 2 : 73 + 37 = 110. Get the odd part of 110, which is 55
Step 3 : 73 + 55 = 128. Get the odd part of 128, which is  1
Continuing this operation (with 73+1) repeats the same steps as above. There are 3 steps in the cycle, so the cycle length of 73 is c=3. (same to A179382((73+1)/2)=3).
More for the "cycle length of n" see link and cross references.
The numbers in the sequence are the values of n in the above conjecture when c=4 in case (1).

			(1217-1)/16 = 76 = A179382(609).

Lear Young and Charles R Greathouse IV, Table of n, a(n) for n = 1..10000 (first 117 terms from Young)
Hagen von Eitzen, Details of the "cycle length of n"

Analogs with different values of c: A001122 when c=1, A155072 when c=2, A001134 when c=3. A225890 has composite values.

Cf. A179382, A136042 (both sequences related to the way to get the "cycle length of n").

oddres(n)=n>>valuation(n, 2)
cyc(d)=my(k=1, t=1); while((t=oddres(t+d))>1, k++); k
forstep(n=17,1e4,[32,16],if(cyc(n)==n>>4 && isprime(n), print1(n", ")))
\\ Charles R Greathouse IV, May 15 2013

Edited by Charles R Greathouse IV, Nov 11 2014

A158379 Period-lengths of the base-3 MR-expansions of the reciprocals of the positive integers.

Original entry on oeis.org

2, 1, 2, 2, 4, 1, 6, 1, 2, 4, 4, 2, 2, 6, 4, 3, 16, 1, 18, 2, 6, 3, 8, 1, 20, 1, 2, 6, 28, 4, 30, 7, 4, 16, 10, 2, 18, 18, 2, 2, 8, 6, 42, 8, 4, 11, 18, 3, 42, 20, 16, 4, 52, 1, 20, 3, 18, 28, 26, 2, 10, 30, 6, 15, 10, 3, 22, 12, 8, 8, 28, 1, 12, 18, 20, 18, 28, 1, 78, 1, 2, 8, 38, 6, 14, 42, 28

Offset: 1

John W. Layman, Mar 17 2009

nonn

See A136042 for the definition of the MR-expansion.
It appears that if p is a prime with 3 as a primitive root (A001122), then the MR-expansion of 1/p is periodic with period p-1.
The period lengths of the base-2 MR-expansions of the reciprocals of the positive integers are given in A136043.

			The base-3 MR-expansion of 1/5 is {2,1,0,1,2,1,0,1,...} because 1/5->3/5->9/5->4/5->12/5->7/5->2/5->6/5->1/5->..., indicating that MR(1/5,3) begins {2,1,0,1,...} and has period 4. Thus a(5)=4.

Cf. A001122, A007733, A115591, A136042, A136043, A136044, A155072.

A384184 Order of the permutation of {0,...,n-1} formed by successively swapping elements at i and 2*i mod n, for i = 0,...,n-1.

Original entry on oeis.org

1, 2, 1, 4, 2, 2, 2, 8, 3, 4, 5, 4, 6, 4, 6, 16, 4, 6, 9, 8, 4, 10, 28, 8, 10, 12, 9, 8, 14, 12, 12, 32, 5, 8, 70, 12, 18, 18, 24, 16, 10, 8, 7, 20, 210, 56, 126, 16, 110, 20, 60, 24, 26, 18, 120, 16, 9, 28, 29, 24, 30, 24, 60, 64, 6, 10, 33, 16

Offset: 1

Mia Boudreau, May 29 2025

nonn

a(2*n) = 2*a(n) since the cycle lengths of the permutation with size 2*n is effectively that of size n twice, doubled. Thus, the LCM/order is doubled.

			For n = 11, the permutation is {0,3,4,7,8,1,2,9,10,5,6} and it has order a(11) = 5.

Mia Boudreau, Table of n, a(n) for n = 1..10000
Mia Boudreau, Java program, GitHub

Cf. A003418, A000027, A051732, A004626, A065119, A001122, A155072, A001133, A001134, A001135, A225759.

from sympy.combinatorics import Permutation
def a(n):
   L = list(range(n))
   for i in range(n):
       if (j:= (i << 1) % n) != i:
           L[i],L[j] = L[j],L[i]
   return Permutation(L).order() # Darío Clavijo, Jun 05 2025

a(2*n) = 2*a(n).
a(2^n) = 2^n.
Conjecture: a(2^n + 2^x) = 2^n * (x-n) if x > n.
a(2^n - 1) = A003418(n-1).
s(2^n + 1) = A000027(n).
a(2*n - 1) = A051732(n).
a(A004626(n)) % 2 = 1.
a(A065119(n)) = n/3.
a(A001122(n)) = (n-1) / 2.
a(A155072(n)) = (n-1) / 4.
a(A001133(n)) = (n-1) / 6.
a(A001134(n)) = (n-1) / 8.
a(A001135(n)) = (n-1) / 10.
a(A225759(n)) = (n-1) / 16.

cp's OEIS Frontend

A115591 Primes p such that the multiplicative order of 2 modulo p is (p-1)/2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

A225759 Primes p such that A179382((p+1)/2) = (p-1)/16.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Extensions

A158379 Period-lengths of the base-3 MR-expansions of the reciprocals of the positive integers.

Views

Author

Keywords

Comments

Examples

Crossrefs

A384184 Order of the permutation of {0,...,n-1} formed by successively swapping elements at i and 2*i mod n, for i = 0,...,n-1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Formula