Cube Numbers To the main page "Mathematische Basteleien" What is a cube number? A cube number (or a cube) is a number you can write as a product of three equal factors of natural numbers. Formula: k=a*a*a=a³ (k and a stand for integers.) On the other hand a cube number results by multiplying an integer by itself three times. Formula: a*a*a=a³=k (a and k stand for integers.) The same factor is called the base. After this a negative number like (-2)³= -8 or a fraction number like (2/3)³=8/27 are suspended. If it is appropriate, the number 0 is also a cubic number. These are the first 100 cube numbers. You can illustrate the name cube number by the following drawings. If a is the side of a cube, the volume is a³. ...1... 1 Computation with the calculator In former times you found cube numbers by ready-reckoners, today there are calculators. You act with the TI30 like this: After entering the number you press the keys yx , (1/3) and finally = .

Example: [2299968] -- [yx] -- [(1/3)] -- [=] . You get 22999681/3 =132. It is even simpler to give in 2299968^(1/3) into the searching field of Google or Bing. The cube root appears after pressing the enter key. 2 Determination by nested intervals 22999681/3 The number must be between 100 and 200 (100³=1000000 and 200³=4000000). It must be between 130 and 140 (130³=2197000 and 140³=2744000). It must be near 130 and 8 is on the ones place. Then 132 comes into consideration. Result: 22999681/3=132 22999681/3 You write the number in factors and develop the cube number this way.

2299968 = 8*287496 = 8*27*10648 = 8*27*8*1331=8*27*8*11*121=8*8*27*11³=(2*2*3*11)³=132. Result: 22999681/3 = 132. Cube Roots of Negative Numbers? top There is (-2)³=-8. You could think that then (-8)1/3=-2 is. In former times this notation was common in schools, too. Today you demand that a1/3 is only defined for a>0 or a=0. The term (-8)1/3 ist not allowed. Thus you avoid conflicts as the following calculations show. There is (-8)1/3=(-8)2/6=[(-8)2]1/6=(64)1/6=(26 )1/6=2. That means that (-8)1/3 would be ambiguous. You would get two results depending on the way of calculation. This is possible.

The equation (-2)³=-8 is changed to -(81/3)=-2. Generally x³=a leads to x=-(-a)1/3 for a<0. Sequences and Series top Series of the cube numbers There is a series to each sequence and this is the sequence of the partial sums. For cube numbers this is the sequence sn= 1³+2³+3³+...+n³. 1³+2³+3³+...+n³=[n(n+1)/2]² is given. Proof by mathematical induction >The statement holds for n=1: s1=[1*(1+1)/2]²=1. >Assume that the formula holds for all natural numbers n: sn=[n(n+1)/2]². >You must show that then the formula also holds for n+1: sn+1 = [(n+1)(n+2)/2]². Calculation: Convert the product [(n+1)(n+2)]² into a sum at first.

[(n+1)(n+2)]²=(n²+3n+2)²=n4+(3n+2)²+2n²(3n+2)=n4+(9n²+12n+4)+(6n³+4n²)=n4+6n³+12n²+12n+4 There is sn+1 = sn+(n+1)³ = [n(n+1)/2]²+(n+1)³ = [n²(n+1)²+4(n+1)³]/4 = [n²(n²+2n+1)+(4n³+12n²+12n+4)]/4 = (n4+6n³+13n²+12n+4)/4 = [(n+1)(n+2)]²/4 = [(n+1)(n+2)/2]², qed..

The formula 1³+2³+3³+...+n³=[n(n+1)/2]² contains the series of the natural numbers, because the sum can be written as 1+2+3+ ...+n=n(n+1)/2. Thus there is the formula 1³+2³+3³+...+n³ = (1+2+3+...+n)², which is illustrated on the right. Interpretation as an arithmetic series of third order The sequence of the cube numbers is also an arithmetic series of third order. A figure follows to explain this. In every new row you find the difference of two numbers a row higher. The feature is that you reach a constant difference 6 after three steps. There are formulas for these sequences, so that you can prove the formula 1³+2³+3³+...+n³=[n(n+1)/2]² in another way. You can read this on Steffen Weber's (URL below) German web site.

Series of odd numbers There is 1³=1, 2³=3+5, 3³=7+9+11, 4³=13+15+17+19, ... and 1³+2³+3³+4³+... = 1+3+5+7+9+11+13+15+17+19+... Series of the reciprocal cube numbers There is another series of cube numbers, the one of the reciprocal cube numbers: 1/1³+1/2³+1/3³+...+1/n³. It is convergent. You find the limit, the Riemann's zeta-function for 3, on the Wikipedia page 1729 (number). Series of the centered hexagonal numbers The sequence of the centered hexagonal numbers is 1, 7, 19, 37, 61, 91, 127, 169, 217, 271, 331, ... The formula is an=3n²-3n+1.

There is 1, 1+7=8, 1+7+19=27, 1+7+19+37=64, ... The series to the sequence of the centered hexagonal numbers is the sequence of the cube numbers. Calculation for proving: The formulas 1²+2²+3³+...+n²=(1/6)n(n+1)(2n+1) and 1+2+3+...+n=(1/2)n(n+1) are used. Sequence of the centered cube numbers The sequence of the centered cube numbers is 1, 9, 35, 91, 189, 341, 559, 855, 1241,... ...1... The picture pairs make a 3-D view possible. The formula is an=2n³-3n²+3n-1. If you add two consecutive cube numbers, the centered cube numbers develop. This is given by 2n³-3n²+3n-1=n³+(n -1)³. Atomium in Brussels, a centered cube ...

It stands 102 meters (335 ft) tall. There are nine steel spheres connected by tubes. Photos from July 2011. Sequence of the perfect numbers T.L. Heath (1861-1940) proved that every even perfect number - except 6 - is the sum of 2(n-1)/2 cube numbers, for example 28=1³+3³, 496=1³+3³+5³+7³, 8128=1³+3³+5³+7³+9³+11³+13³+15³. Source (3), page 14f. Waring's Problem top The English mathematician Eduard Waring (1734-1798) maintained the following statement among others. "Every natural number is either a cube number or the sum of 2,3,4,5,6,7,8 or 9 cube numbers." (2), page 37ff. That means that 9 is a smallest number.

It can be more than 9 as the following sum of 180³ with 64 (!) cubic numbers shows. 180³ = 6³+7³+8³+...+67³+68³+69³ (1). Already 4 summands will do, 180=1³+3³+3³+5³.

The first numbers 2=1³+1³ 3=1³+1³+1³ 4=1³+1³+1³+1³ 5=1³+1³+1³+1³+1³ 6=1³+1³+1³+1³+1³+1³ 7=1³+1³+1³+1³+1³+1³+1³ 15=2³+1³+1³+1³+1³+1³+1³+1³ 23=2³+2³+1³+1³+1³+1³+1³+1³+1³ Dissection of the numbers <= 100, found by a simple computer program The smallest number of the summands is determined.

>The numbers 2, 9, 16, 28, 35, 54, 65, 72, 91 have sums with 2 cubes at least: 2, 9, 16, 28, 35, 54, 65, 72, 91 >Sums with 3 cubes: 3, 10, 17, 24, 29, 36, 43, 55, 62, 66, 73, 80, 81, 92, 99 >Sums with 4 cubes:4, 11, 18, 25, 30, 32, 37, 44, 51, 56, 63, 67, 70, 74, 82, 88, 89, 93, 100 >Sums with 5 cubes: 5, 12, 19, 26, 31, 33,

 38, 40, 45, 52, 57, 59, 68, 71, 75, 78, 83, 90, 94, 96, 97 >Sums with 6 cubes: 6, 13, 20, 27, 34, 39, 41, 46, 48, 53, 58, 60, 69, 76, 79, 84, 86, 95, 98 >Sums with 7 cubes: 7, 14, 21, 42, 47, 49, 61, 77, 85, 87 >Sums with 8 cubes: 15, 22, 50 (All numbers are 15, 22, 50, 114, 167, 175, 186, 212, 231, 238

, 303, 364, 420, 428, 454.) >Sums with 9 cubes for 23, (and 239 only) >8, 27, 64 are the cube numbers < 100.

