A163779 -id:A163779 - cp's OEIS frontend

A163782 a(n) is the n-th J_2-prime (Josephus_2 prime).

2, 5, 6, 9, 14, 18, 26, 29, 30, 33, 41, 50, 53, 65, 69, 74, 81, 86, 89, 90, 98, 105, 113, 134, 146, 158, 173, 174, 186, 189, 194, 209, 210, 221, 230, 233, 245, 254, 261, 270, 273, 278, 281, 293, 306, 309, 326, 329

Offset: 1

Peter R. J. Asveld, Aug 05 2009

nonn

Place the numbers 1..N (N>=2) on a circle and cyclically mark the 2nd unmarked number until all N numbers are marked. The order in which the N numbers are marked defines a permutation; N is a J_2-prime if this permutation consists of a single cycle of length N.
The resulting permutation can be written as p(m,N) = (2N+1-||2N+1-m||)/2 (1 <= m <= N), where ||x|| is the odd number such that x/||x|| is a power of 2. E.g., ||16||=1 and ||120||=15.
No formula is known for a(n): the J_2-primes have been found by exhaustive search (however, see the CROSS-REFERENCES). But we have: (1) N is J_2-prime iff p=2N+1 is a prime number and +2 generates Z_p^* (the multiplicative group of Z_p). (2) N is J_2-prime iff p=2N+1 is a prime number and exactly one of the following holds: (a) N == 1 (mod 4) and +2 generates Z_p^* but -2 does not, (b) N == 2 (mod 4) and both +2 and -2 generate Z_p^*.

			p(1,5)=3, p(2,5)=1, p(3,5)=5, p(4,5)=2 and p(5,5)=4.
So p=(1 3 5 4 2) and 5 is J_2-prime.

R. L. Graham, D. E. Knuth & O. Patashnik, Concrete Mathematics (1989), Addison-Wesley, Reading, MA. Sections 1.3 & 3.3.

P. R. J. Asveld, Table of n, a(n) for n = 1..6706
Jean-Paul Allouche, Manon Stipulanti, and Jia-Yan Yao, Doubling modulo odd integers, generalizations, and unexpected occurrences, arXiv:2504.17564 [math.NT], 2025.
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; alternative link.
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.
Eric Weisstein's World of Mathematics, Josephus Problem
Wikipedia, Josephus Problem
Index entries for sequences related to the Josephus Problem

A163783 through A163800 for J_3- through J_20-primes.
Considered as sets, A163782 is the union of A163777 and A163779, it equals the difference of A054639 and A163780, and 2*a(n) results in A071642.
Cf. A051732, A025480.

isJ2Prime(int n) { // for n > 1
  int count = 0, leader = 0;
  if (n % 4 == 1 || n % 4 == 2) { // small optimization
    do {
      leader = A025480(leader + n);
      count++;
    } while (leader != 0);
  }
  return count == n;
} // Joe Nellis, Jan 27 2023

lst = {};
Do[If[IntegerQ[(2^n + 1)/(2 n + 1)] && PrimitiveRoot[2 n + 1] == 2,
AppendTo[lst, n]], {n, 2, 10^5}]; lst (* Hilko Koning, Sep 21 2021 *)

Follow(s,f)={my(t=f(s),k=1); while(t>s, k++; t=f(t)); if(s==t, k, 0)}
ok(n)={my(d=2*n+1); n>1&&n==Follow(1,i->(d-((d-i)>>valuation(d-i, 2)))/2)}
select(n->ok(n),[1..1000]) \\ Andrew Howroyd, Nov 11 2017

forprime(p=5, 2000, if(znorder(Mod(2, p))==p-1, print1((p-1)/2, ", "))); \\ Andrew Howroyd, Nov 11 2017

a(n) = A071642(n+3)/2.

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

Original entry on oeis.org

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

A163777 Even terms in the sequence of Queneau numbers A054639.

Original entry on oeis.org

2, 6, 14, 18, 26, 30, 50, 74, 86, 90, 98, 134, 146, 158, 174, 186, 194, 210, 230, 254, 270, 278, 306, 326, 330, 338, 350, 354, 378, 386, 398, 410, 414, 426, 438, 470, 530, 554, 558, 606, 614, 618, 638, 650, 686, 690, 726, 746, 774, 810, 818, 834, 846, 866, 870

Offset: 1

Peter R. J. Asveld, Aug 11 2009

nonn

Previous name was: a(n) is the n-th A_0-prime (Archimedes_0 prime).

We have: (1) N is A_0-prime if and only if N is even, p = 2N + 1 is a prime number and both +2 and -2 generate Z_p^* (the multiplicative group of Z_p); (2) N is A_0-prime if and only if N = 2 (mod 4), p = 2N + 1 is a prime number and both +2 and -2 generate Z_p^*.

P. R. J. Asveld, Table of n, a(n) for n = 1..3378.
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. Another link.
Index entries for sequences related to the Josephus Problem

The A_0-primes are the even T- or Twist-primes, these T-primes are equal to the Queneau-numbers (A054639). For the related A_1-, A^+_1- and A^-_1-primes, see A163778, A163779 and A163780. Considered as sets A163777 is the intersection of the Josephus_2-primes (A163782) and the dual Josephus_2-primes (A163781), it also equals the difference of A054639 and the A_1-primes (A163779).

Cf. A137310.

okQ[n_] := EvenQ[n] && PrimeQ[2n+1] && MultiplicativeOrder[2, 2n+1] == 2n;
Select[Range[1000], okQ] (* Jean-François Alcover, Sep 10 2019, from PARI *)

