StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p><strong>edit:</strong> (I'm leaving post here for posterity. But <em>please</em> don't upvote it anymore: it may be theoretically useful but it's not really practical. I have posted another answer which is much more useful from a practical point of view, doesn't require any factoring, and doesn't require the use of bignums.)</p> <hr> <p>@Daniel Bruckner has the right approach, I think. (with a few additional twists required)</p> <p>Maybe there's a simpler method, but the following will always work:</p> <p>Let's use the examples q = x/y = 33/57820 and 44/65 in addition to 33/59, for reasons that may become clear shortly.</p> <p><strong>Step 1: Factor the denominator</strong> (specifically factor out 2's and 5's)</p> <p>Write q = x/y = x/(2<sup>a<sub>2</sub></sup>5<sup>a<sub>5</sub></sup>z). Factors of 2 and 5 in the denominator do not cause repeated decimals. So the remaining factor z is coprime to 10. In fact, the next step requires factoring z, so you might as well factor the whole thing.</p> <p>Calculate a<sub>10</sub> = max(a<sub>2</sub>, a<sub>5</sub>) which is the smallest exponent of 10 that is a multiple of the factors of 2 and 5 in y.</p> <p>In our example 57820 = 2 * 2 * 5 * 7 * 7 * 59, so a<sub>2</sub> = 2, a<sub>5</sub> = 1, a<sub>10</sub> = 2, z = 7 * 7 * 59 = 2891.</p> <p>In our example 33/59, 59 is a prime and contains no factors of 2 or 5, so a<sub>2</sub> = a<sub>5</sub> = a<sub>10</sub> = 0. </p> <p>In our example 44/65, 65 = 5*13, and a<sub>2</sub> = 0, a<sub>5</sub> = a<sub>10</sub> = 1. </p> <p>Just for reference I found a good online factoring calculator <a href="http://www.alpertron.com.ar/ECM.HTM" rel="nofollow noreferrer">here</a>. (even does totients which is important for the next step)</p> <p><strong>Step 2: Use <a href="http://en.wikipedia.org/wiki/Euler%27s_theorem" rel="nofollow noreferrer">Euler's Theorem</a> or <a href="http://en.wikipedia.org/wiki/Carmichael_function" rel="nofollow noreferrer">Carmichael's Theorem</a>.</strong></p> <p>What we want is a number n such that 10<sup>n</sup> - 1 is divisible by z, or in other words, 10<sup>n</sup> &equiv; 1 mod z. Euler's function φ(z) and Carmichael's function λ(z) will both give you valid values for n, with λ(z) giving you the smaller number and φ(z) being perhaps a little easier to calculate. This isn't too hard, it just means factoring z and doing a little math.</p> <p>φ(2891) = 7 * 6 * 58 = 2436</p> <p>λ(2891) = lcm(7*6, 58) = 1218</p> <p>This means that 10<sup>2436</sup> &equiv; 10<sup>1218</sup> &equiv; 1 (mod 2891).</p> <p>For the simpler fraction 33/59, φ(59) = λ(59) = 58, so 10<sup>58</sup> &equiv; 1 (mod 59).</p> <p>For 44/65 = 44/(5*13), φ(13) = λ(13) = 12.</p> <p><strong>So what?</strong> Well, the period of the repeating decimal must divide both φ(z) and λ(z), so they effectively give you upper bounds on the period of the repeating decimal.</p> <p><strong>Step 3: More number crunching</strong></p> <p>Let's use n = λ(z). If we subtract Q' = 10<sup>a<sub>10</sub></sup>x/y from Q'' = 10<sup>(a<sub>10</sub> + n)</sup>x/y, we get:</p> <p>m = 10<sup>a<sub>10</sub></sup>(10<sup>n</sup> - 1)x/y</p> <p><strong>which is an integer</strong> because 10<sup>a<sub>10</sub></sup> is a multiple of the factors of 2 and 5 of y, and 10<sup>n</sup>-1 is a multiple of the remaining factors of y.</p> <p>What we've done here is to shift left the original number q by a<sub>10</sub> places to get Q', and shift left q by a<sub>10</sub> + n places to get Q'', which are repeating decimals, but the difference between them is an integer we can calculate.</p> <p>Then we can rewrite x/y as m / 10<sup>a<sub>10</sub></sup> / (10<sup>n</sup> - 1).</p> <p>Consider the example q = 44/65 = 44/(5*13)</p> <p>a<sub>10</sub> = 1, and λ(13) = 12, so Q' = 10<sup>1</sup>q and Q'' = 10<sup>12+1</sup>q.</p> <p>m = Q'' - Q' = (10<sup>12</sup> - 1) * 10<sup>1</sup> * (44/65) = 153846153846*44 = 6769230769224</p> <p>so q = 6769230769224 / 10 / (10<sup>12</sup> - 1).</p> <p>The other fractions 33/57820 and 33/59 lead to larger fractions.</p> <p><strong>Step 4: Find the nonrepeating and repeating decimal parts.</strong></p> <p>Notice that for k between 1 and 9, k/9 = 0.kkkkkkkkkkkkk...</p> <p>Similarly note that a 2-digit number kl between 1 and 99, k/99 = 0.klklklklklkl...</p> <p>This generalizes: for k-digit patterns abc...ij, this number abc...ij/(10<sup>k</sup>-1) = 0.abc...ijabc...ijabc...ij...</p> <p>If you follow the pattern, you'll see that what we have to do is to take this (potentially) huge integer m we got in the previous step, and write it as m = s*(10<sup>n</sup>-1) + r, where 1 ≤ r < 10<sup>n</sup>-1.</p> <p>This leads to the final answer: </p> <ul> <li>s is the non-repeating part</li> <li>r is the repeating part (zero-padded on the left if necessary to ensure that it is n digits) </li> <li>with a<sub>10</sub> = 0, the decimal point is between the nonrepeating and repeating part; if a<sub>10</sub> > 0 then it is located a<sub>10</sub> places to the left of the junction between s and r.</li> </ul> <p>For 44/65, we get 6769230769224 = 6 * (10<sup>12</sup>-1) + 769230769230</p> <p>s = 6, r = 769230769230, and 44/65 = 0.6769230769230 where the underline here designates the repeated part.</p> <p>You can make the numbers smaller by finding the smallest value of n in step 2, by starting with the Carmichael function λ(z) and seeing if any of its factors lead to values of n such that 10<sup>n</sup> &equiv; 1 (mod z).</p> <p><strong>update:</strong> For the curious, the Python interpeter seems to be the easiest way to calculate with bignums. (pow(x,y) calculates x<sup>y</sup>, and // and % are integer division and remainder, respectively.) Here's an example:</p> <pre><code>>>> N = pow(10,12)-1 >>> m = N*pow(10,1)*44//65 >>> m 6769230769224 >>> r=m%N >>> r 769230769230 >>> s=m//N >>> s 6 >>> 44/65 0.67692307692307696 >>> N = pow(10,58)-1 >>> m=N*33//59 >>> m 5593220338983050847457627118644067796610169491525423728813 >>> r=m%N >>> r 5593220338983050847457627118644067796610169491525423728813 >>> s=m//N >>> s 0 >>> 33/59 0.55932203389830504 >>> N = pow(10,1218)-1 >>> m = N*pow(10,2)*33//57820 >>> m 57073676928398478035281909373919059149083362158422691110342442061570390868211691 45624351435489450017295053614666205465236942234520927014873746108612936700103770 32168799723279142165340712556208924247665167762020062262193012798339674852992044 27533725354548599100657212037357315807679003804911795226565202352127291594603943 27222414389484607402282947077135939121411276374956762365963334486336907644413697 68246281563472846765824974057419578000691802144586648218609477689380837080594949 84434451746800415081286751988931165686613628502248356969906606710480802490487720 51193358699411968177101349014181943964026288481494292632307160152196471809062608 09408509166378415773088896575579384296091317883085437564856451054998270494638533 37945347630577654790729851262538913870632998962296783120027672085783465928744379 10757523348322379799377378069872016603251470079557246627464545140089934278796264 26841923209961950882047734347976478727084053960567277758561051539259771705292286 40608785887236250432376340366655136630923555863023175371843652715323417502594258 04219993081978554133517813905223106191629194050501556554825319958491871324801106 88343133863714977516430300933932895191975095122794880664130058803182289865098581 80560359737115185 >>> r=m%N >>> r 57073676928398478035281909373919059149083362158422691110342442061570390868211691 45624351435489450017295053614666205465236942234520927014873746108612936700103770 32168799723279142165340712556208924247665167762020062262193012798339674852992044 27533725354548599100657212037357315807679003804911795226565202352127291594603943 27222414389484607402282947077135939121411276374956762365963334486336907644413697 68246281563472846765824974057419578000691802144586648218609477689380837080594949 84434451746800415081286751988931165686613628502248356969906606710480802490487720 51193358699411968177101349014181943964026288481494292632307160152196471809062608 09408509166378415773088896575579384296091317883085437564856451054998270494638533 37945347630577654790729851262538913870632998962296783120027672085783465928744379 10757523348322379799377378069872016603251470079557246627464545140089934278796264 26841923209961950882047734347976478727084053960567277758561051539259771705292286 40608785887236250432376340366655136630923555863023175371843652715323417502594258 04219993081978554133517813905223106191629194050501556554825319958491871324801106 88343133863714977516430300933932895191975095122794880664130058803182289865098581 80560359737115185 >>> s=m//N >>> s 0 >>> 33/57820 0.00057073676928398479 </code></pre> <p>with the overloaded Python <code>%</code> string operator usable for zero-padding, to see the full set of repeated digits:</p> <pre><code>>>> "%01218d" % r '0570736769283984780352819093739190591490833621584226911103424420615703908682116 91456243514354894500172950536146662054652369422345209270148737461086129367001037 70321687997232791421653407125562089242476651677620200622621930127983396748529920 44275337253545485991006572120373573158076790038049117952265652023521272915946039 43272224143894846074022829470771359391214112763749567623659633344863369076444136 97682462815634728467658249740574195780006918021445866482186094776893808370805949 49844344517468004150812867519889311656866136285022483569699066067104808024904877 20511933586994119681771013490141819439640262884814942926323071601521964718090626 08094085091663784157730888965755793842960913178830854375648564510549982704946385 33379453476305776547907298512625389138706329989622967831200276720857834659287443 79107575233483223797993773780698720166032514700795572466274645451400899342787962 64268419232099619508820477343479764787270840539605672777585610515392597717052922 86406087858872362504323763403666551366309235558630231753718436527153234175025942 58042199930819785541335178139052231061916291940505015565548253199584918713248011 06883431338637149775164303009339328951919750951227948806641300588031822898650985 8180560359737115185' </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload