Giant numbers (Ex: how many primes are smaller than the largest known?)
February 7, 2015 5:40 AM Subscribe
Many sites say that the largest known prime is "2^57,885,161 − 1, a number with 17,425,170 digits." Given this and well known research about the density of primes, I think it's at least possible to estimate the number of primes between 1 and 2^57,885,161 − 1. But I don't know how to do this myself.
I really want the answer to this one (the order of magnitude at least), but I've got lots of these, and I'd ideally like more cool ones. :)
For context, I'm making an activity for high school students in an afterschool math program. The activity is aimed at understating really big numbers, and this part of the program (4 sessions) is focused on bijections and infinties, with a theme of how mathematicians think about topics that are too large or abstract to handle with intuition, and for how mathematicians make choices that shape what the mathematics we study looks like. For this activity in the first session, in addition to many mathematical examples, I want to include some examples from life and things in the middle (like the limits of modern computation.)
The activity is not to calculate these quantities, but rather to estimate them to the extent that they can be ordered least to greatest.
I would greatly appreciate
A) Suggestions for additions to this list
B) Estimations for new additions or for the items listed below with question marks
C) Corrections to this list if you think one of my listed estimations is at the wrong order of magnitude
D) An estimate for the primes question in particular.
THANKS!
----------------------------------------------------------------
The list so far:
* The number of primes between 0 and 2^57,885,161 − 1
* If two 'opponents' at Go are actually collaborating to make the game as long as possible, how many turns might the game last (on a 19x19 board)? (???)
* The number of different chess games for which the board never returns to a previously experienced state. (???)
* The approximate number of atoms in everything living on the earth (???)
* The approximate circumference of the earth in miles (~10^4)
* The approximate number of sheets of paper in a stack as tall as the height of the Transamerica Pyramid in SF (~10^6)
* The approximate number of seconds in a human life (~10^9)
* The approximate number of people in the world right now (~10^10)
* The approximate number of neurons in a human brain (~10^11)
* The approximate number of seconds between now and when a dinosaur last lived (~10^15)
* The approximate number of ants in the world right now (~10^16)
* The approximate number of calculations that can be done by the world's current fastest computer (The Tianhe-2 supercomputer) in 1 minute (~10^18)
* The approximate number of stars in the universe (~10^30)
* The approximate number of atoms in the earth and everything on it (~10^50)
* The approximate number of different ways a deck of 52 cards might be shuffled (~10^68)
* The approximate predicted number of atoms in the universe (~10^80)
* The approximate number of rabbits that would exist in the universe after a year if, starting with 2 rabbits, ever day, every pair of rabbits alive mate and produce 6 offspring, and no rabbits ever die. (~10^219)
For context, I'm making an activity for high school students in an afterschool math program. The activity is aimed at understating really big numbers, and this part of the program (4 sessions) is focused on bijections and infinties, with a theme of how mathematicians think about topics that are too large or abstract to handle with intuition, and for how mathematicians make choices that shape what the mathematics we study looks like. For this activity in the first session, in addition to many mathematical examples, I want to include some examples from life and things in the middle (like the limits of modern computation.)
The activity is not to calculate these quantities, but rather to estimate them to the extent that they can be ordered least to greatest.
I would greatly appreciate
A) Suggestions for additions to this list
B) Estimations for new additions or for the items listed below with question marks
C) Corrections to this list if you think one of my listed estimations is at the wrong order of magnitude
D) An estimate for the primes question in particular.
THANKS!
----------------------------------------------------------------
The list so far:
* The number of primes between 0 and 2^57,885,161 − 1
* If two 'opponents' at Go are actually collaborating to make the game as long as possible, how many turns might the game last (on a 19x19 board)? (???)
* The number of different chess games for which the board never returns to a previously experienced state. (???)
* The approximate number of atoms in everything living on the earth (???)
* The approximate circumference of the earth in miles (~10^4)
* The approximate number of sheets of paper in a stack as tall as the height of the Transamerica Pyramid in SF (~10^6)
* The approximate number of seconds in a human life (~10^9)
* The approximate number of people in the world right now (~10^10)
* The approximate number of neurons in a human brain (~10^11)
* The approximate number of seconds between now and when a dinosaur last lived (~10^15)
* The approximate number of ants in the world right now (~10^16)
* The approximate number of calculations that can be done by the world's current fastest computer (The Tianhe-2 supercomputer) in 1 minute (~10^18)
* The approximate number of stars in the universe (~10^30)
* The approximate number of atoms in the earth and everything on it (~10^50)
* The approximate number of different ways a deck of 52 cards might be shuffled (~10^68)
* The approximate predicted number of atoms in the universe (~10^80)
* The approximate number of rabbits that would exist in the universe after a year if, starting with 2 rabbits, ever day, every pair of rabbits alive mate and produce 6 offspring, and no rabbits ever die. (~10^219)
For your prime number question, it seems like you might want to show them trial division. This is a concrete way of understanding the concept.
Let n=2^57,885,161 − 1 and systematically test whether each prime number less than n goes into n without a remainder. Count the number of prime numbers you have tested.
If you know any programming, you can write an algorithm to do this as is shown in the Wikipedia link.
Here is a recent SciAm story about how mathematicians think about infinity.
And you could show them the documentary Dangerous Knowledge.
posted by Beethoven's Sith at 6:40 AM on February 7, 2015
Let n=2^57,885,161 − 1 and systematically test whether each prime number less than n goes into n without a remainder. Count the number of prime numbers you have tested.
If you know any programming, you can write an algorithm to do this as is shown in the Wikipedia link.
Here is a recent SciAm story about how mathematicians think about infinity.
And you could show them the documentary Dangerous Knowledge.
posted by Beethoven's Sith at 6:40 AM on February 7, 2015
This may be of interest to you: "From 1,000,000 to Graham’s Number".
posted by andoatnp at 6:47 AM on February 7, 2015 [1 favorite]
posted by andoatnp at 6:47 AM on February 7, 2015 [1 favorite]
So a cheap version of the prime number theorem mentioned above is that the ratio of pi(x) (the number of primes less than x) and the function x/ln(x) tends to 1 as x grows towards infinity. That means that although the difference between these two numbers can grow large, the relative error tends towards 0.
So we can say that 2^57,885,161 − 1 / ln (2^57,885,161 − 1) is pretty close to the number of primes less than 2^57,885,161 − 1. So how can we get a sense of how big that number is?
You can convert between the base of logs using this formula: log (base a) (x) = log (base b) (x) / log (base b) (a). Ln is log with base 'e', so let's convert to base 2 to make it easier to get the log of the power of 2:
ln(2^57,885,161 − 1) = log2 (2^57,885,161 − 1) / log2(e)
log2(2^57,885,161 − 1) will be very close to log2(2^57,885,161) which is just 57,885,161.
log2(e) = 1.443.
So the expression evaluates to around 40114456. That's around 2^25.
Now divide the original number by 2^25 and we get 2^(57,885,161 - 25) = 2^57,885,136.
How big is that in powers of ten? 10^3 is close to 2^10. 2^57,885,136 ~ (2^10)^5,788,514 ~ (10^3)^5,788,514
= 10^17,365,542.
So, a lot of primes.
(can someone check my work please!)
posted by crocomancer at 7:40 AM on February 7, 2015
So we can say that 2^57,885,161 − 1 / ln (2^57,885,161 − 1) is pretty close to the number of primes less than 2^57,885,161 − 1. So how can we get a sense of how big that number is?
You can convert between the base of logs using this formula: log (base a) (x) = log (base b) (x) / log (base b) (a). Ln is log with base 'e', so let's convert to base 2 to make it easier to get the log of the power of 2:
ln(2^57,885,161 − 1) = log2 (2^57,885,161 − 1) / log2(e)
log2(2^57,885,161 − 1) will be very close to log2(2^57,885,161) which is just 57,885,161.
log2(e) = 1.443.
So the expression evaluates to around 40114456. That's around 2^25.
Now divide the original number by 2^25 and we get 2^(57,885,161 - 25) = 2^57,885,136.
How big is that in powers of ten? 10^3 is close to 2^10. 2^57,885,136 ~ (2^10)^5,788,514 ~ (10^3)^5,788,514
= 10^17,365,542.
So, a lot of primes.
(can someone check my work please!)
posted by crocomancer at 7:40 AM on February 7, 2015
D) The prime number theorem states that the number of primes less than or equal to n is asymptotic to n/log(n). In other words, if p(n) is the number of primes less than or equal to n, then, as n goes to infinity, the ratio p(n)/[n/log(n)] goes to 1.
You're interested, more or less, in p(2^a) for a certain a (in fact, you're interested in p(2^a-1), but that's the same as p(2^a) since 2^a is definitely not prime when a>1). The PNT tells you that p(2^a) is around 2^a/log(2^a), or 2^a/(a*log(2)). (Here "log" means "natural logarithm".)
Now, the base-10 logarithm of 2 is like 0.3, and the natural logarithm of 2 is like 0.7, so, when a=57885161, you get 10^(0.3*57885161)/(0.7*57885161). So the right order of magnitude is like 10^17365540. In other words, it's dramatically bigger than anything else on your list.
There is no way you're going to be able to actually count the primes less than 2^(58 million) using trial division. However, Beethoven's Sith's answer gives all kinds of fun questions you could ask: suppose every atom in the universe were actually a CPU core; how long would it take to count all the primes less than 2^57885161?, etc.
There are some slightly more precise statements, though (I'm just looking at the Wikipedia article since IANAANT). For example, for n in the range you're talking about, p(n) is between n/(log(n)+2) and n/(log(n)-4), but this extra accuracy doesn't really make the point any more strongly.
posted by busted_crayons at 7:48 AM on February 7, 2015 [1 favorite]
You're interested, more or less, in p(2^a) for a certain a (in fact, you're interested in p(2^a-1), but that's the same as p(2^a) since 2^a is definitely not prime when a>1). The PNT tells you that p(2^a) is around 2^a/log(2^a), or 2^a/(a*log(2)). (Here "log" means "natural logarithm".)
Now, the base-10 logarithm of 2 is like 0.3, and the natural logarithm of 2 is like 0.7, so, when a=57885161, you get 10^(0.3*57885161)/(0.7*57885161). So the right order of magnitude is like 10^17365540. In other words, it's dramatically bigger than anything else on your list.
There is no way you're going to be able to actually count the primes less than 2^(58 million) using trial division. However, Beethoven's Sith's answer gives all kinds of fun questions you could ask: suppose every atom in the universe were actually a CPU core; how long would it take to count all the primes less than 2^57885161?, etc.
There are some slightly more precise statements, though (I'm just looking at the Wikipedia article since IANAANT). For example, for n in the range you're talking about, p(n) is between n/(log(n)+2) and n/(log(n)-4), but this extra accuracy doesn't really make the point any more strongly.
posted by busted_crayons at 7:48 AM on February 7, 2015 [1 favorite]
Fermi problems are really fun. A professor of mine in grad school used to give us these in our policy class. For instance, you can ask "How many pediatricians are there in Detroit?" It is possible, just by guesstimating several intermediary numbers (how many people in Detroit, what is the proportion of children to overall population, how many visits do children make on average, what is the maximum number of visits a single pediatrician can handle, etc.) to come up with a number that is within an order of magnitude of the correct answer. There is not necessarily a correct way to get to this answer, which is what makes it so fun (and the steps I showed above aren't necessarily the right ones; I can't remember how we solved it exactly). But it's surprisingly possible--as well as great fun--to get from here to there... it sounds like you've got smart kids and would like to challenge them, so they might love the challenge of these sorts of problems...
posted by faux ami at 7:50 AM on February 7, 2015
posted by faux ami at 7:50 AM on February 7, 2015
If two 'opponents' at Go are actually collaborating to make the game as long as possible, how many turns might the game last (on a 19x19 board)? (???)
This is a great thought question. The starting point, though, is to ask whether there are cycles possible with the rules of go, in which case the number of turns is not finite. It may not be immediately obvious if you don't know the game well, because pieces don't move, but there are many ways to construct a cycle using the basic stone placement rules. The simplest of these is just ko, which is prohibited by all rule sets. The reason to prohibit it is that even in an adversarial situation, it might be optimal play to not "give in" -- breaking the cycle means you lose a piece, and so optimal play means a non-terminating game. The basic ko rule in particular prohibits recapturing a piece right after it has captured a ko stone.
So then, you might ask, what if there are two kos going on? Or more? There are any number of what are termed superko rules that attempt to remedy situations like this and prevent non-terminating games (which are extremely uncommon but historically have happened, and usually get called as a draw/"no result"). The most straightforward one is to prevent repeated board configurations, this is called the positional superko rule. With positional superko (and with most superko rules), there are no legal non-finite games.
A 3 move cycle not banned by the basic ko rule would be easy to construct on a much smaller board than 19x19, so if you are trying to steer them to the infinite situation I'd go with 9x9. However, if you have a positional superko rule (or the like), then the number they are trying to estimate will be finite, and so will be affected by board size. But even so I suspect the number is going to be very large even on a smaller board, and is going to involve lots of really complicated near-cycles that just slightly avoid the superko rule in use by one piece or so, and 9x9 will be big enough for this to be a really big number.
There's some discussion of the actual answer to this question here along with a citation, but there seems to be a dispute about accuracy (I haven't tried to check it or follow up on the citation). There are at least examples of the kind of near-cycles I have in mind.
posted by advil at 8:32 AM on February 7, 2015 [1 favorite]
This is a great thought question. The starting point, though, is to ask whether there are cycles possible with the rules of go, in which case the number of turns is not finite. It may not be immediately obvious if you don't know the game well, because pieces don't move, but there are many ways to construct a cycle using the basic stone placement rules. The simplest of these is just ko, which is prohibited by all rule sets. The reason to prohibit it is that even in an adversarial situation, it might be optimal play to not "give in" -- breaking the cycle means you lose a piece, and so optimal play means a non-terminating game. The basic ko rule in particular prohibits recapturing a piece right after it has captured a ko stone.
So then, you might ask, what if there are two kos going on? Or more? There are any number of what are termed superko rules that attempt to remedy situations like this and prevent non-terminating games (which are extremely uncommon but historically have happened, and usually get called as a draw/"no result"). The most straightforward one is to prevent repeated board configurations, this is called the positional superko rule. With positional superko (and with most superko rules), there are no legal non-finite games.
A 3 move cycle not banned by the basic ko rule would be easy to construct on a much smaller board than 19x19, so if you are trying to steer them to the infinite situation I'd go with 9x9. However, if you have a positional superko rule (or the like), then the number they are trying to estimate will be finite, and so will be affected by board size. But even so I suspect the number is going to be very large even on a smaller board, and is going to involve lots of really complicated near-cycles that just slightly avoid the superko rule in use by one piece or so, and 9x9 will be big enough for this to be a really big number.
There's some discussion of the actual answer to this question here along with a citation, but there seems to be a dispute about accuracy (I haven't tried to check it or follow up on the citation). There are at least examples of the kind of near-cycles I have in mind.
posted by advil at 8:32 AM on February 7, 2015 [1 favorite]
For your prime number question, it seems like you might want to show them trial division. This is a concrete way of understanding the concept.
Let n=2^57,885,161 − 1 and systematically test whether each prime number less than n goes into n without a remainder. Count the number of prime numbers you have tested.
From the way your question is written, it sounds like you already know that this is a bad idea, but, since mathematicians are never afraid to state the obvious: this is a bad idea. I mean, it might be a good idea for a smaller n, but not for this one. There's no way for your students to ever, in the amount of time remaining until the heat death of the universe, do enough trial divisions to count the number of primes smaller than this number.
For this value of n, the prime number theorem is indeed the way to go, as people have mentioned upthread.
Cantor's diagonal argument is a very interesting example of how mathematicians deal with infinite quantities/sets. It proves that there are different sizes of infinities: in particular, it shows that the infinite set of real numbers is strictly larger than the infinite set of natural numbers.
It's somewhat of an advanced concept, but my high school math teacher taught us about this (also in an after-school advanced math program), and if you explain it well, it's totally understandable to students at that level.
Another way to illustrate infinity and how arithmetic with infinite quantities differs from ordinary arithmetic is Hilbert's Hotel. The idea there is that you have a hotel with (countably) infinitely many rooms, all of which are occupied, and you ask questions like: what do you do if another guest shows up? Well, just get the person in room 1 to move to room 2, the person in room 2 to move to room 3, and so on. So room 1 is empty, and the new guest can go to room 1. This shows that ∞+1=∞.
Then what if (countably) infinitely many people show up? Well, ask the person in room 1 to move to room 2, the person in room 2 to move to room 4, ... , ask the person in room n to move to room 2n, etc. Then all of the odd-numbered rooms are free, so each of the new guests can be accommodated. This shows that ∞×2=∞.
Then what if infinitely many buses, each containing infinitely many people, show up? And so on...
posted by number9dream at 9:13 AM on February 7, 2015 [1 favorite]
Let n=2^57,885,161 − 1 and systematically test whether each prime number less than n goes into n without a remainder. Count the number of prime numbers you have tested.
From the way your question is written, it sounds like you already know that this is a bad idea, but, since mathematicians are never afraid to state the obvious: this is a bad idea. I mean, it might be a good idea for a smaller n, but not for this one. There's no way for your students to ever, in the amount of time remaining until the heat death of the universe, do enough trial divisions to count the number of primes smaller than this number.
For this value of n, the prime number theorem is indeed the way to go, as people have mentioned upthread.
Cantor's diagonal argument is a very interesting example of how mathematicians deal with infinite quantities/sets. It proves that there are different sizes of infinities: in particular, it shows that the infinite set of real numbers is strictly larger than the infinite set of natural numbers.
It's somewhat of an advanced concept, but my high school math teacher taught us about this (also in an after-school advanced math program), and if you explain it well, it's totally understandable to students at that level.
Another way to illustrate infinity and how arithmetic with infinite quantities differs from ordinary arithmetic is Hilbert's Hotel. The idea there is that you have a hotel with (countably) infinitely many rooms, all of which are occupied, and you ask questions like: what do you do if another guest shows up? Well, just get the person in room 1 to move to room 2, the person in room 2 to move to room 3, and so on. So room 1 is empty, and the new guest can go to room 1. This shows that ∞+1=∞.
Then what if (countably) infinitely many people show up? Well, ask the person in room 1 to move to room 2, the person in room 2 to move to room 4, ... , ask the person in room n to move to room 2n, etc. Then all of the odd-numbered rooms are free, so each of the new guests can be accommodated. This shows that ∞×2=∞.
Then what if infinitely many buses, each containing infinitely many people, show up? And so on...
posted by number9dream at 9:13 AM on February 7, 2015 [1 favorite]
2^57,885,161 − 1 / ln (2^57,885,161 − 1)
A great example of the type of question you are looking for, is exactly: How would you evaluate a formula like this, involving very large numbers?
It ain't easy!
Other equations evaluated at very large numbers could be quite a lot easier, say x^3 -x^2 + 10x - 1000 evaluated at x=10^100. (At large numbers the x^3 dominates so you can just ignore the other terms for practical purposes.)
Others can be fiendishly difficult: What is tan(x) for x=10^100? That might be very difficult to calculate to even the slightest degree of precision. And that was the easy one--now how are you going to calculate tan(2^57,885,161) or (even better) tan(2^57,885,161^57,885,161).
BTW at least some of the solutions to the problems outlined above are in the reach of students at this level, at least conceptually. All you need to figure tan(x) is to know the value of x mod pi.
So to figure out 10^100 mod pi, you need to know the value of pi to some hundred-odd digits, then be able to do arithmetic operations on numbers with that many digits.
So, doable.
2^57,885,161 mod pi is a lot harder because you're going to need to know pi to some 10s of millions of digits and be able to do arithmetic on numbers with that many digits.
2^57,885,161^57,885,161 mod pi is perhaps not something that is knowable, given the age of the universe, fundamental limitations imposed by entropy, etc. Unless someone comes up with a clever solution that bypasses all that, of course!
This little exercise is nice because it ties in to the question of in what possible way calculating pi to a million or hundred million digits could be useful.
One simple answer is, you can't figure out a simple question like what is tan(x) unless you know pi to the same number of digits x has, plus some.
posted by flug at 12:07 PM on February 7, 2015 [1 favorite]
A great example of the type of question you are looking for, is exactly: How would you evaluate a formula like this, involving very large numbers?
It ain't easy!
Other equations evaluated at very large numbers could be quite a lot easier, say x^3 -x^2 + 10x - 1000 evaluated at x=10^100. (At large numbers the x^3 dominates so you can just ignore the other terms for practical purposes.)
Others can be fiendishly difficult: What is tan(x) for x=10^100? That might be very difficult to calculate to even the slightest degree of precision. And that was the easy one--now how are you going to calculate tan(2^57,885,161) or (even better) tan(2^57,885,161^57,885,161).
BTW at least some of the solutions to the problems outlined above are in the reach of students at this level, at least conceptually. All you need to figure tan(x) is to know the value of x mod pi.
So to figure out 10^100 mod pi, you need to know the value of pi to some hundred-odd digits, then be able to do arithmetic operations on numbers with that many digits.
So, doable.
2^57,885,161 mod pi is a lot harder because you're going to need to know pi to some 10s of millions of digits and be able to do arithmetic on numbers with that many digits.
2^57,885,161^57,885,161 mod pi is perhaps not something that is knowable, given the age of the universe, fundamental limitations imposed by entropy, etc. Unless someone comes up with a clever solution that bypasses all that, of course!
This little exercise is nice because it ties in to the question of in what possible way calculating pi to a million or hundred million digits could be useful.
One simple answer is, you can't figure out a simple question like what is tan(x) unless you know pi to the same number of digits x has, plus some.
posted by flug at 12:07 PM on February 7, 2015 [1 favorite]
BTW what made me think of tan(10^100) is that it is the punchline of a famous story told by Richard Feynman about his prowess at solving Fermi-type problems. It's a pretty good story and might give you some ideas to think about.
posted by flug at 12:16 PM on February 7, 2015
posted by flug at 12:16 PM on February 7, 2015
the number of different chess games for which the board never returns to a previously experienced state. (???)
This is pretty easy to get an upper bound on, but reducing that upper bound to eliminate all duplicates or impossibilities would be super-hard.
But:
64 spaces and 96 possible things that can go in each space (32 pieces plus each of the 64 spaces can be blank, 32+64=96).
The formula is 96!/(96-64)! = 96!/32! = 3.768764e+114
That gives us the number of positions of pieces on the board. (Some slight simplifications there, see explanations here under pvmike's comments.)
Now, we are going to define a 'move' as moving from any one of the 3.8e144 positions to any another and a 'game' as continuing this until we repeat a position.
In that case, we get 3.8e144! games. (That's an easy upper bound, actual number somewhat lower.)
Easy!
Of course that is massively high upper bound; you could reduce it a ton by eliminating impossible positions, impossible moves, etc. Of which there will be many; the vast majority, probably. But, that is a *lot* of work--we're just doing the easy part . . .
Regardless of all that, 3.8e144! is a nice and fairly safe upper bound.
A fun exercise would be figuring out how digits 3.8e144! has. I think there is some kind of a way to approximate how many digits x! will have if x has a certain number of digits, but I'm not sure.
posted by flug at 12:39 PM on February 7, 2015
This is pretty easy to get an upper bound on, but reducing that upper bound to eliminate all duplicates or impossibilities would be super-hard.
But:
64 spaces and 96 possible things that can go in each space (32 pieces plus each of the 64 spaces can be blank, 32+64=96).
The formula is 96!/(96-64)! = 96!/32! = 3.768764e+114
That gives us the number of positions of pieces on the board. (Some slight simplifications there, see explanations here under pvmike's comments.)
Now, we are going to define a 'move' as moving from any one of the 3.8e144 positions to any another and a 'game' as continuing this until we repeat a position.
In that case, we get 3.8e144! games. (That's an easy upper bound, actual number somewhat lower.)
Easy!
Of course that is massively high upper bound; you could reduce it a ton by eliminating impossible positions, impossible moves, etc. Of which there will be many; the vast majority, probably. But, that is a *lot* of work--we're just doing the easy part . . .
Regardless of all that, 3.8e144! is a nice and fairly safe upper bound.
A fun exercise would be figuring out how digits 3.8e144! has. I think there is some kind of a way to approximate how many digits x! will have if x has a certain number of digits, but I'm not sure.
posted by flug at 12:39 PM on February 7, 2015
I don't think Flug's counting is right-- each space can have only 33 things in it (one of the pieces, or it can be blank). It's less, even; each space can have only 13 things on it (rook, bishop, knight, king, queen, pawn; both in black and white. or it can be blank). This is still a huge overcounting, because of course I can't have two spaces with a black queen, but all valid states are included. But 13^64 is only 1.96 x 10^71.
(For what it's worth this same counting in the Go case is much easier; for an NxN Go board, if you're never allowed to repeat a board position, then each space can be either black, white, or empty; so 3^(NxN) is an upper bound on the number of possible turns (again, some board arrangements may not be reachable from the start state; at the least all those which have captured stones on them).
posted by nat at 8:26 PM on February 7, 2015
(For what it's worth this same counting in the Go case is much easier; for an NxN Go board, if you're never allowed to repeat a board position, then each space can be either black, white, or empty; so 3^(NxN) is an upper bound on the number of possible turns (again, some board arrangements may not be reachable from the start state; at the least all those which have captured stones on them).
posted by nat at 8:26 PM on February 7, 2015
Of course my example was dumb because you *can* have two spaces with a black queen, if you get a pawn across. You can't however have 10 spaces with a black queen, which my counting allows for.
posted by nat at 8:28 PM on February 7, 2015
posted by nat at 8:28 PM on February 7, 2015
And It should be 3^(NxN)! is a bound on the number of possible turns. That ! matters :-)
posted by nat at 8:30 PM on February 7, 2015
posted by nat at 8:30 PM on February 7, 2015
I don't think Flug's counting is right-- each space can have only 33 things in it (one of the pieces, or it can be blank).
Well, that's why this is advertised as an 'upper bound', not the lowest possible upper bound.
You're right, that you could make the calculation quite a bit tighter by considering that all the blank spaces are equivalent (the calculation I gave above above assumes each blank space is unique and counts each of these different configurations of 'unique' blank spaces as a different board configuration).
Similarly, you could reduce it further by counting pawns as non-distinct (as long as they are the same color), and rooks, bishops, and knights, too.
Then going even further we can eliminate positions impossible according to various rules of chess, etc.
But all that gets pretty complicated; the idea was a provide an easy upper bound.
And FYI you're right that to get every single possibility you'd have to include every possible outcome of pawn promotion, so each side would need ten knights, ten bishops, ten rooks or nine queens, plus king, and eight pawns--giving a total of 140 pieces (48 white, 48 black, 64 'blank space' pieces).
Using the same type of calculation, the number of possible chess board positions including all of those pieces is 160!/(160-96)! = 3.715689e+195. Again, this number considers each piece to be 'distinct' even when it isn't really. So it's an upper bound, but not really a tight upper bound.
Trying to bring this back to the topic at hand: This is a somewhat nice demonstration of large numbers that are easy to calculate vs those that are well nigh-impossible:
posted by flug at 2:29 PM on February 8, 2015
Well, that's why this is advertised as an 'upper bound', not the lowest possible upper bound.
You're right, that you could make the calculation quite a bit tighter by considering that all the blank spaces are equivalent (the calculation I gave above above assumes each blank space is unique and counts each of these different configurations of 'unique' blank spaces as a different board configuration).
Similarly, you could reduce it further by counting pawns as non-distinct (as long as they are the same color), and rooks, bishops, and knights, too.
Then going even further we can eliminate positions impossible according to various rules of chess, etc.
But all that gets pretty complicated; the idea was a provide an easy upper bound.
And FYI you're right that to get every single possibility you'd have to include every possible outcome of pawn promotion, so each side would need ten knights, ten bishops, ten rooks or nine queens, plus king, and eight pawns--giving a total of 140 pieces (48 white, 48 black, 64 'blank space' pieces).
Using the same type of calculation, the number of possible chess board positions including all of those pieces is 160!/(160-96)! = 3.715689e+195. Again, this number considers each piece to be 'distinct' even when it isn't really. So it's an upper bound, but not really a tight upper bound.
Trying to bring this back to the topic at hand: This is a somewhat nice demonstration of large numbers that are easy to calculate vs those that are well nigh-impossible:
- A loose upper bound on the different possible position of chess pieces & blank spaces on the board is pretty easy to calculate using pretty simple methods, though very large. Including pawn promotion, it's 3.715689e+195.
- With a bit more thinking, you could cut that upper bound down some. Now we're into 10^71 territory.
- We could probably make some more progress along these lines pretty easily, looking at various symmetries, etc
- But pretty soon you are into really difficult territory. The number of positions on the board that could be achieved through legal play or the number of different games that could be played using legal moves, are a lot, lot harder to put your finger on than these simplifications, which get pretty quick/easy answers using bits of relatively easy combinatorics. In short, the real number is probably quite a lot less than 10^71, but it's also a lot harder to figure out.
posted by flug at 2:29 PM on February 8, 2015
« Older Help me find an android notification manager? | Near-sighted or bifocaled? How do I do shower... Newer »
This thread is closed to new comments.
posted by vacapinta at 6:15 AM on February 7, 2015 [4 favorites]