There is an anecdote to the sums 1729=1³ + 12³ and 1729= 9³ + 10³, which you can read on the German Wikipedia site Tausendsiebenhundertneunundzwanzig (URL below). Sum of cubes The equation x²+y²=z² leads to the Pythagorean triples (more on my German page 3-4-5-Dreieck ) The more general equation xn+yn=zn has no solution for n>2. This is the famous Fermat's Last Theorem. Andrew Wiles und Richard Taylor proved the theorem not until 1993/95. I recommend the fascinating story in Simon Singh's bestseller Fermat's Last Theorem (5). If you cannot write a cube number as a sum of two cubes, you can look for sums with three or more cubes. A nice example is 3³+4³+5³=6³, particularly, because there are four consecutive numbers. There are more examples in the chapter Playings with Numbers below. Special Cube Numbers top Square numbers among the cubes There are cubes, which also are squares.

You can construct them step by step by squaring cube numbers. 23 leads to 26=64, 33 to 36=729, 4³ to 46=4 096, ... The next cube numbers and at the same time square numbers upto 1 million are 15 625, 46 656, 117 649, 262 144 und 531 441. I must not forget 1. Palindromes among the cube numbers 343=7³ 131=11³, 1030301=101³, 1003003001=1001³, ... 1367631=111³, 1030607060301=10101³, 1003006007006003001=1001001³, ...

1334996994331=11011³, 1331399339931331=110011³, ... 1033394994933301=1011010³, ... It is noticed that all bases are also palindromes. The only palindrome with a non-palindrome base is 10662526601 = 2201³ according to Martin Gardner. Source: Patrick De Geest (World!of numbers) Playing with Numbers top I show results of Lietzmann's book (1) from 1948 among other things in this chapter, extended and controlled by my computer. A cube number is the third power of its digit sum.

512=8³=(5+1+2)³ 4913=17³=(4+9+1+3)³ 5832=18³=(5+8+3+2)³ 17576=26³=(1+7+5+7+6)³ 19683=17³=(1+9+6+8+3)³ A number is the sum of the third power of its digits. 153=1³+5³+3³ 370=3³+7³+0³ 371=3³+7³+1³ 407=4³+0³+7³ The simple program on the right found this.

for x=0 to 9 for y=0 to 9 for z=0 to 9 if x*x*x+y*y*y+z*z*z=1000*x+100*y+z then print x,y,z next z 22+2=2³+2³+2³ 12*3=1³+2³+3³ 32*5=3³+2³+5³ 50*5=5³+0³+5³ 51*3=5³+1³+3³ 151+3=1³+5³+1³+3³ und 153+1 370+1=3³+7³+0³+1³ 371+1=3³+7³+1³+1³ 400+7=4³+0³+0³+7³ 401+7=4³+0³+1³+7³ und 407+1=4³+0³+1³+7³ 464+5=4³+6³+4³+5³ und 

465+4=4³+6³+4³+5³ 624+7=6³+2³+4³+7³ und 627+4=6³+2³+4³+7³ 643+7=6³+4³+3³+7³ und 647+3=6³+4³+3³+7³ 733+7=7³+3³+3³+7³ und 737+3=7³+3³+3³+7³ 773+4=7³+7³+3³+4³ und 774+3=7³+7³+3³+4³ 914+5=9³+1³+4³+5³ und 915+4=9³+1³+4³+5³ 12+32=1³+2³+3³+2³ 20+23=2³+0³+2³+3³ 21+23=2³+1³+2³+3³

 30+32=3³+0³+3³+2³ 31+32=3³+1³+3³+2³ 107*8=1³+0³+7³+8³ 180*3=1³+8³+0³+3³ 989*2=9³+8³+9³+2³ 18*30=1³+8³+3³+0³ Terms with equal digits 3³+7³=37*(3+7) 4³+8³=48*(4+8) 14³+7³=147*(14+7) 14³+8³=148*(14+8) Cube numbers are written in the digits 1 to 9.

