10
$\begingroup$

What's the longest possible repeating decimal (repetend) that can be created from a fraction if:

  • The numerator has to be less than or equal to 9,999
  • The denominator has be less than or equal to 9,999?

I know the repeating decimal part can't exceed the denominator - 1. So the longest possible repeating decimal part has to be 9,998 or less.

The reason I want to know is to test an algorithm that I wrote which accepts fractions with numerators and denominators up to 9,999. The largest repeating decimal part I was able to create so far was 1/97 which equaled 0.[01030927 83505154 63917525 77319587 62886597 93814432 98969072 16494845 36082474 22680412 37113402 06185567] (96 repeating digits).

$\endgroup$
6
  • $\begingroup$ Could you explain what you mean by the largest possible repeating decimal? Because all fractions will produce a repeating decimal and the largest would therefore be 9999/1 = 9999. Do you mean the longest period of repetition? $\endgroup$ Commented Jan 27, 2013 at 1:28
  • $\begingroup$ I mean the longest period of repetition. For 1/97 I get 96 repeating digits. $\endgroup$ Commented Jan 27, 2013 at 1:30
  • $\begingroup$ I'm looking for a fraction that will create a period of repetition of 9,998 repeating digits? $\endgroup$ Commented Jan 27, 2013 at 1:32
  • 2
    $\begingroup$ If you want a fraction with a period of exactly $9998$, then you need to find a denominator which divides $10^{9998}-1$ and doesn't divide $10^r-1$ for any $r$, $1\le r\le9997$. Theory guarantees there are some, but they may have hundreds or thousands of digits. $\endgroup$ Commented Jan 27, 2013 at 3:49
  • 1
    $\begingroup$ The repeating part is called the repetend. You want to know what the longest possible repetend is. $\endgroup$ Commented Nov 18, 2016 at 3:14

6 Answers 6

Reset to default
11
$\begingroup$

The numerator doesn't matter (for this question), so you might as well let it be $1$. The denominator should be the largest prime under $10000$ which has $10$ as a primitive root. I don't know offhand what that prime is, but I'm sure such primes are tabulated and shouldn't be hard to locate.

The table at the Online Encyclopedia doesn't go far enough. There is an applet which claims to find these primes, but I couldn't make it work --- maybe you'll have better luck.

$\endgroup$
5
  • $\begingroup$ I just did 1/9973 and got 0.[00010027073097362879775393562619071493031184197332798556101473979745312343326982853705003509475584077007921387746916675022560914469066479494635515892910859320164443998796751228316454426952772485711420836257896320064173267823122430562518800762057555399578862929910759049433470369998997292690263712022460643738092850696881580266720144389852602025468765667301714629499649052441592299207861225308332497743908553093352050536448410708914067983555600120324877168354557304722751428857916374210367993582673217687756943748119923794244460042113707008924095056652963] --- 554 repeati $\endgroup$ Commented Jan 27, 2013 at 1:38
  • $\begingroup$ I found this list of primes... primes.utm.edu/lists/small/10000.txt $\endgroup$ Commented Jan 27, 2013 at 1:39
  • 11
    $\begingroup$ 1/9967 would be the largest, producing a period of 9966. $\endgroup$ Commented Jan 27, 2013 at 1:43
  • $\begingroup$ @DoctorBatmanGod: Please don't make edits that change the meaning of the post, unless it is marked Community Wiki. $\endgroup$ Commented Jan 27, 2013 at 1:52
  • $\begingroup$ Here is a JS code that i have come up with. Have fun. :) $\endgroup$ Commented Jan 30, 2022 at 21:46
3
$\begingroup$

This question is a variation of Problem 26 on Project Euler. Given the fact that the absolute value of the denominator can be no greater than 10,000, all irreducible fractions of the form n/9967 will have a digital representation with the longest possible repetend of 9966 digits. This is because 9967 is the largest full repetend prime smaller than 10,000.

The following C++ program can be used find the denominator, that is no greater than a certain value, of an irreducible fraction whose decimal expansion will have the longest possible repetend:

#include <iostream>
#include <tuple>
using std::cout;

std::tuple<int, int> maxRepetendDenom(int dMax)
{
    int d, rep = 0;
    int i, j, value, counter;
    for (i = 3; i <= dMax; i += 2) {
        counter = 1;
        value = 10%i;
        j = dMax;
        while (value != 1 && j > 0) {
            value *= 10;
            value %= i;
            counter++;
            j--;
        }
        if (counter > rep && j > 1) {
            rep = counter;
            d = i;
        }
    }
    return {d, rep};
}

int main()
{
    while (true) {
        int d, rep, dMax;
        cout << "Enter the maximum allowed absolute value of the denominator: ";
        std::cin >> dMax;
        if (dMax <= 0) {
            return 0;
        }
        if (dMax < 3) {
            cout << "No fraction with an absolute value of the denominator"
                 << " less than 3 can have a repetend.\n\n";
        } else {
            std::tie(d, rep) = maxRepetendDenom(dMax);
            std::string digits = rep > 1 ? " digits)" : " digit)";
            cout << "Fractions with an absolute value of the denominator no greater"
                 << " than " << dMax << " will have the longest possible repetend "
                 << "(of " << rep << digits << " in their decimal expansion if they"
                 << " are in lowest terms and their denominator is " << d << ".\n\n";
        }
    }
    return 0;
}

