All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Numbers
Baking the best pie (Posted on 2012-11-02) Difficulty: 4 of 5
Find a p/q fraction(fractions?)that gives more exact digits of pi(3.1415926535..etc) than the number of digits of p and q combined.

Feel free to comment on "pi" approximations.

No Solution Yet Submitted by Ady TZIDON    
Rating: 4.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution more Comment 2 of 2 |

The program uses a variation of the Euclidean Algorithm for finding the greatest common divisor. Of course with pi/1 there's no such thing:

3.14159265358979 =    1*pi   +0
1                =    0*pi   +1
0.14159265358979 =    1*pi   -3
0.00885142487    =   -7*pi  +22
0.00882128054    =  106*pi -333
0.00003014433    = -113*pi +355

At each stage a number on the left is divided into the number above it, with the remainder place below it. The quotient is used to multiply the numbers on the divisor line and subtract from the numbers above. For example, as the 1 is above 0.14159265358979, the quotient is 7 and the remainder is 0.00885142487 as 7*0.14159265358979 + 0.00885142487 = 1. The 7 then is multiplied by the 1*pi - 3 and added to the 0*pi + 1 to get -7*pi + 22.

   10    point 100:kill "pimain.txt"
   11    open "pimain.txt" for output as #2
   20    Ratio=#pi
   30    Rat=cutspc(str(Ratio))
   40    Dn=Ratio:Dr=1
   50    D1=1:N1=0
   60    D2=0:N2=1
   70    Cntnue=1
   80    while Cntnue
   85     Prevden=Den:Prevnum=Num
   90     Q=int(Dn/Dr)
  100     R=Dn-Q*Dr
  110     Den=D1-Q*D2
  120     Num=N1-Q*N2
  130     Dn=Dr
  140     Dr=R
  150     D1=D2:N1=N2
  160     D2=Den:N2=Num
  170     D=cutspc(str(abs(D2)))
  180     N=cutspc(str(abs(N2)))
  190     Den=abs(Den)
  200     Num=abs(Num)
  210     Ld=len(D):Ln=len(N):La=Ld+Ln
  220     Precpi=int(Ratio*10^La+0.5)
  230     Precapp=int((Num/Den)*10^La+0.5)
  240     if Precpi=Precapp then
  250       :print N;"  ";D:print Num/Den;
  255       :print #2,N;"  ";D:print #2,Num/Den;
  260       :if Precpi=Precapp then
  261         :print "*";La;La+1:print Ratio
  262         :print #2,"*";La;La+1:print #2,Ratio:else print:print #2,:endif
  280       :repeat
  290         :A=inkey
  300       :until A>""
  310       :if A=chr(27) then end
  330    wend
 
produces the report shown below. Each entry starts with a numerator and denominator, separated by two spaces. Then appears the decimal result of that division an asterisk and the number of invested digits (length of numerator plus length of denominator), and the requisite number that's one higher. Pi itself is listed below it for comparison. The blank at the beginning of the comparison lines as well as the decimal point add up to the same as the two blanks separating numerator from denominator, so the point of match can be seen.

The method used is keeping track of the Euclidean algorithm for finding gcd, except that one of the numbers is irrational and so the algorithm never terminates, but rather provides the equivalent of successive levels of continued fractions. Levels whose decimal values do not exceed the number of digits used are not reported.

So, starting with the famous 355/113, and continuing with the next, 8958937768937/2851718461558:

