Posts Tagged ‘decimal’

More on repetend lengths

Tuesday, January 27th, 2009

In a previous post, I noted that the length of the repetend (repeating portion of the decimal expansion) of a fraction with prime denominator p is at most p-1, and in fact divides p-1. I also said:

In fact, there’s even more that can be said about non-prime denominators, as well.

This was something of a cop-out, and today I’m going to correct that! In general, suppose the denominator d can be factored as


\displaystyle d = p_1^{a_1} p_2^{a_2} \dots p_n^{a_n},

that is, d can be factored as the product of the prime p_1 to the a_1 power, the prime p_2 to the a_2 power, and so on. (For example, 12 = 2^2 \cdot 3^1.) Then it turns out that the length of the repetend of any fraction with denominator d will be a divisor of


\displaystyle \prod_{i=1}^n p_i^{a_i - 1} (p_i - 1).

(The \Pi denotes a product; you can read about the notation here if you haven’t seen it before.) When d is prime, we can see that this just reduces to d-1 as we would expect. For each additional prime p in the factorization, we multiply by p-1; for each additional power of a prime p beyond the first, we multiply by p.

So, for example, the repetend length for fractions with denominator 221 = 13*17 should evenly divide (13-1)(17-1) = 192; and indeed, the repetend length of 1/221 is 48. As another example, the repetend length of 1/(11^3 \cdot 13) = 1/17303 is 726, which indeed divides 11^2(11 - 1) (13 - 1) = 14520.

You may wonder how I know this. Well, asking for the repetend length of a fraction with denominator d amounts to asking for the smallest power of 10 whose remainder, when divided by d, is 1. Another way to say this is that we want to know the order of the element 10 in the group U(d) (the group of positive integers less than and relatively prime to d under multiplication). By Lagrange’s Theorem, the order of any element of a group divides the order of the group; so the question becomes, what is the order of U(d)? The answer, as explained e.g. on p. 155 of Contemporary Abstract Algebra by Joseph Gallian (Houghton Mifflin, 2002), is the above formula.

Now, maybe that went way over your head. It certainly did if you’ve never studied any group theory. But I don’t know a simpler way to explain it! Perhaps there is a better way, and if you know of one, I’d love to hear about it in the comments. Nonetheless, this is a great example of a simple question that quickly leads into some very deep structure.

You may also wonder how on earth I know that the repetend length of 1/17303 is 726! No, I didn’t sit there and do long division; of course, I wrote a computer program. Perhaps I will post it soon.

Tags: , , , ,
Posted in group theory, number theory, pattern, primes | 4 Comments »

More on decimal expansions

Wednesday, January 21st, 2009

Today, I’d like to answer some of the questions I raised in the Decimal Expansion Zoo:

  1. Which decimal expansions terminate, and which are repeating—and how does it relate to the denominator?

    As we know, the decimal expansion of every rational number either terminates or repeats—but in a sense, they all repeat; the ones that “terminate” just happen to repeat the digit zero. That is, 0.25 is really just 0.25000000…. This should give us a clue that the “terminating” is not really a fundamental difference, but an artifact of the particular way we’ve chosen to represent numbers, in base 10. And indeed, as you can check, the fractions with terminating representations are those whose denominators are divisible only by 2 and 5 (since 2 and 5 are the divisors of 10). If we used, say, base 21 instead of base 10, the fractions with terminating representations would be the ones whose denominators are divisible by only 3 and 7, and so on.

  2. How are the different cycles for a given denominator related to each other, and why?

    If some fraction has a decimal expansion with a repeating portion like [abcde], then every cyclic rearrangement of [abcde] (that is, [bcdea], [cdeab], [deabc], and so on) also occurs as the expansion of some other fraction with the same denominator. To see why this is so is not hard if you think about the process of long division; the remainder at each step uniquely determines the next remainder, and so on, so given the same divisor, we are always going to see the exact same sequence of digits in the decimal expansion following a given remainder.

  3. How are the lengths of the cycles for a given denominator related to the denominator itself?

    As noted by Jonathan,

    The length of the repeating unit is less than or equal to one less than the denominator. That’s cool.

    Indeed! And understanding why this must be the case is not hard, again, if we think about the process of long division to produce the decimal expansion for some fraction. Suppose the fraction has denominator d. At each step of the long division, we must get a remainder less than d. If we ever get a remainder of zero, the expansion terminates. If we ever get a remainder that we’ve seen before, the expansion will begin to repeat. So, the longest an expansion can possibly go before repeating is (d-1).

    However, as noted by silverpie, there’s more:

    Not only is it always less than or equal to d-1; for prime denominators, it’s a divisor of d-1. (The quotient is equal to the number of different patterns–13, for example has 12/6 or two 6-digit patterns.)

    This is true! In fact, there’s even more that can be said about non-prime denominators, as well. However, unlike the previous observations, this one is extremely non-obvious. The only way I know how to prove it takes a detour through group theory. Perhaps I’ll write about it some day, but for now I’ll leave you to be amazed. =)

