|
|
A163782
|
|
a(n) is the n-th J_2-prime (Josephus_2 prime).
|
|
26
|
|
|
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_2-prime if this permutation consists of a single cycle of length N.
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^*.
|
|
REFERENCES
|
P. R. J. Asveld, Permuting Operations on Strings-Their 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), Addison-Wesley, 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) 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.
Eric Weisstein's World of Mathematics, Josephus Problem
Wikipedia, Josephus Problem
Index entries for sequences related to the Josephus Problem
|
|
FORMULA
|
a(n) = A071642(n+3)/2.
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.
|
|
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_2-prime.
|
|
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-((d-i)>>valuation(d-i, 2)))/2)}
select(n->ok(n), [1..1000]) \\ Andrew Howroyd, Nov 11 2017
(PARI)
forprime(p=5, 2000, if(znorder(Mod(2, p))==p-1, print1((p-1)/2, ", "))); \\ Andrew Howroyd, Nov 11 2017
|
|
CROSSREFS
|
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.
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
|
|
|
|