No digit is twice or more.

125*438976=380³ 24+76=100, 13824 and 438976 25+75=100, 15625 and 421875 49+51=100, 117649 and 132651 125+875=1000, 1953125 and 669921875 251+749=1000, 15813251 and 420189749 0624+9376=10000, 242970624 and 824238309 376 0625+9375=10000, 244140625 and 823974609 375 21952 and 2+1+9+

5+2, plus 6+8+5+9 and 6859 The bases form an arithmetic progression 180³ = 6³+7³+8³+...+67³+68³+69³ 540³ = 34³+35³+ ...

+158³ 2856³ = 213³+214³+ ... +555³ 5544³ = 406³+407³+ ... +917³ 16830³ = 1134³+1135³+ ... +2133³ 3990³ = 290³+293³+ ... +935³ 29880³ = 2108³+2111³+ ...

+4292³ 408³ = 149³+256³+363³ 440³ = 230³+243³+265³+269³+282³ 1155³ = 435³+506³+577³+648³+719³+790³ 2128³ = 553³+710³+867³+1024³+1181³+1338³+1475³ 168³ = 28³+41³+54³+67³+80³+93³+106³+119³ 64085³ = 935³+5868³+10801³+15734³+20667³+25600³+30533³+35466³+40399³+45332³

 495³ = 15³+52³+89³+126³+163³+200³+237³+274³+311³+248³ Cube Numbers on the Internet top Deutsch God's Number is 20 God's Number is 20 R L U2 F U' D F2 R2 B2 L U2 F' B' U R2 D F2 U R2 U Superflip, the first position proven to require 20 moves.

New results: God's Number is 26 in the quarter turn metric! Every position of Rubik's Cube™ can be solved in twenty moves or less. With about 35 CPU-years of idle computer time donated by Google, a team of researchers has essentially solved every position of the Rubik's Cube™, and shown that no position requires more than twenty moves. We consider any twist of any face to be one move (this is known as the half-turn metric.) Every solver of the Cube uses an algorithm, which is a sequence of steps for solving the Cube. One algorithm might use a sequence of moves to solve the top face, then another sequence of moves to position the middle edges, and so on. There are many different algorithms, varying in complexity and number of moves required, but those that can be memorized by a mortal typically require more than forty moves. One may suppose God would use a much more efficient algorithm, one that always uses the shortest sequence of moves; this is known as God's Algorithm . The number of moves this algorithm would take in the worst case is called God's Number. At long last, God's Number has been shown to be 20.

It took fifteen years after the introduction of the Cube to find the first position that provably requires twenty moves to solve; it is appropriate that fifteen years after that, we prove that twenty moves suffice for all positions. A History of God's Number By 1980, a lower bound of 18 had been established for God's Number by analyzing the number of effectively distinct move sequences of 17 or fewer moves, and finding that there were fewer such sequences than Cube positions. The first upper bound was probably around 80 or so from the algorithm in one of the early solution booklets. This table summarizes the subsequent results. Date How did we solve all 43,252,003,274,489,856,000 positions of the Cube? We partitioned the positions into 2,217,093,120 sets of 19,508,428,800 positions each. We reduced the count of sets we needed to solve to 55,882,296 using symmetry and set covering.

