|
|
||
| GBB Services | ||
| GBB Services : Mathematics : 1010 |
10, 1010, 101010… Infinityby Walter VanniniSome Questions Mathematical Preliminaries An Aside An Observation Some Examples Cells in a Human 10101.1 Largest 64 bit Signed Integer 10101.278 Atoms in a Human 10101.44 Largest Single Precision Float 10101.586 Elementary Particles in the Known Universe 10101.9 Googol 10102 Hubble Volume 10102.079 Number of Chess Games Under 50 Moves 10102.399 Largest Double Precision Float 10102.489 Number of Photos 10106.86 Largest Known Prime 10106.99 Typing Monkeys 10107.3 DNA 10109.4 Number of Movies 1010101.086 Gases and Statistical Mechanics 1010101.4 Tegmark's Number 1010101.46 Number of Chess Games 1010101.7 Googolplex 1010102 Number of High Definition Movies 1010102.21 Even bigger numbers 1010103 Skewes' Number 101010101.53 Graham's Number Multiplication Table Exponentiation Table Miscellaneous Arithmetic Results n^n^n^n Repackaging the lump of dirt under the carpet Calculus The Answers The Next Step Feedback IntroductionThe title of this essay is inspired by the title of George Gamow's classic book "One, Two, Three … Infinity". The title refers to the counting practices of a mathematically unsophisticated human. Once this hypothetical human has reached three, his ability to make meaningful distinctions has been pushed to the limit, and all numbers beyond that are just classified as "big" (or "infinite"). It's not that larger numbers like 20 or 10,000 or 1,000,000 can't be understood. It's just that there's no "feel" for the relative sizes of 20 or 10,000 or 1,000,000. They're all equally enormously "big". I personally don't remember transitioning from the "One, Two, Three … Infinity" stage to being able to handle the relative sizes of larger numbers. I do remember that at about age six I was limited to "One, Ten, One Hundred … Infinity". My father explained how to systematically count beyond a hundred to me, and infinity receded a little further out. By the time I was in college, my number boundaries could be described as "10, 1010, 10100… Infinity". This was not due to my study of mathematics, but more due to my study of astronomy, physics and chemistry. Numbers on the order of 1020 are extremely common in chemistry and physics, and numbers all the way up to 1080 come up in astronomy and physics. For example, the number of elementary particles in the known universe is about 1080. This makes it possible to have some kind of feel for numbers just shy of a googol (10100 = 10102). But, numbers like a googolplex (10googol = 1010100 = 1010102) were, and still are to some extent, effectively infinite. It's not immediately clear to me which of 9999 and 1010102 and (1010)! is bigger, and by how much. Recently I've been attempting to push my boundaries, and get a feel for the next level out. By that I mean trying to appreciate numbers beyond a googol, and even beyond a googolplex. That means numbers of the form 1010n, where n is in the range from 1 to 10, and 101010n , where n is again in the range from 1 to 10. Here's a little of what I've found, and how I found it. Some QuestionsTo get started here are three questions to think about. The answers are at the end of this essay. You might want to record your initial guesses before doing any quantitative analysis or reading further. 1. Writing 11101010 as 101010w, which inequality is true? (a) w < 10 (b) w > 11 (c) 10.1 < w < 11 (d) 10.0001 < w < 10.1 (e) 10.00000001 < w < 10.0001 (f) 10 < w < 10.00000001 Posing and answering the following question has really gotten me to appreciate the enormity of the numbers we're considering. The answer might surprise you. It surprised me! 2. Writing 10101011 as x101010, which inequality is true? (a) x < 10 (b) 10 < x < 100 (c) 100 < x < 1000 (d) 1000 < x < 1010 (e) 1010 < x < 101010 (e) 101010 < x < 10101010 (f) x > 10101010 3. Write the following three numbers in ascending order (ie smallest to largest): 9999, 1010102, and (1010)! (ie factorial) Mathematical PreliminariesIf you don't already know that aman = am+n and that (am)n = amn, you're going to have a tough time reading this essay. I'm just going to take that kind of knowledge as a given. Another thing you should be aware of is that the expression abc is ambiguous, unlike the expression a*b*c. Its value depends on how the terms are grouped: (ab)c is very different from a(bc). The universal convention in the mathematical literature is that abc always means a(bc). A possible justification for this is that if you want (ab)c, you can always write it as abc anyway. If the previous paragraph was news to you, you might want to contemplate the fact that (1010)10 is "just" 1010*10=10100, which is a lot smaller than 10(1010)=1010000000000. An AsideThe emphasis of this essay is on being able to distinguish between large numbers. I should mention that it's just as important to realize when you shouldn't distinguish between large numbers. There's an old joke which I can't resist mentioning at this point: An astrophysicist is giving a lecture on stellar evolution, and mentions that the interior temperature of a star of some given mass is 107 degrees. One of the students gets very excited, puts up his hand and asks "Is that Celsius or Kelvin?" An ObservationHere's a way to get a feel for the size difference between 101010n and 101010n+1: Firstly, note that 1010n+1 is 1010n10, which is (1010n)10, so that 1010n+1 = 1010n 1010n 1010n 1010n 1010n 1010n 1010n 1010n 1010n 1010n This means that 101010n+1 is the same as ((((((((( (101010n) 1010n) 1010n) 1010n) 1010n) 1010n) 1010n) 1010n) 1010n) 1010n) This would mean that confusing 1010104 with 1010105 is analogous to confusing 102 with ((((((((( (102) 2) 2) 2) 2) 2) 2) 2) 2) 2) ie 100 with 101024, which are numbers that are even more different that 100 and a googol! Some ExamplesTo begin getting a feel for these numbers, some examples that aren't too contrived are good to know. Here's a few: Cells in a Human: 10101.1From the world of biology: the number of cells in a human body is estimated as being somewhere between 1013 and 1014. Largest 64 bit Signed Integer: 10101.278From the world of programming: 263-1 = 9,223,372,036,854,775,807. This is 1018.965. Writing this number in the form 1010n, it's 10101.278. Atoms in a Human: 10101.44We'll make use of the fact that the human body is mostly water. From the world of chemistry: Avogadro's number, roughly 6 * 1023, is the number of carbon-12 atoms in 12 grams. A typical water molecule consists of two hydrogen-1 atoms and one oxygen-16 atom, so that Avogadro's number must be (almost equal to) the number of water molecules in 18 grams of water. Since there are three atoms per water molecule, Avogadro's number is (almost equal to) the number of atoms in 6 grams of water. Since the body is mostly water, that means that the number of atoms in a 60 kilogram human must be very close to 104 * Avogadro's number = 6 * 1027 = 1027.8 = 10101.44. Largest Single Precision Float: 10101.586From the world of programming: 2128 (1-2-24). This is 1038.532. Writing this number in the form 1010n, it's 10101.586. Elementary Particles in the Known Universe: 10101.9From the world of physics: the number of elementary particles is about 1080 = 10101.9. As a consistency check, I'll do a back of the envelope calculation of the number of atoms in the known universe. That should be the number of elementary particles, to within a few orders of magnitude. There's roughly 1011 galaxies in the known universe, with roughly 1011 stars per galaxy. The sun is a typical star, and its volume is about 106 times the volume of the earth. The earth's diameter is about 104 kilometers, giving it a volume of roughly 1012 cubic kilometers. An atom has a diameter of roughly an Angstrom, which is a tenth of a nanometer. So there should be about 1039 atoms in a cubic kilometer. Putting it all together, there should be about 1011+11+6+12+39 = 1079 atoms in the known universe. Googol: 10102From the world of mathematics: one followed by a hundred zeros. This is 10100. Writing this number in the form 1010n, it's 10102. Hubble Volume: 10102.079From the world of physics: the size of the known universe is about 13 billion light years. This is about 1040 proton diameters. This means that the volume of the known universe is about (1040)3 = 10120 proton volumes. Writing this number in the form 1010n, it's 10102.079. Number of Chess Games Under 50 Moves: 10102.399From the world of games: the number of possible chess games of 50 moves or less is bounded above by 321100 = 10250.65. I give the reasoning behind this in the chess section below. Writing this number in the form 1010n, it's 10102.399. Largest Double Precision Float: 10102.489From the world of programming: 21024 (1-2-53). This is 10308.2547. Writing this number in the form 1010n, it's 10102.489. Number of Photos: 10106.86From the world of computer science: the number of megapixel images (1000 pixel rows and 1000 pixel columns giving a total of 1000*1000 pixels) that have 24 bit color is: (224)1000*1000 = 224,000,000. Writing this in the form 1010n, it's 10106.86 Largest Known Prime: 10106.99From the world of mathematics: the largest known prime (as of August 2007) is the Mersenne prime 232,582,657-1. Writing this in the form 1010n, it's 10106.99. Typing Monkeys: 10107.3From the world of probability: the number of letters (including spaces and returns) in Shakespeare's collected works is about 107. The number of typeable characters with a typewriter keyboard (including use of the shift key) is about 100. Given a monkey sitting at a keyboard, what are the odds that he'll type the works of Shakespeare? Well it's 1 in 100107, which is 1 in 10107.3 DNA: 10109.4From the world of biology: the number of base pairs in the human genome is about 3*109. There are 4 kinds of base pairs (they're often referred to by the letters G,C,A,T). This means that the number of possible DNA molecules must be bounded above by 43*109. Writing this in the form 1010n, it's 10109.4. Number of Movies: 1010101.086Continuing with the photos example: the number of 24 bit color, 2 hour silent movies running at 30 frames a second is (224)1000*1000*30*3600*2. This is 101012.1932, which is 1010101.086 Great, we finally broke through to numbers of the form 101010n Gases and Statistical Mechanics: 1010101.4Suppose one starts with a room sized box that is partitioned into two equal volumes, and we start with all the air in one volume. Removing the partition will result in the air being equally distributed. What is the probability that the air will regroup in the original volume? The probability that a single molecule will be in the desired volume is 1 in 2. A good estimate of the number of molecules is Avogadro's number, which is 6.022*1023. Let's work with 1024. The probability is then 1 in 21024. Writing this in our standard form, the odds are one in 1010101.4 Tegmark's Number: 1010101.46Lee Corbin, a fellow programmer and mathematics enthusiast, has been thinking about large numbers for many years (at least since 1976). He has even coined a name for the kind of mathematics I'm writing about here: "megamathematics". In May he turned me onto a paper by Max Tegmark. In it the number 101029 comes up as the number of meters you must travel to find an exact copy of yourself, assuming that the universe is homogeneous and infinite. This number is 1010101.46. Number of Chess Games: 1010101.7From the world of games: the number of possible chess games has been estimated by G.H. Hardy as about 101050, which can be rewritten as 1010101.7 It's unclear to me how G.H. Hardy, a world class mathematician, came up with this estimate. My own analysis gives the number as not even 10105. It's big, but nowhere near as big as Hardy is claiming. Here's my reasoning: There are at least three interesting upper bounds associated with counting chess games. I've labelled them P, M, and S, and they're defined below. P is an upper bound on the number of plies. Each "move" consists of two plies, one involving action by white, the other involving action by black. S is an upper bound on the number of static positions. The number of static positions is less than 1364. That's because each of the 64 squares can only have 13 states (6 for each kind of white chess piece, 6 for each kind of black chess piece, and empty). So S ≤ 1364 ( ≈ 1071.3 ). M is an upper bound on the maximum number of legal moves from a given position to another position via one ply. It's bounded above by 321 = 8 + 27 + 2*14 + 2*13 + 2*8 + 8*27 (corresponding to the moves available to a king, a queen, two rooks, two bishops, two knights, and eight pawns (which might have turned into queens)). So M ≤ 321. Given the above quantities, an upper bound on the number of games can be given by MP or SP. Since M is much smaller than S (321 < 1364) we'll go with MP = 321P. The maximum possible number of plies in a game is bounded by 100*(6*16 + 30 + 1) = 12700. This is because of the rule that says that if there is no pawn movement or piece capture in fifty moves (ie one hundred plies) then the game is a draw. There are only 16 pawns, and they can only move 6 times each. There are only 30 pieces that can be captured (there are 32 pieces, but the 2 kings don't count). So, P ≤ 12700. The actual rule is that a player has to claim the draw. I'm assuming that he does that, otherwise there is no upper bound to the number of games, since the players can just agree to move around the pieces forever. The values of M and P give an upper bound of MP = 32112700 to the number of possible chess games. That's 10104.503, which is way below Hardy's 101050. It could be that Hardy wasn't thinking of the fifty move rule at all, but was considering the number of games that don't repeat a static position. That's bounded by S! ≤ 1364!, which by Stirling's approximation is roughly 101073.14. It's also bounded by MS = 3211364 ≈ 101071.7. Maybe Hardy used a tighter upper bound on S to get down to 101050. Hardy's long time collaborator J.E. Littlewood wrote an essay on large numbers in his book Littlewood's Miscellany, in which he gives a detailed analysis of the maximum number of chess games. He derives the bound 101070.5. I've written more about it in the Feedback section. Googolplex: 1010102From the world of mathematics: one followed by googol zeros. This is 1010100. Writing this number in the form 101010n, it's 1010102. Number of High Definition Movies: 1010102.21Instead of a 2 hour megapixel movie, we can consider a voxel (ie 3d volumetric) movie. Let's go crazy! Imagine that the voxels are the size of a proton. Take the volume the movie plays in to be the size of the known universe. Assume a trillion (ie 1012) frames a second. Assume the movie plays for the age of the universe (ie 1018 seconds). Assume that instead of 24 bit color, we have trillion bit color. How many of these movies are there? Well, the number of voxels is 10120. The number of frames is 1030 ( = 1018 * 1012). Trillion bit color means 21012 kinds of voxels. That means that the number of movies is about (21012)101201030. This is 210162, which simplifies to 1010102.21 Even bigger numbers: 1010103I'm finding it really hard to find or create any kind of examples where numbers like 101010n show up, for values of n from 3 to 10. If you know of any, please let me know. I wrote the above in December of 2003. It's now August of 2007, and I still don't have a good example for numbers in this range. Skewes' Number: 101010101.53This number is named after the mathematician Stanley Skewes. This number is usually expressed as 10101034 ( = 101010101.53), which puts it in the camp of numbers of the form 10101010n, which is beyond the class of numbers I'm considering here. It comes up as the upper bound eeee79 in number theory. There's an analytical approximation to π(n) (the number of primes less than n) that is even better that n/log(n). It's Li(n), and is defined as Li(x) = ∫2x dt/log(t) The error term of this better approximation is known to alternate its sign infinitely often as n increases. Skewes' number is an upper bound on when the first change of sign must occur by, given the truth of the Riemann hypothesis. Graham's NumberThis number is named after the mathematician Ron Graham. I won't say much about it, since it would take us too far afield. It's a number that comes up in Ramsey theory (which is named after the mathematician Frank Ramsey). It's way bigger than any of the other numbers discussed here. For those who are curious, consider the super-exponentiation operation a↑↑b defined inductively by a↑↑b = a↑(a↑↑(b-1)) and a↑↑1 = a (where a↑b = ab). Using this notation, the numbers we're discussing in this essay are in the ranges from 10↑↑2 to 10↑↑3 and from 10↑↑3 to 10↑↑4 (and this essay can be retitled "10↑↑1, 10↑↑2, 10↑↑3, … ∞"). Skewes' number is in the range 10↑↑4 to 10↑↑5. Well, you can now use the same kind of generalization to consider a↑↑↑b defined inductively by a↑↑↑b = a↑↑(a↑↑↑(b-1)) and a↑↑↑1 = a. To even talk about Graham's number involves continuing with generalized arithmetic operations of this kind. Maybe I'll take it up in another essay. For now, just dealing with the range from 10↑↑3 to 10↑↑4 is enough for me. Incidentally, the above notation is known as Knuth's up arrow notation, and you can read more about it in the wikipedia article on the topic. It's named after the computer scientist Donald Knuth. Multiplication Table"All I really need to know about mathematics I learned from the multiplication table". Well, maybe not! But you can learn a lot from contemplating the standard 10 by 10 multiplication table. Maybe the following table might be useful too.
For the morbidly curious, "13" comes from log10(2)/log(10) ≈ 0.3010/2.302585 ≈ 0.1307 101010n 101010n = 101010x where x = n + log10(1+log10(2)10-n) ≈ n + log10(2)10-n/log(10) Similarly 101010n 101010m = 101010x where x = n + log10(1+log10( 1+1010m-10n-n )10-n) ≈ n + 1010m-10n-nlog(10)-2 (for m < n). Exponentiation Table
Miscellaneous Arithmetic Resultsaddition103 + 103 ≈ 103.3010 10103 + 10103 ≈ 10103.00013 multiplication103 * 103 = 106 10103 * 10103 ≈ 10103.3010 1010103 * 1010103 ≈ 1010103.00013 exponentiation(103)3 = 109 (10103) 103 = 10106 (1010103) 10103 ≈ 1010103.301 factorials103! ≈ 10103.40 10103! ≈ 1010103.0013 n^n^n^nWe really should evaluate nnnn as a number of the form 101010m for various values of n, if we're serious about getting a feel for large numbers. Here are the results:
I usually find that a little context helps. Here are the corresponding results for nnn:
Finally, here are the corresponding results for nn:
Incidentally, if nnnn = 101010x, then the following relationships exist between x and n: 1010x = log10(n) * nnn 10x = log10(n) * nn + log10(log10(n))
10x = nn * ( log10(n) + (log10(log10(n))/(nn)) ) x = n log10(n) + log10( log10(n) + (log10(log10(n))/(nn)) ) Repackaging the lump of dirt under the carpetSuppose that x,y,z,w satisfy I've found it useful to consider what happens to the other three variables when one of the variables is equal to 11. Here are the results:
Here are the corresponding results for x1010 = 10y10 = 1010z:
Finally, here are the corresponding results for x10 = 10y:
CalculusSince I was a teenager, I've always liked to see what light calculus can shed on a topic. This is probably one of the reasons why I specialized in differential geometry as a graduate student and as a professional mathematician. Turning the spotlight on numbers of the form 101010n, it seems to me that the we might want to look at the derivative with respect to n. More generally, we might want to look at the four partial derivatives of the four variable function xyzw. This should give a feel for what effect varying the various numbers will have on the final result. Well, before doing that, we should look at the simplest case 10n and xy, and then the intermediate case 1010n and xyz. Here we go: From elementary calculus, we have d/dx(xn) = n xn-1 and d/dx(ex) = ex. Since ax = (elog(a))x, we also have d/dx(ax) = log(a) ax. Using the above notation:
This tells us that Using the chain rule and the above identities, we have:
This tells us that Finally, the case we're really interested in:
This tells us that These results have many interesting implications. Among them, for small values of delta, δ, we have (10+δ)1010n ≈ 101010n + (1/10) 1010n 101010n δ 101010n+δ ≈ 101010n + (log(10))3 10n 1010n 101010n δ which immediately tells us that (10+δ)1010n ≈ 101010n+10-(n+1) log(10)-3δ Since log(10)3 is roughly 10, this gives us (10+δ)1010n ≈ 101010n+(10-(n+2) δ) The Answers1. (f) 2. (f) 3. (1010)! < 1010102 < 9999. Here are more details: 1. 11101010 = 101010w implies 1010 + log10(log10(11)) = 10w. This immediately implies w = 10 + log10( 1+ 10-10log10(log10(11)) ) The well known approximation log10(1+x) ≈ x/log(10) (where log10 is log base 10 and log is the natural logarithm, of course) then gives us w ≈ 10 + 10-10log10(log10(11))/log10 ie w ≈ 10.000000000000766 which puts it in the range (f) 10 < w < 10.00000001 2. 10101011 = x101010 implies x = 10109 * 1010 which is much bigger than x = 10101 * 1010 which puts it in the range x > 10101010 Note that since log10(9)≈ 0.9542, we have x = 10101010.9542 3. (1010)! < (1010)1010 = 101011 < 1010100 = 1010102 log10(9) ≈ 0.9542 immediately tells us that 99 > 108, and so 9999 > 99108 > 910107 > 1010106 which is of course greater that 1010102 Note that more careful analysis gives us: (1010)! ≈ 1010101.0406 (9999) ≈ 1010108.568 The Next StepAs I mentioned before, Lee Corbin has been thinking about these kinds of issues ( "megamathematics" ) since the mid 1970's. He was kind enough to look over this essay in draft form, and to remind me of Skewes' number and Graham's number, which led me to add the sections dealing with them. He also mentioned a great question for getting to grips with the next level up, ie numbers of the form 10101010n. Here it is: Write the following four numbers in ascending order: 9999!, 99(99)!, 9(999)!, (9999)!. Have fun! Feedback[ 1 ] Ray Johnston wrote to me and mentioned that it seems that Hardy never gave an explicit justification for his estimate of 101050. But, Hardy's long time collaborator (and Skewes' PhD advisor) J.E. Littlewood wrote an essay on large numbers in his book Littlewood's Miscellany, in which he gives a detailed analysis of the maximum number of chess games. Using Littlewood's reasoning, I get the number 101070.71. Littlewood's approach was to use MP to find an upper bound, but his approach to bounding P was to use the "three position rule", rather than the "fifty move rule" I used above. Using that rule, we can conclude that P ≤ 4S+1, via the pigeonhole principle. Littlewood gives a better bound on S than 1364=1071.3: namely 1016Σ{1 ≤ N ≤ 32}64!/(64-N)!, which is 1069.7. In his essay he uses the symbol "a" for what I'm writing as "S". Putting it all together, we get the upper bound MP = 3214*1069.7, which is 101070.71. Incidentally, it turns out that Littlewood's detailed analysis was slightly off: he overestimated M as 332 (he used an upper bound of 14 diagonal moves for a bishop or queen, instead of 13), which is no problem when computing an upper bound, and he underestimated P as 2S+1 instead of 4S+1, which is a problem. He ended up underestimating the upper bound as 101070.5. Here's what I wrote to Ray: Incidentally, Littlewood's upper bound is not quite right. For one thing, it is based on assuming the rule that a chess game is a draw when the same position is repeated 3 times. The actual rule is a little different. For one thing, the same position has to be repeated 3 times, with the SAME player to move each time (in Littlewood's essay, this means that he should have used "4a+1" instead of "2a+1", to give a slightly larger upper bound). If he had used the correct rule, his reasoning gives an upper bound of 10^(10^70.8), according to my calculations. Secondly, the rule does not state that the game is a draw. It only states that the a draw can be claimed by the player to move. If he doesn't, then the game can continue forever, and there is no upper bound. Finally, I should mention that Ray was a member of the Monash University Chess Club, as I was (an amazing coincidence). We didn't overlap: Ray got his PhD at Monash just as I graduated from elementary school. His homepage is at http://members.iinet.com.au/~ray/. I enjoyed reading the letter that Richard Feynman wrote to Ray. [ 2 ] Clifford Pickover wrote to correct the physical units I was using for Tegmark's number. I've modified this essay accordingly. If you have corrections, additions, modifications, etc please let me know mailto:walterv@gbbservices.com
|