0

I'm working on a problem about shuffling decks, using https://mathworld.wolfram.com/Out-Shuffle.html

So I need to find all deck sizes $n$ where you can shuffle (using out-shuffle) so that it returns to the original order in a given number $k$ shuffles.

What I've gathered, after help from the friendly folks here at Math Stack Exchange, is that I need to factorize the following, for my given $k$:

$$ 2^{k} \equiv 1 \mod (n-1) $$

i.e factorize for

$$ 2^{k} - 1 $$

For $k=8$, I know from a brute-force attempt, that the correct list of deck sizes should be:

$$ [18, 52, 86, 256] $$

How do I go from the above formulas to all the divisors, to this list?

Lê Thành Đạt
  • 4,228
gunnar2k
  • 3
  • 4
  • 3
    Why $(n-1)$ and not $n$? As for solution, just factor $2^{60}-1$, it is easy. – metamorphy Mar 18 '20 at 11:38
  • @metamorphy Im sorry, I dont understand what you mean by just factoring – gunnar2k Mar 18 '20 at 11:40
  • 2
    The congruence means that $\ n-1\mid 2^{60}-1\ $, so you just have to find the divisors of $2^{60}-1$ – Peter Mar 18 '20 at 11:41
  • Thank you everyone! Extremely helpful! – gunnar2k Mar 18 '20 at 12:04
  • The problem relates to this https://mathworld.wolfram.com/Out-Shuffle.html but I seem to be missing something – gunnar2k Mar 18 '20 at 14:04
  • When I test for k=8, ie 2^8 = 1, I get prime factors 3, 5, 17, with solutions for n=[16, 52, 86, 256], which is wrong. I should be getting n=[18, 52, 86, 256].. – gunnar2k Mar 18 '20 at 14:06
  • ok, sorry, I will make an edit – gunnar2k Mar 18 '20 at 14:20
  • Why are you leaving the single primes $+ 1$ out of your list? The $18$ is $\ 17+1\ $, and divisors of $\ 2^8-1\ $ are $\ 1, $$3, $$5, $$17,$$ 3\times5,$$ 3\times17, $$5\times17\ $ and $\ 3\times5\times17\ $, omitting the unit $1$ and adding $1$ to the rest of those numbers gives you $\ 4,$$6,$$18,$$16,$$52,$$86\ $, and $256$. Why do you omit $\ 4, 6\ $ and $\ 18\ $ from your original list (and $\ 4, 6\ $ and $16$ from what you apparently regard as the "correct" list)? And why do think that is the "correct" list? – lonza leggiera Mar 18 '20 at 15:12
  • @lonzaleggiera the correct list of deck sizes should be correct because I've run a more naive brute force solution with k=8 and it gives me this list of deck sizes. Problem is I cant run it for very large k's – gunnar2k Mar 18 '20 at 15:45
  • @lonzaleggiera Not sure why I'm leaving out 1s, could be because I'm using a fast prime factorization algorithm I found which does it.. – gunnar2k Mar 18 '20 at 15:46
  • You ask for what you did wrong but you don't show us what you did for us to check... – Simply Beautiful Art Mar 18 '20 at 15:50
  • @SimplyBeautifulArt Im sorry, I thought it would be enough to show my thought process – gunnar2k Mar 18 '20 at 15:58
  • Previously you had said you had gotten something else and asked for what you did wrong, yet I did not see any explanation of your thought process on how you had gotten what you did. – Simply Beautiful Art Mar 18 '20 at 16:00
  • @SimplyBeautifulArt I edited the original question to try to clarify what I want to do, which is to figure out how to get that correct list n's from that modular arithmetic formula. I'm sorry if I was unclear before. – gunnar2k Mar 18 '20 at 16:09

1 Answers1

0

While all divisors $\ d\ $ of $\ 2^8-1\ $ will satisfy the congruence $\ 2^8\equiv$$ 1\pmod{d}\ $ , you only want the ones for which $8$ is the order of $2 \pmod{d}\ $—i.e. those which do not divide $\ 2^2-1=3\ $ or $\ 2^4-1=15\ $. So, from the list of non-unit divisors $\ 3,$$5,$$17,$$15,$$51,$$85,$ and $255$, of $\ 2^8-1\ $ you have to eliminate $\ 3,$$5,$ and $15$, leaving $17,$$51,$$85$ and $255$, which gives you your list of $18,$$52,$$86,$ and $256$ as the possible values for $\ n\ $.

More generally, after getting all the divisors $\ d\ $ of $\ 2^k-1\ $, you need to eliminate any which divide $\ 2^r-1\ $ for any factor $\ r<k\ $ of $\ k\ $.

lonza leggiera
  • 28,646
  • 2
  • 12
  • 33