We did not find optimal solutions to each position, but instead only solutions of length 20 or less. We wrote a program that solved a single set in about 20 seconds. We used about 35 CPU years to find solutions to all of the positions in each of the 55,882,296 sets. Partitioning We broke the problem down into 2,217,093,120 smaller problems, each comprising 19,508,428,800 different positions. Each of these subproblems was small enough to fit in the memory of a modern PC, and the way we broke it down (mathematically, using cosets of the group generated by {U,F2,R2,D,B2,L2}, or more concisely, cosets of H) allowed us to solve each set rapidly. Symmetry If you take a scrambled Cube and turn it upside down, you have not made it any more difficult; it will still take the same number of moves to solve. Instead of solving both of these positions, you can simply solve one, and then turn the solution upside down for the other.

There are 24 different ways you can orient the Cube in space, and another factor of two using a mirror, for a total reduction of a factor of about 48 in the number of positions that need solving. Using similar symmetry arguments and by finding a solution to a large "set cover" problem, we were able to reduce the number of sets that needed solving from 2,217,093,120 down to 55,882,296. Good vs. Optimal Solutions 1,000,000,000 Solution rate, in positions/second An optimal solution to a position is one that requires no more moves than is required. Since a position that required 20 moves was already known, we did not need to optimally solve every position; we just needed to find a solution of 20 moves or less for each sequence. This is substantially easier; the table at left show the rate a good desktop PC has when solving random positions.

Fast Coset Solving Program Using a combination of mathematical tricks and careful programming, we were able to solve a complete coset of H, either optimally, or with sequences of twenty moves or less, on a single desktop PC, at the rates shown in the table at left. Lots of Computers Finally, we were able to distribute the 55,882,296 cosets of H among a large number of computers at Google and complete the computation in just a few weeks. Google does not release information on their computer systems, but it would take a good desktop PC (Intel Nehalem, four-core, 2.8GHz) 1.1 billion seconds, or about 35 CPU years, to perform this calculation. What are the Hardest Positions? Distance 20 about 490,000,000 We have known for fifteen years that there are positions that require 20 moves; we have just proved that there are none that require more. Distance-20 positions are both rare and plentiful; they are rarer than one in a billion positions, yet there are probably more than one hundred million such positions. We do not yet know exactly how many there are.

The table on the right gives the count of positions at each distance; for distances 16 and greater, the number given is just an estimate. Our research has confirmed the prior results for entries 0 through 14 below, and the entry for 15 is a new result, which has since been independently confirmed by another researcher. To date we have found about twelve million distance-20 positions. The following position was the hardest for our programs to solve: F U' F2 D' B U R' F' L D' R' U' L U B' D2 R' F U2 D2 The hardest position for our programs. Source Released You may examine our source code , or even rerun part of the proof on your own computer. Known Distance-20 Positions Released You can download our list of known distance-20 positions here . Site Content Some results on Rubik's Clock including a full state space exploration. Source code for the half-turn God's Number result on this page (quarter-turn code to follow). All known hard positions in both the half-turn and quarter-turn metric.

Contact Our group consists of Tomas Rokicki, a programmer from Palo Alto, California, Herbert Kociemba, a math teacher from Darmstadt, Germany, Morley Davidson, a mathematician from Kent State University, and John Dethridge, an engineer at Google in Mountain View. Email may be sent to rokicki@gmail.com or to davidson@math.kent.edu. Rubik's Cube is a registered trademark of Seven Towns, Ltd. Thanks to Lucas Garron for writing the Cube animator on this page. How many primes are there? How Many Primes Are There? Contents: Consequence One: You can Approximate pi(x) with x/(log x - 1) Consequence Two: The nth prime is about n log n Consequence Three: The chance of a random integer x being prime is about 1/log x History of the Prime Number Theorem and other approximations of pi(x) Primes: [ Home || Largest | Proving | How Many? | Mersenne | Glossary | Mailing List ] Notes: (1) Rather than fill this document with gifs like " " (which can not be displayed on some browsers and display poorly on others), I am going to just write pi(x).

