52 Factorial(czep.net)
czep.net
52 Factorial
https://czep.net/weblog/52cards.html
64 comments
And maybe Joyce was a fan of the Brothers Grimm! [1]
"The third question is, how many seconds of time are there in
eternity?" Then said the shepherd boy: "In Lower Pomerania is the Diamond
Mountain, which is two miles and a half high, two miles and a half wide,
and two miles and a half in depth; every hundred years a little bird
comes and sharpens its beak on it, and when the whole mountain is worn
away by this, then the first second of eternity will be over."
Love it!
I think it is a somewhat common analogy in catechistic texts but I’m not positive. I don’t think anyone could write it quite like Joyce though!
I think it is a somewhat common analogy in catechistic texts but I’m not positive. I don’t think anyone could write it quite like Joyce though!
The number has 12 zeroes at the end, which confused me for a bit, so I'm leaving this comment in case anyone else is similarly confused and would like to know why.
There are 10 total numbers between 1 and 52 which include 5 as a factor (5 which also include 2 as a factor to make a factor of 10 and 5 more to be multiplied with a bunch of other 2-factor numbers) so intuitively I was thinking there should be 10 zeroes. The two I missed are additional factors of 5, one each in 25 and 50.
There are 10 total numbers between 1 and 52 which include 5 as a factor (5 which also include 2 as a factor to make a factor of 10 and 5 more to be multiplied with a bunch of other 2-factor numbers) so intuitively I was thinking there should be 10 zeroes. The two I missed are additional factors of 5, one each in 25 and 50.
The cute general theorem is: if p is a prime number then the number of times p divides n factorial is floor(n/p) + floor(n/p^2) + floor(n/p^3) + ...
And from this (or by other arguably more elegant means) one can get the related cute theorem: the number of times p divides the binomial coefficient (n choose r) is the number of carries that occur when adding r to n-r in base p.
In particular, if n = p^k then unless r=0 or r=n there is always at least one carry because n is "longer" than r and n-r, so all the binomial coefficients (p^k choose r) are multiples of p apart from (p^k choose 0) and (p^k choose p^k).
(You can use this sort of idea to understand why, if you write out many many rows of Pascal's triangle mod 2, you get a sort of Sierpinski gasket thing.)
And from this (or by other arguably more elegant means) one can get the related cute theorem: the number of times p divides the binomial coefficient (n choose r) is the number of carries that occur when adding r to n-r in base p.
In particular, if n = p^k then unless r=0 or r=n there is always at least one carry because n is "longer" than r and n-r, so all the binomial coefficients (p^k choose r) are multiples of p apart from (p^k choose 0) and (p^k choose p^k).
(You can use this sort of idea to understand why, if you write out many many rows of Pascal's triangle mod 2, you get a sort of Sierpinski gasket thing.)
2^49×3^23×5^12×7^8×11^4×13^4×17^3×19^2×23^2×29×31×37×41×43×47
There is a 5^12 and more than that for the 2s. So yes 12 zeros it will be as God intended.
https://www.wolframalpha.com/input?i=factors+of+806581751709...
There is a 5^12 and more than that for the 2s. So yes 12 zeros it will be as God intended.
https://www.wolframalpha.com/input?i=factors+of+806581751709...
25 and 50 contribute two 5 factors each. The multiplicity of 2 factors is even greater, as every other even factor contributes at least two, every fourth at least three, etc.
In terms of actually playing games with cards, the effective number of permutations can be much smaller (though still large enough to be going on with). In many card games, the suits are distinct but functionally identical; you could swap spades rank-for-rank with hearts and get a functionally equivalent deck. In Klondike solitaire, the tableau is concerned with red cards and black cards, not all four suits.
I imagine somebody has done research on this: for a given card game, how many functionally distinct shuffles there are.
I imagine somebody has done research on this: for a given card game, how many functionally distinct shuffles there are.
I remember looking at some early Draw Poker machines in Las Vegas back in the late 80's/early 90's, and thinking about pseudo-random number generation (as it existed at that time). If it was using a standard linear-congruential RNG with a 16 bit value, there would be only 65536 possible seeds, and hence only that many distinct sequences of random numbers, and hence only that many possible shuffles. Even a 64-bit RNG would have only 1.844674407370955e+19 possible shuffles, far lower than 52!.
When playing draw poker, you only need to select 10 cards from the deck, because the other cards will never be played. So that's 52⋅51⋅…⋅43 = 57,407,703,889,536,000, which needs 56 bits.
ln(52!)/ln(2)≈226 bits. You don't have to depend on a single random 64-bit number: https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
If the RNG has < 226 bits of state, such as most non cryptographic PRNGs, you cannot reach all shuffles even if you use multiple numbers.
Hey, sorry to contact you via this method. I meant to reply to your comment under the thread on SCALE but it's locked. I'm expecting an offer from that company and would like to ask you about your experience there. If you don't mind, could you accept my connection request on LinkedIn and we could chat there? Thank you :)
I'm not totally sure that's true. I get where you are coming from, an 8 bit rng can only output 256 distinct values at most. 256 would be the longest cycle.
However if you combine the outputs of two, but don't step them at the same time, you can have more outputs.
Imagine you had one that outputs just 0 and 1 and then loops. You could have two of these updating at a different frequency and have four distinct outputs.
I think that makes sense.
However if you combine the outputs of two, but don't step them at the same time, you can have more outputs.
Imagine you had one that outputs just 0 and 1 and then loops. You could have two of these updating at a different frequency and have four distinct outputs.
I think that makes sense.
Oh, yeah, there are ways to finesse it. I’m just wondering whether anyone involved in those early poker machines had made the effort.
In Nevada one was required to “prove the randomness” of random outcomes in video poker machines as well as other electronic gambling machines. So effort was made.
You're right. There are also game rules that can act as multipliers (e.g. who has the blind affects the game state in poker - so that means that there are actually multiple "games" for each given shuffle).
Something you may find interesting is formal methods - what we're talking about here are "equivalence classes". In formal methods you want to analyze the totality of a system and understand every outcome based on every possible state within the rules of the system. Clearly this is a combinatoric nightmare in anything interesting (even a simple system like a card game and 52 cards, as we can see). Equivalence classes are a way of knowing distinct, but not actually different, states, and grouping them together so that they can all be considered just once.
Something you may find interesting is formal methods - what we're talking about here are "equivalence classes". In formal methods you want to analyze the totality of a system and understand every outcome based on every possible state within the rules of the system. Clearly this is a combinatoric nightmare in anything interesting (even a simple system like a card game and 52 cards, as we can see). Equivalence classes are a way of knowing distinct, but not actually different, states, and grouping them together so that they can all be considered just once.
Those interested can read Mark Conger's thesis to learn about the mathematics of repeated cards: https://websites.umich.edu/~mconger/thesis.pdf
Pretty easy to calculate how many distinct shuffles considering only the numbers: 52!/(4!^13)=~9.2e49. Still monstrously big
I remember reading once that every time you shuffle a deck of cards, it's almost certainly the first time any deck of cards has ever been in that configuration. Seeing how outrageously large 52! is puts this into perspective.
Most likely not true, since many shuffles are from a sorted deck (original buy, result of playing out some game, etc...). The 52! possibilities are certainly not uniformly spread in real life.
With enough shuffles then you'll likely hit never before seen territory.
With enough shuffles then you'll likely hit never before seen territory.
This is a good Numberphile video about it - The Best (and Worst) Ways to Shuffle Cards: https://youtube.com/watch?v=AxJubaijQbI
Some debate, but it seems that ! was used for factorial to replace another symbol that was less easy to print https://math.stackexchange.com/questions/802141/history-of-n....
I sometimes wake up having an anxiety attack because my dream was attempting to play something like this out- always something to do with permutations of massive numbers. It was a little bit of a challenge to keep it together while reading this. No idea why that is, either. It's the only thing that has such an effect on me.
Hit the pressure release valve. Next time this happens look around and find the button or lever or old fashioned knife switch labeled "pressure release valve" or something like that and push/pull/flip/throw it.
(I'm seriously. The brain works like that. Draw a door on the wall and open it and walk through.)
(I'm seriously. The brain works like that. Draw a door on the wall and open it and walk through.)
Have you ever dreamt of Graham's number?
I have something similar but for lambda terms with huge normal forms, I always wake up exhausted when this happens
Wow. I read your comment a few hours ago. Disturbed sleep, the tight little loops of information retrieval, processing and repeat. That feeling of exhaustion. It’s real. It’s happening to me right now. What’s new is I knew I’d be here, writing this, all those hours ago. Mixed with the cards and the Maths.
> This number is beyond astronomically large.
52! ~ 10^67 is far many orders of magnitude than the number of particles in the universe, which is exactly an astronomical number.
52! ~ 10^67 is far many orders of magnitude than the number of particles in the universe, which is exactly an astronomical number.
A word got lost, but current estimates for Universe particles are around 10^80, so 52! is 13 magnitudes smaller.
This thought experiment gets even wilder if you like to live dangerously and leave two jokers and the rules card in the deck. 55 factorial is even larger
The jokers are indistinguishable, so it's only 55 factorial divided by two.
Sometimes they are distinct, usually one is black & white and the other is color.. the solitaire cipher makes use of this distinction.
Youtuber "But Why" marvels at the size of 52! in https://www.youtube.com/watch?v=hoeIllSxpEU and then tries to relate it to something graspable by humans https://www.youtube.com/watch?v=RdnVhjYFr7w
You can use one deck to encode 225 bits of information.
277 if we encode information in whether each card is face up or down
Not quite, because you won't be able to tell the deck orientation any more.
So, then 275? With the both the top and bottom card face down?
That's going in my next spy novel. Spy 1 gets together with Spy 2, for cracking game of Cribbage, and at the end, Spy 2 walks out with a deck of cards, but it's actually a 256 bit encryption key.
That's going in my next spy novel. Spy 1 gets together with Spy 2, for cracking game of Cribbage, and at the end, Spy 2 walks out with a deck of cards, but it's actually a 256 bit encryption key.
Some cards are not symmetrical, (e.g. any seven or a five of not-diamonds) so they can encode two bits of information.
Yeah, I actually implemented this some years ago here, for UTF-8 text: https://github.com/Michael-Zinn/cardfs
Works for Poker, Skat, Tarot and Quartett decks.
Works for Poker, Skat, Tarot and Quartett decks.
A tarot deck has more than only trumps. It also has fourteen non-trumps in each of four suits (Latin-suited or French-suited depending on the deck), so the total number of cards (trumps and non-trumps) is 78.
Furthermore, if you can store bytes, then why should it need to be UTF-8? Not all data is text, and not all text is Unicode (and not all Unicode text is most efficient with UTF-8). As far as I can tell, the only part of the program that requires it to be UTF-8 is the "decode_array_to_string" function (although I think it will have to be a string without embedded null characters since that is how argv is working, and that could possibly allow you to store a few more bytes, if the data is required to not have null characters).
Furthermore, if you can store bytes, then why should it need to be UTF-8? Not all data is text, and not all text is Unicode (and not all Unicode text is most efficient with UTF-8). As far as I can tell, the only part of the program that requires it to be UTF-8 is the "decode_array_to_string" function (although I think it will have to be a string without embedded null characters since that is how argv is working, and that could possibly allow you to store a few more bytes, if the data is required to not have null characters).
Thanks for pointing this out, I did not know that there are other tarot decks (I only have this one https://steemit.com/software/@michaelzinn/store-text-in-a-de... )
I originally had planned to store other data as well (that's why it's called "CardFS"): With the bytes, there is another multiplier 3 in there, which is unused. My plan was to do 0=UTF-8 text, 1=raw bytes, 2=bitmap graphic, but I stopped working on it after I got the UTF-8 text working.
Excluding NUL characters would only up the byte count to floor(log_255(52!)), which is still 28 bytes (though it increases the unused multiplier from 2.99 to 3.1, which makes it possible to use all bytes in all three file types), but how would you then store texts that use fewer than the maximum number of characters? Fill it with spaces?
I originally had planned to store other data as well (that's why it's called "CardFS"): With the bytes, there is another multiplier 3 in there, which is unused. My plan was to do 0=UTF-8 text, 1=raw bytes, 2=bitmap graphic, but I stopped working on it after I got the UTF-8 text working.
Excluding NUL characters would only up the byte count to floor(log_255(52!)), which is still 28 bytes (though it increases the unused multiplier from 2.99 to 3.1, which makes it possible to use all bytes in all three file types), but how would you then store texts that use fewer than the maximum number of characters? Fill it with spaces?
And despite the huge size of 52!, it is possible with basic motor skills to produce a random deck. For those with the background and interest, there is a great book: The Mathematics of Shuffling Cards by Diaconis and Fulman, published 2023.
Animated version by VSauce [1] starting at about 15 minutes.
[1] https://www.youtube.com/watch?v=ObiqJzfyACM
[1] https://www.youtube.com/watch?v=ObiqJzfyACM
Is it safe to say that it's almost certain that no two people have ever shuffled a deck of cards in the exact same order?
No, due to suboptimal shuffling strategies. If you shuffle exactly the wrong way, you can even end up with the cards in their original order.
Yep, this. Matt Parker makes a convincing argument that multiple people have accidently performed a perfect Faro shuffle when trying to randomize a new deck of cards
https://www.youtube.com/watch?v=s9-b-QJZdVA
https://www.youtube.com/watch?v=s9-b-QJZdVA
Given the set of people who can competently shuffle a deck of cards. No, there has never been an identical deck, and there never will be. This would be true even if every human ever dedicated their entire life to randomly shuffling decks looking for a repeat.
Even if all compute on earth was focused on shuffling as many decks as fast as possible, we still wouldn't ever get two identical decks. Even after hundreds of millions of trillions of years.
The odds of getting two identical shuffles is somewhere around the odds of picking the correct sand grain sized piece of matter, out of all matter in the Milky Way.
Even if all compute on earth was focused on shuffling as many decks as fast as possible, we still wouldn't ever get two identical decks. Even after hundreds of millions of trillions of years.
The odds of getting two identical shuffles is somewhere around the odds of picking the correct sand grain sized piece of matter, out of all matter in the Milky Way.
That would only be safe if you assumed everyone shuffled well.
The likelihood that more than one person used a poor or lazy shuffling technique on a brand new deck of cards seems significant.
The likelihood that more than one person used a poor or lazy shuffling technique on a brand new deck of cards seems significant.
[deleted]
So if I want a collection of card decks in every possible combination I should start collecting now, got it.
With this, you could invent a very unique magic trick where your spectator well-shuffles a deck of cards, then you can secretly swap your deck with one of the decks from your collection to reveal that yours was shuffled in the exact same way.
This is a relatively well known technique in card manipulations known as a "cold deck". There are many variations of it involving probabilistic but not entirely deterministic forces that lead to a branching path to a different cold deck.
mass of Earth is 6×10^27 kg
mass of the Milky Way is 6x10^42 kg
mass of the visible Universe is 1.5×10^53 kg
Quality deck of cards weighs 0.3 kg. All deck combinations would weigh 2.4×10^67 kg.
= 10^14 times the mass of the visible Universe.
You need many multiverses to store all those cards.
mass of the Milky Way is 6x10^42 kg
mass of the visible Universe is 1.5×10^53 kg
Quality deck of cards weighs 0.3 kg. All deck combinations would weigh 2.4×10^67 kg.
= 10^14 times the mass of the visible Universe.
You need many multiverses to store all those cards.
Or just make each deck 10^14 times smaller
Reminds of "Could you fold a sheet of paper on itself 64 times?". "No problem! It's easy". Until you try or think about powers of 2 and calculate the height of the thickness of the sheet multiplied by 2^64. 64 might by replaced by 32 to make it seem more approcheable. That's funny how counter-intuitive it might be.
32 is far too many as the World Record is currently 12 times: https://www.guinnessworldrecords.com/world-records/494571-mo...
I remember as a kid being told that it was impossible to fold a piece of paper in half 8 times and most of the time, that's true unless you use a very long and thin bit of paper.
I remember as a kid being told that it was impossible to fold a piece of paper in half 8 times and most of the time, that's true unless you use a very long and thin bit of paper.
That would be a serious magic trick, as that's the explanation given to the rubes.
Some sort of auto-shuffling machine with some computer vision to match the shuffling in real time... still a magic trick, a different kind of impressive. But that guy who makes robots at home and does videos would love a project like this. I seriously doubt it would work.
Some sort of auto-shuffling machine with some computer vision to match the shuffling in real time... still a magic trick, a different kind of impressive. But that guy who makes robots at home and does videos would love a project like this. I seriously doubt it would work.
52! is not small. Yet factorials grow slowly compared to the Ackerman function
or "busy beavers":
https://www.quora.com/What-is-the-fastest-growing-mathematic...
https://www.quora.com/What-is-the-fastest-growing-mathematic...
And there are 26 letters in the english language, which is 52/2.
Combinatorial problems are hard. The number of ways to arrange N guests in N seats at a seated event (such as a wedding or gala) is N!. Even with only 60 guests, there are already more possible seating permutations that there are believed to be atoms in the observable universe. The solution space for hundreds of guests is mind boggling large. I sometimes try to explain this to customers of my seating planning software (PerfectTablePlan) when they complain that the auto seating algorithm has separated 2 people in a 500 seat event, but I don't think many of them understand!
> What must it be, then, to bear the manifold tortures of hell forever? Forever! For all eternity! Not for a year or an age but forever. Try to imagine the awful meaning of this. You have often seen the sand on the seashore. How fine are its tiny grains! And how many of those tiny grains go to make up the small handful which a child grasps in its play. Now imagine a mountain of that sand, a million miles high, reaching from the earth to the farthest heavens, and a million miles broad, extending to remotest space, and a million miles in thickness, and imagine such an enormous mass of countless particles of sand multiplied as often as there are leaves in the forest, drops of water in the mighty ocean, feathers on birds, scales on fish, hairs on animals, atoms in the vast expanse of air. And imagine that at the end of every million years a little bird came to that mountain and carried away in its beak a tiny grain of that sand. How many millions upon millions of centuries would pass before that bird had carried away even a square foot of that mountain, how many eons upon eons of ages before it had carried away all. Yet at the end of that immense stretch time not even one instant of eternity could be said to have ended. At the end of all those billions and trillions of years eternity would have scarcely begun. And if that mountain rose again after it had been carried all away again grain by grain, and if it so rose and sank as many times as there are stars in the sky, atoms in the air, drops of water in the sea, leaves on the trees, feathers upon birds, scales upon fish, hairs upon animals – at the end of all those innumerable risings and sinkings of that immeasurably vast mountain not even one single instant of eternity could be said to have ended; even then, at the end of such a period, after that eon of time, the mere thought of which makes our very brain reel dizzily, eternity would have scarcely begun.
(From Portrait of the Artist)