You can use GDB Online to run the program.

$\endgroup$
4
  • $\begingroup$ It's not actually clear to me that it had to be a full repetend prime. There could have been a prime that was much larger than the largest full repetend prime whose repetend was longer, e.g. 9967 is the largest full repetend prime, giving a period of 9966, but there could have been a prime 9991 (which, for arguement's sake is prime) whose repetend was 9970. This would have not been full but still larger than 9967. $\endgroup$ Commented Oct 17, 2019 at 19:59
  • 1
    $\begingroup$ Or even a composite. For example, 1/289 has a repetend of length 272 which is longer than any before it and 289 is not prime. The same is true for 1/361 which has a repetend of length 342. It is interesting to note that each has a deficiency in length equal to its prime factor: 289 = $17^2$ and 272+17=289; 361 = $19^2$ and 342+19=361. (For 1/$17^3$, the repetend length is $17^3 - 17^2$.) $\endgroup$ Commented Jan 30, 2020 at 13:23
  • 1
    $\begingroup$ @IskyMathews 9991's repetend seems to be 1632. $\endgroup$ Commented Jan 22, 2022 at 14:34
  • $\begingroup$ @IskyMathews The denominator doesn't have to be a prime number. It depends on the constraints. You can run my program and input an upper bound of 312, for example. The program will correctly calculate the denominator (289 in this case, which is a composite) that will generate the longest repetend (272 digits long). $\endgroup$ Commented Oct 15, 2022 at 12:55
2
$\begingroup$

Several answer indicate that you must look for the largest full-repetend prime lower than your upper limit for the denominator. Since every number that is coprime to the base (but not necessarily prime) has a repetend and not every prime has a full repetend it is possible that a non-prime will hold the distinction of having the longest repetend in that range.

In base 10 only the squares 289 and 361 have the longest repetend up to their value...at least up to $10^8$. So for limits above 361 (and certainly below $10^8$ but only with diminishing probability at higher values) the "full repetend prime" is the right answer.

But in general it appears that one must check all numbers that are coprime to the base and not only primes. For example, in base 8 (below 11467) the repetend for $107^2$ with length 5671 is the longest.

$\endgroup$
0
$\begingroup$

1/9801= 0.010203040506070809010111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697990010203..., about 100 repeating digits

$\endgroup$
3
  • $\begingroup$ since each number is represented by two digits (01, 02, 03...) and every number to 99 is represented, that's 99x2 + 1 (for the final zero). That's 199 repeating digits. $\endgroup$ Commented Dec 31, 2014 at 11:32
  • $\begingroup$ What is special about the numbers 9801, 998001, 99980001 ..? $\endgroup$ Commented Mar 23, 2016 at 6:08
  • $\begingroup$ @LưuVĩnhPhúc - $99^2, 999^2, 9999^2$? $\endgroup$ Commented Nov 18, 2016 at 4:02
0
$\begingroup$

You can find more details on on my main web page at “engert.us/erwin/Miscellaneous.html” where I have a listing of repeating digits for all odd numbers under 28,000. I also have a listing of prime numbers with how many repeating digits hey have in “engert.us/erwin/miscellaneous/Reciprocals%20of%20prime%20numbers.pdf. For your interest here a just a few of the numbers under 9,999 they are: 1/9871, 4935 1/9883, 4941 1/9887, 9886 1/9901, 12 1/9907, 4953 1/9923, 4961 1/9929, 1241 1/9931, 9930 1/9941, 1988 1/9949, 9948 1/9967, 9966 1/9973, 554 Erwin

$\endgroup$
0
$\begingroup$

1/9679 = 00010331645831180907118503977683645004649240624031408203326789957640252092158280814133691497055480938113441471226366360161173674966422151048662051864862072528153734889967971897923339187932637669180700485587354065502634569686951131315218514309329476185556359128009091848331439198264283500361607604091331749147639218927575162723421841099287116437648517408823225539828494679202396941832833970451492922822605641078623824775286703171815270172538485380721148879016427316871577642318421324516995557392292592209939043289596032648000826531666494472569480318214691600371939249922512656266143196611220167372662465130695319764438475049075317698109308812893893997313772083892964149188965802252298791197437751833867135034611013534456038846988325240210765574956090505217481144746358094844508730240727347866515135861142680028928608327306539931811137514206013017873747287942969315011881392705858043186279574336191755346626717636119433825808451286289905982022936253745221613803078830457691910321314185349726211385473705961359644591383407376795123463167682611840066122533319557805558425457175328029755139993801012501291455728897613389812997210455625581155078003926025415848744705031511519785101766711437131935117264180183903295795020146709370802768881082756483107759066019216861245996487240417398491579708647587560698419258187829321210868891414402314288666184523194544891001136481041429899783035437545200950511416468643454902365946895340427730137410889554706064676102903192478561834900299617729104246306436615352825705134827978096910837896476908771567310672590143609877053414608947205289802665564624444674036574026242380411199504081 (1613 digits? K.)

$\endgroup$
1
  • 1
    $\begingroup$ This is not as good as 1/9967 cited in a comment to Gerry Myerson's answer. $\endgroup$ Commented Nov 18, 2016 at 3:09

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.