Restoring order in a deck of playing cards (II)

Question

Michelle has a deck of 52 playing cards in a pile with their backs facing up. She takes the first 2 cards in the pile, turns them over, and places them at the bottom of the pile. She now takes the next 3 cards in the pile and, once again, turns them over, and places them at the bottom of the pile. She proceeds like this, taking each time the next prime number of cards from the top, turning them over, and placing them at the bottom of the deck. Once she has done this for all primes up to 47 (the largest prime less than 52), she continues counting in the same fashion with the next primes, 53, 59, 61,..., but taking them module 52 (the residue after dividing by 52), that is 1, 7, 9, etc.

Will the deck of cards ever have all their backs facing up again?

Answer 1

Basically, what we are asking here is if a sum of primes (modulo 52) will ever result in a sum that is a multiple of 104. Intuitively I believe this should occur, but I actually ran a simple script to see if this is the case and:

I found that this first occurs when adding the 49th prime number, 227, your resulting sum is 1144, equal to 104*11, so a total of 11 cycles have occurred and you have returned to a deck with all cards facing up. This later occurs when adding 449 (sum of 2080), 653 (sum of 3016), 739 (sum of 3328), and 1063 (sum of 4680).

Answer 2

So far:

Using the same techniques as the Part I puzzle, but generating the primes.
I have run a code with $50847534$ operations, using primes $\lt 10^9$.
The deck was not restored.

Investigations proceed. . .

Update:

I have run a code with $189961812$ operations, using primes up to $4 \times 10^9$.
The deck was not restored.

Edit:

I have run a revised code with $1300005926$ operations, using primes up to $3 \times 10^{10}$.
The deck was not restored.

This is the limit (for now) of what I can do with the Visual C compiler which gives a program less than 2 Gb memory to use. I got this far by implementing the sieve of Eratosthenes with bit fields. The running time was 17 minutes.

So it appears that a mathematical or deductive proof is needed.

Answer 3

There seems to be a typo in the post, or an intentional fakeout. The setup says the cards are

in a pile with their backs facing up

meaning the deck is facing down, but the question asks whether it

will ever have all the cards face up again?

The deck has not previously been facing up, so I'll err on the side of caution and take it that the question asks whether the pile will face up more than once when shuffled in the described manner and starting face down.

EDIT: The following up to and including the C++ code has been proven wrong.

Since we are drawing cards in order, whenever the sum of cards flipped is a multiple of 52, the entire deck will be either facing up or down. The deck starts face down, so it will be face down again only when we've flipped a multiple of 104 cards. Ergo it faces up when the number of cards flipped is divisble by 52 but not 104.

I wrote a short, somewhat optimized C++ snippet to determine when the desired states are reached. Here are the highlights of the output:

All cards are facing down after 49 primes! (last prime: 227)
All cards are facing down after 87 primes! (last prime: 449)
All cards are facing up after 117 primes! (last prime: 643)
All cards are facing down after 119 primes! (last prime: 653)
All cards are facing down after 131 primes! (last prime: 739)
All cards are facing down after 179 primes! (last prime: 1063)
All cards are facing down after 203 primes! (last prime: 1237)
All cards are facing up after 319 primes! (last prime: 2113)

And here the code:

#include <iostream>
// Returns whether the given number n > 3 is a prime.
bool isPrime(long n) {
    if(n%2 == 0 || n%3 == 0) return false;
    for(int i = 6; (i-2)*i + 1 <= n; i += 6) {
        if(n % (i-1) == 0) return false;
        if(n % (i+1) == 0) return false;
    }
    return true;
}
// Returns the closest prime larger than the given number.
int nextPrime(int n) {
    while(!isPrime(++n)) { continue; }
    return n;
}

int main() {
    const short DECK_SIZE = 52;
    short faceUp = 5;
    unsigned int steps = 2;
    long prime = 3;
    unsigned short timesDeckWasFaceUp = 0;
    while(timesDeckWasFaceUp != 2) {
        do { // Run until all cards are facing up again.
            prime = nextPrime(prime);
            ++steps;
            // Number of cards to flip this turn.
            short flips = prime % DECK_SIZE;
            std::cout << "Face up: " << (faceUp > DECK_SIZE ? (DECK_SIZE << 1) - faceUp : faceUp) << "\nPrime: " << prime << "\nFlipping: " << flips << " cards.\n\n";
            faceUp = (faceUp + flips) % (DECK_SIZE << 1);
            if(faceUp % DECK_SIZE == 0) { // Entire deck faces in one direction
                if(faceUp) {
                    std::cout << "All cards are facing up after " << steps << " primes! (last prime: " << prime << ")\n";
                    ++timesDeckWasFaceUp;
                    break;
                } else {
                    std::cout << "All cards are facing down after " << steps << " primes! (last prime: " << prime << ")\n";
                }
            }
        } while(faceUp % (DECK_SIZE << 1) != 0);
    }
    return 0;
}

EDIT: Here the revised code that accounts for the fact that the order of the flipped cards gets reversed.

#include <iostream>
#include <deque>
// Checks if the given number > 3 is a prime.
bool isPrime(unsigned long long n) {
    if(n%2 == 0 || n%3 == 0) return false;
    for(unsigned long long i = 6; (i-2)*i + 1 <= n; i += 6) {
        if(n % (i-1) == 0) return false;
        if(n % (i+1) == 0) return false;
    }
    return true;
}
// Returns the nearest prime larger than the given number.
unsigned long long nextPrime(unsigned long long n) {
    while(!isPrime(++n)) { continue; }
    return n;
}

void flipCards(int flips, std::deque<bool>& cards, unsigned short& counter) {
    // Flip the order of the top cards
    std::reverse(cards.begin(), cards.begin() + flips);
    // Turn each card around
    std::deque<bool> flipped(cards.begin(), cards.begin() + flips);
    for(bool& card : flipped) {
        counter += (card) ? -1 : 1;
        card = !card;
    }
    // Remove the cards from the top
    std::deque<bool>(cards.begin()+flips, cards.end()).swap(cards);
    // Add them to the bottom
    cards.insert(cards.end(), flipped.begin(), flipped.end());
}

int main() {
    const short DECK_SIZE = 52;
    // Keep track of how many cards are facing down.
    unsigned short faceUp = 0;
    std::deque<bool> cards(52);
    // Flip the first two primes (2 + 3).
    flipCards(5, cards, faceUp);
    // Keep track of the number of primes flipped.
    unsigned int steps = 2;
    unsigned long long prime = 3;
    unsigned short timesFaceUp = 0;
    while(timesFaceUp != 2) {
        // Run until no more cards are facing down.
        while(true) {
            prime = nextPrime(prime);
            ++steps;
            // Number of cards to flip this turn.
            unsigned short flips = prime % 52;
            flipCards(flips, cards, faceUp);
            if(faceUp % 52 == 0) {
                if(faceUp) {
                    std::cout << "All cards are facing up after " << steps << " primes! (last prime: " << prime << ")\n";
                    ++timesFaceUp;
                    break;
                } else {
                    std::cout << "All cards are facing down after " << steps << " primes! (last prime: " << prime << ")\n";
                }
            }
        }
    }
    return 0;
}

I'm afraid Weather Vane's answer may be correct.

Answer 4

I'll go with

Yes, because given infinite time, every possible deck state will repeat indefinitely many times.

That's because

1. There are infinitely many primes
2. There are finitely many deck states, and
3. There are no patterns in the primes (mod 52) that would exclude one state or another.

The first two points are pretty easy to prove:

1: If there were finitely many primes, one of them would be the largest prime, and we could call it the Big-P. Now, multiplying all the primes together and adding one, we would get a new number Bigger-X. It is larger than Big-P, and not divisible by any prime smaller than (or equal to) Big-P. That means that either Bigger-X is prime, or Bigger-X is divisible by some prime(s) bigger than Big-P. This is a contradiction, which means that Big-P cannot exist, and therefore "there's always a bigger prime".

2: Since we don't care about the actual order of the cards, only whether they are face-up or not, the deck has $2^{52}$ possible states, which is a big number (abt. 4.5 quadrillion (US reckoning)), and very definitely finite.

The third proposition is a lot harder to prove, but here's my go:

All but the first two primes are of the form $6n\pm1$. Because 52 is not divisible by 6, taking modulo 52 of such numbers makes every odd number between 1 and 51 possible, and equally likely over a long period of time, even if there were a hitherto unknown secret pattern in the huge primes.

Since the number of flipped cards is always odd, the number of face-up cards in the deck switches between odd and even every time, making each kind equally likely.

Therefore no particular deck state is preferred over another, and each state will occur equally likely in a given (even-length) sequence of states.

This is enough to show the result, because

The probability of any given state occurring in some sequence of two consecutive states is non-zero ($2^{-51}$ actually, because of the abovementioned parity issue), so given infinitely many of these sequences, every state will occur infinitely many times.

Answer 5

Yes, though it would probably take a bit.

Once we really start getting into the big primes we know that # mod 52 is going to be effectively random... but always odd. The idea that random card-moves will get you back to all cards face-down isn't a crazy notion... there are some really big numbers under infinity. But the restriction of using only odd-moves presents a potential problem. We did, after all, make an even-card move initially since 2 is prime.

It ends up being not that important. I played around with it and I can show that any state of cards being up/down can become any other state of cards being up/down. It's not even that hard, honestly. Here's an example of 8 cards, where the first move was 2 cards and the remaining moves were odd.



That example is really trivial but with the right goals in mind you can always improve your standing in a move or two. I would therefore say any state of 52 cards could become face-down within 104 moves. Of course, the actual output from our prime sequence isn't going to agree with what we wanted... usually. The idea is that at any given point, you want a particular sequence to get back to all face-down and it will take a while but somewhere down the number-line you will eventually get it. Solvable by computer? I suspect not. 2^52 possible states is a bit much, and I see no reason one would be more likely than another.

Answer 6

I am going to be the first to say that the answer is no, the deck will never again be in order.

I have no real proof other than the following intuition. The frequency of primes is generally known, but only for very large numbers, and it is only a guide, not exact. Thus, the difference modulo 52 will be mostly random. As a result, we are randomly flipping subsets of cards, so unless we manage to be very fortuitous, we will never get back to in-order.

However, I could be dead wrong - we are dealing with an infinite number of flips.