A318712 Numbers k for which a riffle shuffle permutation with two or more packets permutes all except the first and the last of the k cards.

4, 6, 12, 14, 18, 20, 30, 38, 42, 54, 60, 62, 68, 84, 90, 98, 102, 108, 110, 114, 132, 138, 140, 150, 164, 174, 180, 182, 198, 212, 228, 230, 234, 252, 258, 270, 282, 294, 308, 318, 348, 350, 354, 374, 380, 390, 402, 420, 422, 434, 444, 450, 462, 468, 492, 500, 510, 522, 524, 542, 548, 558, 564

Offset: 1

Author

Mauro Rigo, Sep 01 2018

Keywords

• nonn

Comments

If k cards are cut into m packets of s cards each, the r-th card of the deck can be identified with the pair (p,q), where p=(r-1)%s+1 ('%' is the Euclidean division) is the number of the packet and q=((r-1) mod s)+1 is the position in the packet; e.g., k=4, m=2, s=2: 1->(1,1), 2->(1,2), 3->(2,1), 4->(2,2).

The shuffle is performed by taking the card with the lowest q of each packet in sequence and stacking them on top of one another. It is a generalization of the riffle shuffle with two cards (cf. A217948) and it can be described as a permutation where (p,q) becomes (((q-1)*m+p-1)%s+1,(((q-1)*m+p-1) mod s)+1). For example, k=8, m=4, s=2, (1,1)->(1,1), (2,1)->(1,2), (3,1)->(2,1), (4,1)->(2,2), (1,2)->(3,1), (2,2)->(3,2), (3,2)->(4,1), (4,2)->(4,2); this permutation can be described using the index r as (3,2,5)(4,6,7).

The terms of the sequence are the values of k for which the permutation consists of only one orbit with k-2 passages (e.g., k=6, m=3, s=2 is (3,2,4,5)).

Sequence A217948 is a subsequence of this one as it takes into consideration only the m=2 case.

If the formula is true then Tiago Januario's conjecture on A217948 would be solved (see formula).

Links

• Mauro Rigo, Table of n, a(n) for n = 1..5000

Crossrefs

Cf. A217948, A225184.

Programs

MATLAB

arr = []; for i = 4:1000 pdiv = 2:ceil(sqrt(i)); divisors = pdiv(rem(i, pdiv)==0); stop = 0; for j = divisors if ~stop ndiv = j; neldiv = i/j; a0 = 1; b0 = 2; a = a0; b = b0; a1 = 0; b1 = 0; operations = 0; while a1~=a0 || b1~=b0 b1 = mod((b-1)*ndiv+a-1, neldiv)+1; a1 = floor(((b-1)*ndiv+a-1)/neldiv)+1; operations = operations + 1; a = a1; b = b1; end if operations==i-2 arr = [arr, i]; stop = 1; end end end end

Formula

Apparently a(n) = A225184(n+1) + 1.