Tags: ,
Posted in number theory, pattern | 15 Comments »

Decimal expansion zoo

Tuesday, September 23rd, 2008

In a comment on a previous post about rational numbers and decimal expansions, Steve Gilberg noted:

I’ve been fascinated at how any multiple of 1/7 that’s not an integer repeats the same digits in decimal expression, only starting at different points in the sequence:

1/7 = .142857…
3/7 = .428571…
2/7 = .285714…
6/7 = .857142…
4/7 = .571428…
5/7 = .714285…

I’ve rearranged the order of the fractions to make the pattern obvious.

This is pretty cool indeed, and probably well-known to many. But there’s nothing particularly special about 7, other than the fact that it is small. In order to talk about the sorts of patterns we find in the expansions of rational numbers—and why—I’m going to start by having a special exhibit: the Decimal Expansion Zoo! Have a look around and see if you notice any patterns. I’ll follow the convention of enclosing repeating portions in [square brackets]. So, for example, 0.23[48] means 0.234848484848… and so on.

Some questions for you to think about while you wander about the zoo: what patterns do you notice? Which decimal expansions terminate, and which are repeating—and how does it relate to the denominator? How are the different cycles for a given denominator related to each other, and why? How are the lengths of the cycles for a given denominator related to the denominator itself? I’ll answer all these questions, and more, in an upcoming post!

1/2 = .5                              1/8 = .125
                                      3/8 = .375
1/3 = .[3]                            5/8 = .625
2/3 = .[6]                            7/8 = .875  

1/4 = .25                             1/9 = .[1]
3/4 = .75                             2/9 = .[2]
                                      3/9 = .[3]
1/5 = .2                              4/9 = .[4]
2/5 = .4                              5/9 = .[5]
3/5 = .6                              6/9 = .[6]
4/5 = .8                              7/9 = .[7]
                                      8/9 = .[8]
1/6 = .1[6]
5/6 = .8[3]                           1/10 = .1
                                      3/10 = .3
1/7 = .[142857]                       7/10 = .7
3/7 = .[428571]                       9/10 = .9
2/7 = .[285714]
6/7 = .[857142]                       1/12  = .08[3]
4/7 = .[571428]                       5/12  = .41[6]
5/7 = .[714285]                       7/12  = .58[3]
                                      11/12 = .91[6]
1/11  = .[09]
2/11  = .[18]                         1/13  = .[076923]
3/11  = .[27]                         10/13 = .[769230]
4/11  = .[36]                         9/13  = .[692307]
5/11  = .[45]                         12/13 = .[923076]
6/11  = .[54]                         3/13  = .[230769]
7/11  = .[63]                         4/13  = .[307692]
8/11  = .[72]                         2/13  = .[153846]
9/11  = .[81]                         7/13  = .[538461]
10/11 = .[90]                         5/13  = .[384615]
                                      11/13 = .[846153]
1/17  = .[0588235294117647]           6/13  = .[461538]
10/17 = .[5882352941176470]           8/13  = .[615384]
15/17 = .[8823529411764705]
14/17 = .[8235294117647058]           1/14  = .0[714285]
4/17  = .[2352941176470588]           3/14  = .2[142857]
6/17  = .[3529411764705882]           5/14  = .3[571428]
9/17  = .[5294117647058823]           9/14  = .6[428571]
5/17  = .[2941176470588235]           11/14 = .7[857142]
16/17 = .[9411764705882352]           13/14 = .9[285714]
7/17  = .[4117647058823529]
2/17  = .[1176470588235294]           1/15  = .0[6]
3/17  = .[1764705882352941]           2/15  = .1[3]
13/17 = .[7647058823529411]           4/15  = .2[6]
11/17 = .[6470588235294117]           7/15  = .4[6]
8/17  = .[4705882352941176]           8/15  = .5[3]
12/17 = .[7058823529411764]           11/15 = .7[3]
                                      13/15 = .8[6]