(when the numbers get larger, I've split the fraction into two separate lines.)

355 / 113
 3.141592920353982300884955752212389380530973451327433628318584070796460176991150442477876
106194690265486725663716814159292035398230088495575221238938053097345132743362831858407079
646017699115044247787610619469026548672566371681415929203539823008849557522123893805309734
513274336283185840707964601769911504424778761061946902654867256637168141592920353982300884
955752212389380530973451327433628318584070796460176991150442477876106194690265486725663716
8141592920353982300884955752212389 * 6  7
 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034
825342117067982148086513282306647093844609550582231725359408128481117450284102701938521105
559644622948954930381964428810975665933446128475648233786783165271201909145648566923460348
610454326648213393607260249141273724587006606315588174881520920962829254091715364367892590
360011330530548820466521384146951941511609433057270365759591953092186117381932611793105118
5480744623799627495673518857527248
8958937768937 / 2851718461558
 3.141592653589793238462643375557908904121193621399491287039462014350644622064723625916129
389162305458332351678194135645975913296703745110846449097678889488205750218896237449386803
090602205094552624406929361173334079862829622940306473121825116942363401401061807699328672
019202740299293826717277068779953238034876996637901498606615417838580453347940825015351688
899219759826857386963002017776903143623646810574125984766922508799530908563228518869457389
4231429098645114309184263549737275 * 26  27
 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034
825342117067982148086513282306647093844609550582231725359408128481117450284102701938521105
559644622948954930381964428810975665933446128475648233786783165271201909145648566923460348
610454326648213393607260249141273724587006606315588174881520920962829254091715364367892590
360011330530548820466521384146951941511609433057270365759591953092186117381932611793105118
5480744623799627495673518857527248
2646693125139304345 / 842468587426513207
 3.141592653589793238462643383279502884183062184016283770132773708960402899373640293814361
991185808100024072772190087539408546932511469136361425822953524510652737309727603347066432
044924141517542227755052447649621587730202555648237430638911512982925963515397056647149512
639411437136085874445321150310055097682033046462939298973662210800521541507350611826570426
745700512958511889009483075564142452742768281134541523689391989468410827158494246522105543
6513363651205074986098317340589134 * 37  38
 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034
825342117067982148086513282306647093844609550582231725359408128481117450284102701938521105
559644622948954930381964428810975665933446128475648233786783165271201909145648566923460348
610454326648213393607260249141273724587006606315588174881520920962829254091715364367892590
360011330530548820466521384146951941511609433057270365759591953092186117381932611793105118
5480744623799627495673518857527248
4427007044615115050034854648525685871587 / 1409160108506276783085718440252375099653
 3.141592653589793238462643383279502884197169399375105820974944592307816406286208995518742
779532338874566512549482575722776483738164310364510933080500034065887921365707244603278813
140868757692856834029104259114493866808975003212136200564063071939921593919284756571926805
096115588776629767547088427283419790028581370396573485934827270352495589006212049432803698
401513701524334441205297247348644728656294225001774264375416108190408936458525112447206040
2964057554794378435279505455900004 * 80  81
 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034
825342117067982148086513282306647093844609550582231725359408128481117450284102701938521105
559644622948954930381964428810975665933446128475648233786783165271201909145648566923460348
610454326648213393607260249141273724587006606315588174881520920962829254091715364367892590
360011330530548820466521384146951941511609433057270365759591953092186117381932611793105118
5480744623799627495673518857527248
716918301303787149323038550270812273699415  
------------------------------------------
228202182891085034903619974895950891885862
 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628452
600626822784702019248458767796872121533601003832820100098044313701177243985770360962220018
013970792216004028155682360422848774214068276329272567707862360990185953540878640081776806
190832447978333574572018174342784766034030544075744403249533880412612265464971800545949681
883963333817410959650311465499693525761094451878814200972173854786698554470536490055526635
2337838700833645364452042800163588 * 84  85
 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034
825342117067982148086513282306647093844609550582231725359408128481117450284102701938521105
559644622948954930381964428810975665933446128475648233786783165271201909145648566923460348
610454326648213393607260249141273724587006606315588174881520920962829254091715364367892590
360011330530548820466521384146951941511609433057270365759591953092186117381932611793105118
5480744623799627495673518857527248
2635622779696759818963956926355997625653382829357706805515232 
-------------------------------------------------------------
838944787028681613144502774660896402692975681322322888764935
 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034
825342117067982148086513282306647127025671309507908507920526798648941277772785069663663488
303145345584122787774273412227178052341381610589607044493389275752738840918886538101754563
854592453170783331435472378773156584346194070735504913374293062221035315004374702465135144
146461667874544780697215436054660738801130635393905366066964383030077202807103366194049125
1341665502776950572694133404267247 * 121  122
 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034
825342117067982148086513282306647093844609550582231725359408128481117450284102701938521105
559644622948954930381964428810975665933446128475648233786783165271201909145648566923460348
610454326648213393607260249141273724587006606315588174881520920962829254091715364367892590
360011330530548820466521384146951941511609433057270365759591953092186117381932611793105118
5480744623799627495673518857527248
2805566453916402616788439453817210917066487546495895963005320692551644  
----------------------------------------------------------------------
893039538627191313089158596549606265611472858084463970643690535852361
 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034
825342117067982148086513282306647093844609550582231746710937789746699599043842861508673561
478057141097421371217822333506918634132693705173151638722233096375717154269436221953152568
381341616084967820120962125754194883481014901288406196566648637323874352588781530649736818
319772013970542460448893741634964494896484422326316575856853915808383686141498577349759004
8876170923228754107578324844791668 * 139  140
 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034
825342117067982148086513282306647093844609550582231725359408128481117450284102701938521105
559644622948954930381964428810975665933446128475648233786783165271201909145648566923460348
610454326648213393607260249141273724587006606315588174881520920962829254091715364367892590
360011330530548820466521384146951941511609433057270365759591953092186117381932611793105118
5480744623799627495673518857527248
310344899529166378282668219806259094484974141966064716624513822519724343047938730895279048
1796734804918099  987858496468489010389754786152989268495055922473506859285063463155440686
602872966161674984095951267279994
 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034
825342117067982148086513282306647093844609550582231725359408128481117450284102701938521105
559644622948954930381964428810975727231259639496051371963365366831474356053494072296465260
250619797850867451355311345075951499342132570496789134506655446882165579306487183377173650
760286874249679761021133071787098501169151225997473040907213474982226997941020648192278409
6814392790071533877135475435561729 * 211  212
 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034
825342117067982148086513282306647093844609550582231725359408128481117450284102701938521105
559644622948954930381964428810975665933446128475648233786783165271201909145648566923460348
610454326648213393607260249141273724587006606315588174881520920962829254091715364367892590
360011330530548820466521384146951941511609433057270365759591953092186117381932611793105118
5480744623799627495673518857527248
474490238234227174515948361693811988401340891649950114502451856183877768471768408541740671
73766596944222479515740143273879768480709913455315809719544718248 
------------------------------------------------------------------------------------------
--
151034933727656572741457537643244123466736157365649904806452295026919400951667087834668197
43670409392336434093031760588386010342390699617474201564040715683
 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034
825342117067982148086513282306647093844609550582231725359408128481117450284102701938521105
559644622948954930381964428810975665933446128475648233786783165271201909145648566923460348
610454326648213393607260249141273724587006596282344068363966845298801563142651995814418531
442855051211048698606140707115478204868418028234356317665768917127977131470968248165917398
9514993543687770201170429641606333 * 310  311
 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034
825342117067982148086513282306647093844609550582231725359408128481117450284102701938521105
559644622948954930381964428810975665933446128475648233786783165271201909145648566923460348
610454326648213393607260249141273724587006606315588174881520920962829254091715364367892590
360011330530548820466521384146951941511609433057270365759591953092186117381932611793105118
5480744623799627495673518857527248
772187630129478758962601413878408957651530989572869267713572282648872995561869829435008133
162124722139861407125140800260854078374277445389539787473840352996519382056599759670848751
42 
------------------------------------------------------------------------------------------
--
245794956659045432099461284342893767627735779554946120007517646266672883530606187218562361
435775126203830656772401230544053310580823502473597237831126801449174197098907578466956772
15
 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034
825342117067982148086513282306647093844609550582231725359408128481117450284102701938521105
559644622948954930381964428810975665933446128475648233786783165271201909145648566923460348
610454326648213393607260249141273724587006606315588174881520920962829254091715364367892590
360011302426331027503917585800360001043371653829802183319164627479199655446123669208370238
1530432844340310527797778725292668 * 364  365
 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034
825342117067982148086513282306647093844609550582231725359408128481117450284102701938521105
559644622948954930381964428810975665933446128475648233786783165271201909145648566923460348
610454326648213393607260249141273724587006606315588174881520920962829254091715364367892590
360011330530548820466521384146951941511609433057270365759591953092186117381932611793105118
5480744623799627495673518857527248
845228964509364857285451044683744471281013570656725631598459313189458598122135084250110468
058985521881396049580847456432069809811493461158318275911194360635176315140558250144472474
5992482165813705867717921079545509 
------------------------------------------------------------------------------------------
--
269044735492219172645286234173638694854912133950118506154264475181718905898457956147619098
189535710321194254709555411862787728634814404790487538226495756026086716399012778250529209
5264012421812368972205650281709434
 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034
825342117067982148086513282306647093844609550582231725359408128481117450284102701938521105
559644622948954930381964428810975665933446128475648233786783165271201909145648566923460348
610454326648213393607260249141273724587006606315588174881520920962829254091715364367892590
360011330530548820466521384146951941511609433057270365759591953092186120451762892798764212
7201718809489527691718639340288218 * 428  429
 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034
825342117067982148086513282306647093844609550582231725359408128481117450284102701938521105
559644622948954930381964428810975665933446128475648233786783165271201909145648566923460348
610454326648213393607260249141273724587006606315588174881520920962829254091715364367892590
360011330530548820466521384146951941511609433057270365759591953092186117381932611793105118
5480744623799627495673518857527248
190187072856692307609014394471477033962159076831354633719252611556270433968096356432000780
810792937029975234518768883574138700303685336128567115805986770239907322799442690522019469
9766118756059055619036488502928002591 
------------------------------------------------------------------------------------------
--
605384255146420326102361023215940531716391478150345020739231253172134740688232476946000058
713774549796561447468267746412874022717544100946587144148739626803435133473281606663121381
125761746030151344353855924025288111
 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034
825342117067982148086513282306647093844609550582231725359408128481117450284102701938521105
559644622948954930381964428810975665933446128475648233786783165271201909145648566923460348
610454326648213393607260249141273724587006606315588174881520920962829254091715364367892590
360011330530548820466521384146951941511609433057270365759591953092186117381932480464696187
9790707507019889940680942867384216 * 433  434
 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034
825342117067982148086513282306647093844609550582231725359408128481117450284102701938521105
559644622948954930381964428810975665933446128475648233786783165271201909145648566923460348
610454326648213393607260249141273724587006606315588174881520920962829254091715364367892590
360011330530548820466521384146951941511609433057270365759591953092186117381932611793105118
5480744623799627495673518857527248
829811339066982130876058198968068410862650851015911973311226612700024485057349312961541969
285196267406861823954979198922192105880351220076032665770174257080550463817983221086166360
145838459204571042537355859890994714178639 
------------------------------------------------------------------------------------------
--
264137152892430011699969916696643139695705442190816743007777612090652217173046962095469671
017596981860796907631670496695516884285848965487333467142874468050234307173796701062864498
309627509956854801151282493814161519811988
 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034
825342117067982148086513282306647093844609550582231725359408128481117450284102701938521105
559644622948954930381964428810975665933446128475648233786783165271201909145648566923460348
610454326648213393607260249141273724587006606315588174881520920962829254091715364367892590
360011330530548820466521384146951941511609433057270365759591953092186117381932611793104533
5000516759458184301504896794805256 * 444  445
 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034
825342117067982148086513282306647093844609550582231725359408128481117450284102701938521105
559644622948954930381964428810975665933446128475648233786783165271201909145648566923460348
610454326648213393607260249141273724587006606315588174881520920962829254091715364367892590
360011330530548820466521384146951941511609433057270365759591953092186117381932611793105118
5480744623799627495673518857527248
508239685501559807293084935851128442030769369296518599661444679177836287511429446251774461
949809485175658215343577801278333998680876300795076100714009635384445119316669975702361861
604328893720772564173289552095512449550742383 
------------------------------------------------------------------------------------------
--
161777716446087068182119281713961832493697624026118952133686196582342261332207690917434237
379920519659486003859262368656716405017273277436165739558427276397315380418261658678024905
270494976424810609602571991742445112723313661
 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034
825342117067982148086513282306647093844609550582231725359408128481117450284102701938521105
559644622948954930381964428810975665933446128475648233786783165271201909145648566923460348
610454326648213393607260249141273724587006606315588174881520920962829254091715364367892590
360011330530548820466521384146951941511609433057270365759591953092186117381932611793105118
5484779419325170732666655361289588 * 450  451
 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034
825342117067982148086513282306647093844609550582231725359408128481117450284102701938521105
559644622948954930381964428810975665933446128475648233786783165271201909145648566923460348
610454326648213393607260249141273724587006606315588174881520920962829254091715364367892590
360011330530548820466521384146951941511609433057270365759591953092186117381932611793105118
5480744623799627495673518857527248
230727689442532399117749228295838082685261233512775489984766538100233713507641069379372253
906167983144179557796518171105919137121570495317833816165448348095635164916499494875464636
10128540948982550561408502447307624638576097797181979279 
------------------------------------------------------------------------------------------
--
734429045659014884994777619116328565733647035575735046636514858156135551120319770822625997
474542076849225623467727474839182964738634032679620575762111609296156550613690390766163123
1409829601983610983435411476944453990444375332500581033
 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034
825342117067982148086513282306647093844609550582231725359408128481117450284102701938521105
559644622948954930381964428810975665933446128475648233786783165271201909145648566923460348
610454326648213393607260249141273724587006606315588174881520920962829254091715364367892590
360011330530548820466521384146951941511609433057270365759591953092186117381932611793105118
548074462379962749567352250986225 * 471  472
 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034
825342117067982148086513282306647093844609550582231725359408128481117450284102701938521105
559644622948954930381964428810975665933446128475648233786783165271201909145648566923460348
610454326648213393607260249141273724587006606315588174881520920962829254091715364367892590
360011330530548820466521384146951941511609433057270365759591953092186117381932611793105118
5480744623799627495673518857527248
 


In fact, the investment of 433 digits yields 435 significant digits of pi, a gain of 2 ins
tead of just 1, and almost has another (and would have if truncated rather than rounded).
This seems to be the only such case in the above report.

 


  Posted by Charlie on 2012-11-02 11:56:59
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (4)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information