

A163782


a(n) is the nth J_2prime (Josephus_2 prime).


25



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,1


COMMENTS

Place the numbers 1..N (N>=2) on a circle and cyclicly 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_2prime if this permutation consists of a single cycle of length N.
No formula is known for a(n): the J_2primes have been found by exhaustive search (however, see the CROSSREFERENCES). But we have: (1) N is J_2prime iff p=2N+1 is a prime number and +2 generates Z_p^* (the multiplicative group of Z_p). (2) N is J_2prime 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^*.


REFERENCES

P. R. J. Asveld, Permuting Operations on StringsTheir Permutations and Their Primes, Twente University of Technology, 2014; http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.216.1682; http://doc.utwente.nl/67513/1/pospp.pdf.
R. L. Graham, D.E. Knuth & O. Patashnik, Concrete Mathematics (1989), AddisonWesley, Reading, MA. Sections 1.3 & 3.3.


LINKS

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) 19151932.
P. R. J. Asveld, Permuting operations on strings and the distribution of their prime numbers (2011), TRCTIT1124, Dept. of CS, Twente University of Technology, Enschede, The Netherlands.
P. R. J. Asveld, Some Families of Permutations and Their Primes (2009), TRCTIT0927, Dept. of CS, Twente University of Technology, Enschede, The Netherlands.
Eric Weisstein's World of Mathematics, Josephus Problem
Wikipedia, Josephus Problem


FORMULA

a(n) = A071642(n+3)/2.
The resulting permutation can be written as
p(m,N)=(2N+1_2N+1m_)/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.


EXAMPLE

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_2prime.


PROG

(PARI)
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((di)>>valuation(di, 2)))/2)}
select(n>ok(n), [1..1000]) \\ Andrew Howroyd, Nov 11 2017
(PARI)
forprime(p=5, 2000, if(znorder(Mod(2, p))==p1, print1((p1)/2, ", "))); \\ Andrew Howroyd, Nov 11 2017


CROSSREFS

A163783 through A163800 for J_3 through J_20primes.
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.
Sequence in context: A271371 A193978 A224486 * A226793 A255747 A256264
Adjacent sequences: A163779 A163780 A163781 * A163783 A163784 A163785


KEYWORD

nonn


AUTHOR

Peter R. J. Asveld, Aug 05 2009


STATUS

approved