(2) log x, in this document, is the natural logarithm. This is sometimes denoted ln x, but log x is the mathematical standard. 1. Introduction: Asking the Correct Question Over 2,300 years ago Euclid proved that the number of primes is infinite, so two possible questions come to mind: How many primes are there less than the number x? There are infinitely many primes, but how big of an infinity? This document will focus on the first question. The second question is discussed on the page " How Big of an Infinity? ." 1.1. pi(x) is the number of primes less than or equal to x Let x be a positive real number. The question "how many primes are there less than x?" has been asked so frequently that its answer has a name: = pi(x) = the number of primes less than or equal to x. The primes under 25 are 2, 3, 5, 7, 11, 13, 17, 19 and 23 so pi(3) = 2, pi(10) = 4 and pi(25) = 9.

(A longer table can be found in the next sub-section .) Look at the following graph and notice how irregular the graph of pi(x) is for small values of x. Now back up and view a larger portion of the graph of pi(x). So even though pi(x) is "locally" irregular , there is a definite trend to its values. ( Graph to 1,000,000 .) In this document we will study the function pi(x), the prime number theorem (which quantifies this trend) and several classical approximation to pi(x). Table 1. Values of pi(x) 1.2. A Table of values of pi(x) For the smaller values of x in this table (say to 10,000,000,000) the value of pi(x) can be found by finding and counting all of the primes. Before the age of computers many mathematicians formed tables of primes. The most widely distributed was D. N. Lehmer's table of primes to 10,006,721 [ Lehmer14 ]. By far the most amazing was a table by Kulik completed in 1867.

This table listed the smallest factors of integers (hence all the primes) up to 100,330,200! In the 1870's Meissel developed a clever way to calculate pi(x) far beyond the known tables of primes and in 1885 (slightly mis-)calculated pi(109). Meissel's methods were simplified by D. H. Lehmer in 1959 and then in 1985 improved using sieve techniques by Lagarias, Miller and Odlyzko [ LMO85 ]. In 1994 Deléglise and Rivat [ DR96 ] improved the technique once again to find the values for pi(1017) and pi(1018). Deléglise continued this work with an improved algorithm to find pi(1020) and other values (see his e-mail messages of 18 Apr 1996 and 19 Jun 1996 ). See Riesel94 for practical information about how these calculations are made.

Xavier Gourdon's distributed computing project determined pi(4*1022), but stopped when they found an error of at least one in the calculation of pi(1023). Tomás Oliveira e Silva has extensive tables of values of pi(x) and pi2(x). In 2007 he reevaluated pi(1023) to get the value in the table. This calculation was done on a single machine and verified in 2008. The value given for pi(1024) was found by an analytic methods assuming the unproven Riemann Hypothesis by J. Buethe, J. Franke, A. Jost, T. Kleinjung. Their method "is similar to the one described by Lagarias and Odlyzko, but uses the Weil explicit formula instead of complex curve integrals" (see their e-mail announcing the result in July 2010). This value was later verified unconditionally by D. J. Platt [ Platt2012 ]. In May 2013, J. Buethe, J. Franke, A. Jost, and T.

Kleinjung completed calculating pi(10^25) unconditionally, using an analytic method based on Weil's explicit formula. 2. The Prime Number Theorem: approximating pi(x) Even though the distribution of primes seems random (there are (probably) infinitely many twin primes and there are (definitely) arbitrarily large gaps between primes), the function pi(x) is surprisingly well behaved: In fact, it has been proved (see the next section ) that: The Prime Number Theorem: The number of primes not exceeding x is asymptotic to x/log x. In terms of pi(x) we would write: The Prime Number Theorem: pi(x) ~ x/log x. This means (roughly) that x/log x is a good approximation for pi(x)--but before we consider this and other consequences lets be a little more specific: "a(x) is asymptotic to b(x)" and "a(x) ~ b(x)" both mean that the limit (as x approaches infinity) of the ratio a(x)/b(x) is 1. If you have not had calculus then this means that you can make a(x)/b(x) as close to 1 as you want by just requiring that x is large enough.

