A373461 -id:A373461 - cp's OEIS frontend

A323712 Number of the following described shuffles required to return a deck of n cards to its original state. Create two piles by alternating a card from the top of the deck left-right-left-right until the deck is exhausted. Then, placing the left pile on top of the right pile constitutes one shuffle.

1, 1, 3, 4, 4, 6, 6, 3, 9, 5, 5, 12, 12, 4, 12, 8, 8, 9, 9, 6, 6, 22, 22, 20, 20, 9, 27, 28, 28, 10, 10, 5, 15, 12, 12, 36, 36, 12, 12, 20, 20, 7, 7, 12, 36, 46, 46, 42, 42, 8, 24, 52, 52, 20, 20, 9, 9, 29, 29, 60, 60, 6, 18, 12, 12, 33, 33, 22, 66, 70, 70, 18

Offset: 1

David Lovler, Jan 24 2019

nonn

The card shuffling procedure is the same for even n and odd n.
Here are a few conjectures.
a(n) <= n for all n.
a(p)=a(p-1) and a(p)|p-1 when p is a prime >= 5.
a(n)=a(n-1) and a(n)|n-1 for nonprimes 341=31*11 and 22369621=8191*2731 and probably other pseudoprimes of the form p*((p+2)/3) where p is a Mersenne prime and (p+2)/3 is prime.
n cards are returned to their original state after n shuffles when n=1, 3, 4, 6, 9, 12, 22, 27, 28, 36, 46, 52, 60, 70, 78, 81, ... (A373461) . These values of n are either of the form p-1 where p is an odd prime number or 3^i, i >= 0.
a(c) is relatively small (compared with nearby values) when c is a Catalan number.
a(2n+1)=3*a(2n) or a(2n+1)=a(2n) for all n.

			For n=4, {a1,a2,a3,a4}-->{a3,a1,a4,a2}-->{a4,a3,a2,a1}-->{a2,a4,a1,a3}-->{a1,a2,a3,a4}, so a(4)=4.
For n=5, {a1,a2,a3,a4,a5}-->{a5,a3,a1,a4,a2}-->{a2,a1,a5,a4,a3}-->{a3,a5,a2,a4,a1}-->{a1,a2,a3,a4,a5}, so a(5)=4.

Alois P. Heinz, Table of n, a(n) for n = 1..1024

Cf. A024222, A022998, A163776, A373416 (fixed points).

pileShuf := proc(L::list)
    local i,n,shf ;
    shf := [] ;
    n := nops(L) ;
    if type(n,'odd') then
        for i from n to 1 by -2 do
            shf := [op(shf),op(i,L)] ;
        end do:
        for i from n-1 to 2 by -2 do
            shf := [op(shf),op(i,L)] ;
        end do:
    else
        for i from n-1 to 1 by -2 do
            shf := [op(shf),op(i,L)] ;
        end do:
        for i from n to 2 by -2 do
            shf := [op(shf),op(i,L)] ;
        end do:
    end if;
    shf ;
end proc:
A323712 := proc(n)
    local L,itr,isord,i;
    L := [seq(i,i=1..n)] ;
    for itr from 1 to n! do
        L := pileShuf(L) ;
        isord := true ;
        for i from 1 to nops(L) do
            if op(i,L) <> i then
                isord := false ;
                break ;
            end if;
        end do:
        if isord then
            return itr ;
        end if;
    end do:
    -1 ;
end proc:
seq(A323712(n),n=1..50) ; # R. J. Mathar, Aug 02 2024

perm(n, vn) = {my(va = List(), vb = List()); for (k=1, n, if (k % 2, listput(va, vn[k]), listput(vb, vn[k]));); Vec(concat(Vecrev(va), Vecrev(vb)));}
a(n) = {my(vn = vector(n,k,k), vs = perm(n, vn), nb = 1); while (vs != vn, vs = perm(n, vs); nb++); nb;} \\ Michel Marcus, Feb 06 2019

a(2^m) = m if m is odd, a(2^m) = 2m if m is even. - Alois P. Heinz, Feb 15 2019

A373352 Factor of n generated by William B. Hart's 'one line' factoring algorithm.

Original entry on oeis.org

1, 2, 1, 2, 1, 2, 1, 2, 3, 2, 1, 2, 1, 2, 3, 4, 1, 6, 1, 4, 3, 2, 1, 4, 5, 2, 3, 2, 1, 6, 1, 4, 3, 2, 5, 6, 1, 2, 3, 4, 1, 6, 1, 4, 5, 2, 1, 6, 7, 10, 3, 2, 1, 6, 5, 8, 3, 2, 1, 6, 1, 2, 7, 8, 5, 6, 1, 4, 3, 10, 1, 6, 1, 2, 15, 4, 7, 6, 1, 8, 9, 2, 1, 6, 5, 2

Offset: 1

Peter Luschny, Jun 22 2024

nonn

The algorithm finds a nontrivial factor of n. If it returns 1 then n is an odd prime or 1. It has heuristic running time O(n^(1/3 + eps)).

William B. Hart, A One Line Factoring Algorithm, J. Aust. Math. Soc. 92 (2012), 61-69.

Cf. A373461.

from math import isqrt
from sympy.ntheory.primetest import is_square
from sympy import igcd
def a(n):
    k = -1
    while True:
        k += n
        s = isqrt(k) + 1
        m = pow(s, 2, n)
        if is_square(m):
            return igcd(n, s - isqrt(m))
print([a(n) for n in range(1, 87)])

cp's OEIS Frontend

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

PARI

Formula