Follow(s, f)={my(t=f(s), k=1); while(t>s, k++; t=f(t)); if(s==t, k, 0)}
ok(n)={n>1 && n==Follow(1, j->ceil((n+1)/2) - (-1)^j*ceil((j-1)/2))}
select(ok, [1..1000]) \\ Andrew Howroyd, Nov 11 2017

ok(n)={n%2==0 && isprime(2*n+1) && znorder(Mod(2, 2*n+1)) == 2*n}
select(ok, [1..1000]) \\ Andrew Howroyd, Nov 11 2017

a(n) = 2*A137310(n). - Andrew Howroyd, Nov 11 2017

Definition simplified by Michel Marcus, May 27 2013
a(33)-a(55) from Andrew Howroyd, Nov 11 2017
New name from Joerg Arndt, Mar 23 2018, edited by M. F. Hasler, Mar 24 2018

A163778 Odd terms in A054639.

Original entry on oeis.org

3, 5, 9, 11, 23, 29, 33, 35, 39, 41, 51, 53, 65, 69, 81, 83, 89, 95, 99, 105, 113, 119, 131, 135, 155, 173, 179, 183, 189, 191, 209, 221, 231, 233, 239, 243, 245, 251, 261, 273, 281, 293, 299, 303, 309, 323, 329, 359, 371, 375, 393, 411, 413, 419, 429

Offset: 1

Peter R. J. Asveld, Aug 11 2009

nonn

Previous name was: The A_1-primes (Archimedes_1 primes).
We have: (1) N is an A_1-prime iff N is odd, p=2N+1 is a prime number and only one of +2 and -2 generates Z_p^* (the multiplicative group of Z_p); (2) N is an A_1-prime iff p=2N+1 is a prime number and exactly one of the following holds: (a) N == 1 (mod 4) and +2 generates Z_p^* but -2 does not, (b) N == 3 (mod 4) and -2 generates Z_p^* but +2 does not.
The A_1-primes are the odd T- or Twist-primes (the T-primes are the same as the Queneau-numbers, A054639). For the related A_0-, A^+_1- and A^-_1-primes, see A163777, A163779 and A163780. Considered as a set, the present sequence is the union of the A^+_1-primes (A163779) and the A^-_1-primes (A163780). It is also equal to the difference of A054639 and the A_0-primes (A163777).

P. R. J. Asveld, Table of n, a(n) for n=1..6706.
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.

Cf. A054639, A163777, A163779, A163780, A294434, A294673.

follow[s_, f_] := Module[{t, k}, t = f[s]; k = 1; While[t>s, k++; t = f[t]]; If[s == t, k, 0]];
okQ[n_] := n>1 && n == follow[1, Function[j, Ceiling[n/2] + (-1)^j*Ceiling[ (j-1)/2]]];
A163778 = Select[Range[1000], okQ] (* Jean-François Alcover, Jun 07 2018, after Andrew Howroyd *)

Follow(s, f)={my(t=f(s), k=1); while(t>s, k++; t=f(t)); if(s==t, k, 0)}
ok(n)={n>1 && n==Follow(1, j->ceil(n/2) + (-1)^j*ceil((j-1)/2))}
select(ok, [1..1000]) \\ Andrew Howroyd, Nov 11 2017

ok(n)={n>1 && n%2==1 && isprime(2*n+1) && znorder(Mod(2, 2*n+1)) == if(n%4==3, n, 2*n)}
select(ok, [1..1000]) \\ Andrew Howroyd, Nov 11 2017

a(33)-a(55) from Andrew Howroyd, Nov 11 2017

New name from Joerg Arndt, Mar 23 2018

A163780 Terms in A054639 equal to 3 mod 4.

Original entry on oeis.org

3, 11, 23, 35, 39, 51, 83, 95, 99, 119, 131, 135, 155, 179, 183, 191, 231, 239, 243, 251, 299, 303, 323, 359, 371, 375, 411, 419, 431, 443, 483, 491, 495, 515, 519, 531, 543, 575, 611, 615, 639, 651, 659, 683, 719, 723, 743, 755, 771, 779, 783, 791, 803, 831, 879

Offset: 1

Peter R. J. Asveld, Aug 12 2009

nonn

Previous name was: a(n) is the n-th A^-_1-prime (Archimedes^-_1 prime).

N is A^-_1-prime iff N=3 (mod 4), p=2N+1 is a prime number and -2 generates Z_p^* (the multiplicative group of Z_p) but +2 does not.

P. R. J. Asveld Table of n, a(n) for n=1..3378.
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.

The A^-_1-primes are the T- or Twist-primes congruent 3 (mod 4), these T-primes are equal to the Queneau-numbers (A054639). For the related A_0-, A_1- and A^+_1-primes, see A163777, A163778 and A163779. Considered as sets the union of A163779 and A163780 equals A163778, the union of A163780 and A163777 is equal to A163781 (dual J_2-primes).

ok(n) = n%4==3 && isprime(2*n+1) && znorder(Mod(2, 2*n+1)) == n;
select(ok, [1..1000]) \\ Andrew Howroyd, Nov 11 2017

a(33)-a(55) from Andrew Howroyd, Nov 11 2017

New name from Andrey Zabolotskiy, Mar 23 2018

Showing 1-5 of 5 results.

cp's OEIS Frontend

A163782 a(n) is the n-th J_2-prime (Josephus_2 prime).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Java

Mathematica

PARI

PARI

Formula

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

A163777 Even terms in the sequence of Queneau numbers A054639.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A163778 Odd terms in A054639.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Extensions

A163780 Terms in A054639 equal to 3 mod 4.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Extensions