Warning: a(x) ~ b(x) does not mean that a(x)-b(x) is small! For example, x2 is asymptotic to x2-x, but the difference between them, x, gets arbitrarily large as x goes to infinity. 5428681 5740304 The prime number theorem clearly implies that you can use x/(log x - a) (with any constant a) to approximate pi(x). The prime number theorem was stated with a=0, but it has been shown that a=1 is the best choice: There are longer tables below and (of pi(x) only) above . Example: Someone recently e-mailed me and asked for a list of all the primes with at most 300 digits. Since the prime number theorem implies this list would have about 1.4*10297 entries we know that there can be no such list!

Note that Pierre Dusart [ Dusart99 ] showed that if x>598 then (x/log x)(1 + 0.992/log x) < pi(x) <(x/log x)(1 + 1.2762/log x) (The upper bound holds for all x > 1.) This gives a tight bound for larger x. Note x/log x< pi(x) for x > 10. Let p(n) be the nth prime. It is easy to show that the prime number theorem is equivalent to the statement Theorem: p(n) ~ n log n [see Hardy and Wright , page 10]. A better estimate is Theorem: p(n) ~ n (log n + log log n - 1) [see Ribenboim95 , pg. 249]. Example: These formulae predict that the one millionth prime is about 13,800,000 and 15,400,000 respectively. In fact, the one millionth prime is 15,485,863.

There have been many improvements on these bounds; for example, Robin [ Robin83 ] showed that if n>8601 [actually Robin erroneously used 7021], then n (log n + log log n - 1.0073) < p(n) < n (log n + log log n - 0.9385) More recently Massias and Robin [ MR96 ] showed that if n > 15985, then p(n) < n (log n + log log n - 0.9427) and if n > 13, then p(n) < n (log n + log log n - 1 + 1.8 log log n / log n) (which is better for large n). Pierre Dusart [ Dusart99 ] made these results stronger and showed p(n) > n (log n + log log n - 1) for all n. Dusart's article also gives better bounds getting even closer to the next term in the following well known asymptotic expansion for pn.

The first terms of this asymptotic expansion were given by Cipolla [ Cipolla1902 ] in 1902: p(n) = n (log n + log log n - 1 + (log log (n) - 2)/log n - ((log log (n))2 - 6 log log (n) + 11)/(2 log2 n) + O((log log n / log n)3)) Again Ribenboim95 and Riesel94 are excellent starting places to look up more information. By the way, if you are interested in the nth prime for small n (say less than 1,000,000,000), then use the nth prime page ." Consequence Three: The chance of a random integer x being prime is about 1/log x Let x be a positive integer. Since about x/log x of the x positive integers less than or equal to x are prime, the probability of one of them being prime is about 1/log x. Example: Suppose I want to find a 1000 digit prime.

If I am choosing 1000 digit integers x to test for primality at random, then I'd expect to test about log(101000) of them, or about 2302 integers before finding a prime. Obviously if I used odd integers I could multiply this estimate by 1/2, and if I choose integers not divisible by 3, then I could multiply by 2/3,... Another way to say this is that the density of primes less than x is about 1/log x. Below is a graph of the actual density for small values of x. 3. History of the Prime Number Theorem In 1798 Legendre published the first significant conjecture on the size of pi(x), when in his book Essai sur la Théie des Nombres he stated Legendre: pi(x) is approximately x/(log x - 1.08366) Clearly Legendre's conjecture is equivalent to the prime number theorem, the constant 1.08366 was based on his limited table for values of pi(x) (which only went to x = 400,000).

In the long run 1 is a better choice than Legendre's 1.08366. Gauss was also studying prime tables and came up with a different estimate (perhaps first considered in 1791), communicated in a letter to Encke in 1849 and first published in 1863. Gauss: pi(x) is approximately Li(x) (the principal value of integral of 1/log u from u=0 to u=x). Notice again that Gauss' conjecture is equivalent to the prime number theorem. Let's compare these estimates: Table 3. Comparisons of approximations to pi(x) x 454011971 455050683.3 In this table Gauss' Li(x) is always larger than pi(x), this is true for all small x > 2. However in 1914 Littlewood proved that pi(x)-Li(x) assumes both positive and negative values infinitely often.