1/18  = .0[5]                         14/15 = .9[3]
5/18  = .2[7]
7/18  = .3[8]                         1/16  = .0625
11/18 = .6[1]                         3/16  = .1875
13/18 = .7[2]                         5/16  = .3125
17/18 = .9[4]                         7/16  = .4375
                                      9/16  = .5625
1/19  = .[052631578947368421]         11/16 = .6875
10/19 = .[526315789473684210]         13/16 = .8125
5/19  = .[263157894736842105]         15/16 = .9375
12/19 = .[631578947368421052]
6/19  = .[315789473684210526]         1/31  = .[032258064516129]
3/19  = .[157894736842105263]         10/31 = .[322580645161290]
11/19 = .[578947368421052631]         7/31  = .[225806451612903]
15/19 = .[789473684210526315]         8/31  = .[258064516129032]
17/19 = .[894736842105263157]         18/31 = .[580645161290322]
18/19 = .[947368421052631578]         25/31 = .[806451612903225]
9/19  = .[473684210526315789]         2/31  = .[064516129032258]
14/19 = .[736842105263157894]         20/31 = .[645161290322580]
7/19  = .[368421052631578947]         14/31 = .[451612903225806]
13/19 = .[684210526315789473]         16/31 = .[516129032258064]
16/19 = .[842105263157894736]         5/31  = .[161290322580645]
8/19  = .[421052631578947368]         19/31 = .[612903225806451]
4/19  = .[210526315789473684]         4/31  = .[129032258064516]
2/19  = .[105263157894736842]         9/31  = .[290322580645161]
                                      28/31 = .[903225806451612]
1/23  = .[0434782608695652173913]     3/31  = .[096774193548387]
10/23 = .[4347826086956521739130]     30/31 = .[967741935483870]
8/23  = .[3478260869565217391304]     21/31 = .[677419354838709]
11/23 = .[4782608695652173913043]     24/31 = .[774193548387096]
18/23 = .[7826086956521739130434]     23/31 = .[741935483870967]
19/23 = .[8260869565217391304347]     13/31 = .[419354838709677]
6/23  = .[2608695652173913043478]     6/31  = .[193548387096774]
14/23 = .[6086956521739130434782]     29/31 = .[935483870967741]
2/23  = .[0869565217391304347826]     11/31 = .[354838709677419]
20/23 = .[8695652173913043478260]     17/31 = .[548387096774193]
16/23 = .[6956521739130434782608]     15/31 = .[483870967741935]
22/23 = .[9565217391304347826086]     26/31 = .[838709677419354]
13/23 = .[5652173913043478260869]     12/31 = .[387096774193548]
15/23 = .[6521739130434782608695]     27/31 = .[870967741935483]
12/23 = .[5217391304347826086956]     22/31 = .[709677419354838]
5/23  = .[2173913043478260869565]
4/23  = .[1739130434782608695652]
17/23 = .[7391304347826086956521]
9/23  = .[3913043478260869565217]
21/23 = .[9130434782608695652173]
3/23  = .[1304347826086956521739]
7/23  = .[3043478260869565217391]

Tags: , ,
Posted in number theory, pattern | 14 Comments »

Rational numbers and decimal expansions

Sunday, September 7th, 2008

As you may remember from school, rational numbers have a terminating or eventually repeating (periodic) decimal expansion, whereas irrational numbers don’t. So, for example, 0.123123123123…, with 123 repeating forever, is rational (in fact, it is equal to 41/333), whereas something like 0.123456789101112131415…, which will never repeat, is irrational.

But do you know why this is true? (Despite what your teachers may have told you, the most important question in mathematics is not how, it is why!) Today I will show why every rational number has a terminating or eventually repeating decimal expansion, and in a future post I will show why every repeating or terminating decimal expansion represents a rational number. From these two pieces of information, of course, we can also deduce that every decimal expansion which doesn’t terminate or repeat must represent an irrational number, and vice versa.

(more…)

Tags: , ,
Posted in infinity, iteration, number theory, pattern | 9 Comments »