cp's OEIS Frontend

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^*.

The Josephus elimination begins with a circular list {1,...,n} from which successively take 2 elements and skip 1, and the permutation is the elements taken in the order they're taken.

The same effect can be had by leaving remaining elements at the end of a flat list of {1,...,n} and applying the "skip" as a move (rotate) of the element at position 2*i+3 to the end of the list, for successive i >= 0.

Take 2 and move 1 is a move every 3rd element, but with the next 3 elements reckoned inclusive of the element which replaced the moved 1, and hence positions 2 apart.

A given element can be skipped or moved multiple times before reaching its final position.

The value of a(n) can vary sharply; for example, a(62) = 280, a(63) = 15939, a(64) = 210.

With 2n cards, a riffle shuffle can be described as a permutation, where r becomes 2r-1 when r <= n and r becomes 2r-2n when r > n. The first and last cards are always left unaltered. Sequence A002326 describes the lengths of the longest orbits in the permutation. E.g. when 2n=10, the permutation can be described as (2,3,5,9,8,6)(4,7). The present sequence gives the values of 2n for which there is just one orbit on the 2n-2 cards, for example the permutation when 2n=12 is (2,3,5,9,6,11,10,8,4,7) containing all the 10 numbers other than 1 & 12.

Tiago Januario (email, Jan 12 2015; see also reference) conjectures that these terms are always one more than a prime. - N. J. A. Sloane, Mar 02 2015

Origin unknown. First encountered by this author as part of an employment-interview question at Apple Inc, in early 2016.

While holding a deck of n cards:

1. Deal the top card from the deck onto the table ('deal one').

2. Move the next card from the top of the deck to the bottom of the deck ('skip one').

3. Repeat steps 1 and 2 until all cards are on the table. This is a round.

4. Pick up the deck from the table and repeat steps 1 through 3 until the deck is in its original order.

From Robert Israel, Jul 06 2017: (Start)

a(n) <= A000793(n).

a(n) divides n!.

Conjecture: a(n) < n for infinitely many n.

Conjecture: the set of n for which the permutation is a single n-cycle, and thus a(n) = n, has nonzero density. (End)

It appears that for n = 2^k and all m > n, a(n) <= a(m). - Andrew Warren, Jul 15 2017

a(2^(k+1)) / a(2^k) = A020513(k+2) at least for 1 <= k <= 30, according to the values computed by Andrew Warren. - Andrey Zabolotskiy, Apr 02 2018

The Josephus elimination begins with a circular list [n] from which successively take 3 elements and skip 1, and the permutation is the elements taken in the order they're taken.

The same effect can be had by leaving remaining elements at the end of a flat list of [n] and applying the "skip" as a move (rotate) of the element at position 3*i+4 to the end of the list, for successive i >= 0.

Take 3 and move 1 is a move every 4th element, but with the next 4 elements reckoned inclusive of the element which replaced the moved 1, and hence positions 3 apart.

A given element can be skipped or moved multiple times before reaching its final position.

The Yummie permutation is done as follows. Start with a packet of n cards (numbered 1 to n from top to bottom), and deal them into two piles, first to a spectator (pile A), and then to yourself (pile B), saying "You, me," silently to yourself over and over. Then, pick up pile B and deal again, first to the spectator, thereby adding to the existing pile A, and then to yourself, forming a new pile B. Repeat, picking up the diminished pile B, and dealing "You, me" as before. Eventually, just one card remains in pile B; place it on top of pile A. The sequence of cards in pile A determines the Yummie permutation ("You, me" said fast sounds like "Yummie").

Size of the largest part of the partition of n that is associated with the cycle structure of the permutation given by the permutation product (1)*(1,2)*(1,2,3)*...*(1,2,3,...n) after the product is rewritten as the product of disjoint cycles, where * means functional composition, and the permutations are written in cycle form.

Also see Circular shift on Wikipedia.

For n>1, a(n) is always greater than 1, since the given product can never be the identity permutation on the set {1,2,...,n}, which is the only permutation associated with the partition <1,1,...,1> (1 repeated n times).

Connections: The image of 1 in each resulting permutation appears to be the same as the numbers in A003602. The number of parts in the partition associated with each resulting permutation appear to match the numbers in A006694.

The LCM of all cycle lengths gives A051732(n+1). - Alois P. Heinz, Apr 08 2020

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.

The Josephus elimination begins with a circular list [n] from which successively take k elements and skip 1 where k begins at 1 and monotonically increases after each skip, and the permutation is the elements taken in the order they're taken.

Take k and move 1 is a move every k-th element, but with the next k+1 elements reckoned inclusive of the element which replaced the moved 1, and hence positions k apart.

A given element can be skipped or moved multiple times before reaching its final position.

This sequence enters relatively lengthy stretches of linearity where a(n) = n-1 before entering stretches where it oscillates between n-1 and much larger values. This behavior is observed multiple times between a(1) and a(1000). It is unknown if this behavior continues to happen further into the sequence. For example: a(n)=n-1 for n=905 to 946, and the terms that follow are 9419588158802421600, 947, 224555, 949, 1582305192, 951, 226455, 953, etc.