In 1986 Te Riele showed there are more than 10180 successive integers x for which pi(x)>Li(x) between 6.62.10370 and 6.69.10370. Tchebycheff made the first real progress toward a proof of the prime number theorem in 1850, showing there exist positive constants a < 1 < b such that a(x/log x) < pi(x) < b(x/log x) and that if pi(x)/(x/log x) had a limit, then its value must be one. Sylvester in 1982 refined Tchebycheff's method and showed that we can use a = 0.95695 and b = 1.04423 if x is large enough. (In 1962 it was shown that we can use a = 1 for all x > 10 [ RS62 ].) Finally, in 1896 Hadamard and independently de la Vallée Poussin completely proved the prime number theorem using Riemann's work relating pi(x) to the complex zeta function.

de la Vallée Poussin also proved that Gauss' Li(x) is a better approximation to pi(x) than x/(log x -a) no matter what value is assigned to the constant a (and also that the best value for a is 1). A much better approximation than any of these is the Riemann function [ Ribenboim91 , Riesel94 ]. In 1949 Atle Selberg [ Selberg49 ] and Paul Erdös [ Erdös49 ] independently gave the first elementary proofs of the prime number theorem-- here elementary means not using modern complex analysis--in fact their proofs are very difficult! An easier to read (but less elementary) proof is in Hardy and Wright's text [ HW79 sect. 22.15-16]. Finally, when Hadamard and de la Vallée Poussin proved the Prime number theorem , they actually showed for some positive constant a. The error term depended on what was known about the zero-free region of the Riemann zeta function within the critical strip. As our knowledge of the size of this region increases, the error term decreases.

In 1901 von Koch showed that the Riemann hypothesis is equivalent to the far tighter estimate: 4. More Accurate Estimates This page focused on the prime number theorem in it simplest form, but there are far better estimates for pi(x). To cut to the chase, the Riemann zeta function provides a way to give an exact formula for pi(x) by summing over the non-trivial zeros of the zeta function (in order of increasing magnitude). (At the primes, the graph of pi(x) takes a step up one unit, this formula approches the value in the middle of that step.) The first (and dominant) term above is called Riemann's function R(x). The last form above for R(x) is the Graham series and is an excellent way to calculate this function. The graph on the right shows how close of an approximaton R(x) is, at least for small values of x. An even better one for the smallest small x values is the following (they are essentially the same for large x). To appreciate how close of an approximation these are, see the impressive tables of deviations by Andrey Kulsha. Matthew R.

Watkins also has a beautiful development of this information and some excellent animations. Warning It is easy to look at a graph like the one on the left which shows Li(x) (blue), R(x) (black), pi(x) (red) and x/ln x (green); and then proclaim "R(x) is the best estimate of pi(x)." Indeed it is for that range, but as we mentioned above, Li(x)-pi(x) changes value infinitely often, and near where it does, Li(x) would be the best value. A. E. Ingham says it this way: Considerable importance was attached formerly to a function suggested by Riemann as an approximation to pi(x)... This function represents pi(x) with astonishing accuracy for all values of x for which pi(x) has been calculated, but we now see that its superiority over Li(x) is illusory... and for special values of x (as large as we please) the one approximation will deviate as widely as the other from the true value. ...

And we can see in the same way that the function Li(x)-(1/2)Li(x1/2) is 'on the average' a better approximation than Li(x) to pi(x); but no importance can be attached to the latter terms in Riemann's formula even by repeated averaging. The problem is that the contributions from the non-trivial zeros at times swamps that of any but the main terms in these expansions.

Question: 6,859 is the cube of what number, (less than twenty)?
Answer: 19