[math-fun] Multiplying repeating decimals
I had assumed that if you multiply an eventually repeating decimal of period m and an eventually repeating decimal of period n, you get an eventually repeating decimal whose period is bounded by some polynomial function of m and n. But today I learned from Henry Cohn that that's not true: the period length can be exponentially large in m and n. More specifically, 1/(10^n-1) repeats with period n, but its square repeats with period 10^n-1 or thereabouts. I'm sure someone has written about the repeat-length for 1/(10^n-1)^2; can anyone provide a reference? Jim Propp
To make a short story long, what does "the period length *can be* exponentially large in n and m" mean? Maybe it means sup L(rs) over all r, s in Q with L(r) = m, (s) = n, is >= exp(Cm + Dn), where L(t) is the period of the repeating decimal of t in Q, for some C and D in R+. Is that it? --Dan On Sep 29, 2014, at 2:53 PM, James Propp <jamespropp@gmail.com> wrote:
I had assumed that if you multiply an eventually repeating decimal of period m and an eventually repeating decimal of period n, you get an eventually repeating decimal whose period is bounded by some polynomial function of m and n. But today I learned from Henry Cohn that that's not true: the period length can be exponentially large in m and n.
Arggh. There should have been an L before each of (r) and (s) as below, not just (r): On Sep 29, 2014, at 3:03 PM, Dan Asimov <dasimov@earthlink.net> wrote:
Maybe it means sup L(rs) over all r, s in Q with L(r) = m, L(s) = n, is >= exp(Cm + Dn), where L(t) is the period of the repeating decimal of t in Q, for some C and D in R+. Is that it?
I should have said "cannot be bounded by any subexponential function of m and n". Or perhaps I should have said "I had assumed that if you multiply two eventually repeating decimals of period less than or equal to n, you get an eventually repeating decimal whose period is bounded by some polynomial function of n." In fact, my intuition told me that there'd be a quadratic bound. Wrong! Jim On Mon, Sep 29, 2014 at 6:03 PM, Dan Asimov <dasimov@earthlink.net> wrote:
To make a short story long, what does "the period length *can be* exponentially large in n and m" mean?
Maybe it means sup L(rs) over all r, s in Q with L(r) = m, (s) = n, is >= exp(Cm + Dn), where L(t) is the period of the repeating decimal of t in Q, for some C and D in R+. Is that it?
--Dan
On Sep 29, 2014, at 2:53 PM, James Propp <jamespropp@gmail.com> wrote:
I had assumed that if you multiply an eventually repeating decimal of period m and an eventually repeating decimal of period n, you get an eventually repeating decimal whose period is bounded by some polynomial function of m and n. But today I learned from Henry Cohn that that's not true: the period length can be exponentially large in m and n.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Your intuition isn't completely off base. If the two periods M & N are relatively prime, then the product period should be a divisor of 9MN. This is because 10^M - 1 and 10^N - 1 both divide 10^MN - 1, and if gcd(M,N)=1, then gcd(10^M-1,10^N-1) is 9. The 9 in 9MN provides the required factor of 9, so that (10^M-1)*(10^N-1) divides 10^9MN - 1. This suggests the general period formula is (a divisor of) lcm(M,N) * (10^gcd(M,N) - 1). Rich ---- Quoting James Propp <jamespropp@gmail.com>:
I should have said "cannot be bounded by any subexponential function of m and n".
Or perhaps I should have said "I had assumed that if you multiply two eventually repeating decimals of period less than or equal to n, you get an eventually repeating decimal whose period is bounded by some polynomial function of n."
In fact, my intuition told me that there'd be a quadratic bound. Wrong!
Jim
On Mon, Sep 29, 2014 at 6:03 PM, Dan Asimov <dasimov@earthlink.net> wrote:
To make a short story long, what does "the period length *can be* exponentially large in n and m" mean?
Maybe it means sup L(rs) over all r, s in Q with L(r) = m, (s) = n, is >= exp(Cm + Dn), where L(t) is the period of the repeating decimal of t in Q, for some C and D in R+. Is that it?
--Dan
On Sep 29, 2014, at 2:53 PM, James Propp <jamespropp@gmail.com> wrote:
I had assumed that if you multiply an eventually repeating decimal of period m and an eventually repeating decimal of period n, you get an eventually repeating decimal whose period is bounded by some polynomial function of m and n. But today I learned from Henry Cohn that that's not true: the period length can be exponentially large in m and n.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Nice, Rich! Rich's observation is a perfect embodiment of one of my principles of teaching: When a student gets a wrong answer, see if there's a way to view it as the right answer to a different question, and if you find one, share it with the whole class. Jim On Tue, Sep 30, 2014 at 3:38 PM, <rcs@xmission.com> wrote:
Your intuition isn't completely off base.
If the two periods M & N are relatively prime, then the product period should be a divisor of 9MN. This is because 10^M - 1 and 10^N - 1 both divide 10^MN - 1, and if gcd(M,N)=1, then gcd(10^M-1,10^N-1) is 9. The 9 in 9MN provides the required factor of 9, so that (10^M-1)*(10^N-1) divides 10^9MN - 1.
This suggests the general period formula is (a divisor of)
lcm(M,N) * (10^gcd(M,N) - 1).
Rich
----
Quoting James Propp <jamespropp@gmail.com>:
I should have said "cannot be bounded by any subexponential function of m
and n".
Or perhaps I should have said "I had assumed that if you multiply two eventually repeating decimals of period less than or equal to n, you get an eventually repeating decimal whose period is bounded by some polynomial function of n."
In fact, my intuition told me that there'd be a quadratic bound. Wrong!
Jim
On Mon, Sep 29, 2014 at 6:03 PM, Dan Asimov <dasimov@earthlink.net> wrote:
To make a short story long, what does "the period length *can be*
exponentially large in n and m" mean?
Maybe it means sup L(rs) over all r, s in Q with L(r) = m, (s) = n, is >= exp(Cm + Dn), where L(t) is the period of the repeating decimal of t in Q, for some C and D in R+. Is that it?
--Dan
On Sep 29, 2014, at 2:53 PM, James Propp <jamespropp@gmail.com> wrote:
I had assumed that if you multiply an eventually repeating decimal of period m and an eventually repeating decimal of period n, you get an eventually repeating decimal whose period is bounded by some polynomial function of m and n. But today I learned from Henry Cohn that that's not true: the period length can be exponentially large in m and n.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
"JP" == James Propp <jamespropp@gmail.com> writes:
JP> More specifically, 1/(10^n-1) repeats with period n, but its square JP> repeats with period 10^n-1 or thereabouts. If one looks at it as base b=10^n, where any integer divided by b-1 repeats in base b with a cycle 1 base b "digit" long, then since the square of b-1 is b²-2b+1, one needs to find the smallest b' such that b' is 10^m, m>n and b'-1 is an integer multiple of b²-2b+1. (Or, put another way, b²-2b+1 is a factor of b'-1.) The length of the decimal cycle is then m. That gives k·(10ⁿ-1)²/(10ⁿ) = 10^l, where k,l are in Z+, and n+l as a funtion of n is the question. It has been long engough, that I forget how to attack that style of equation. -JimC -- James Cloos <cloos@jhcloos.com> OpenPGP: 0x997A9F17ED7DAEA6
Let m be a positive integer relatively prime to 10. Then the period length of 1/m is the multiplicative order of 10 modulo m -- i.e. we look in the group (Z/mZ)*. Note that if p is an odd prime, that even though the multiplicative,a =order of 10 mod p might be small, the multiplicative order of 10 mod p^2 is overwhelmingly likely to be p*a (except when we have something like a Wieferich prime). If m,n are relatively prime, then by the Chinese remainder theorem the multiplicative order of 10 mod mn is the lcm of the multiplicative orders of 10 mod each of m and n. Victor On Mon, Sep 29, 2014 at 5:53 PM, James Propp <jamespropp@gmail.com> wrote:
I had assumed that if you multiply an eventually repeating decimal of period m and an eventually repeating decimal of period n, you get an eventually repeating decimal whose period is bounded by some polynomial function of m and n. But today I learned from Henry Cohn that that's not true: the period length can be exponentially large in m and n. More specifically, 1/(10^n-1) repeats with period n, but its square repeats with period 10^n-1 or thereabouts.
I'm sure someone has written about the repeat-length for 1/(10^n-1)^2; can anyone provide a reference?
Jim Propp _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (5)
-
Dan Asimov -
James Cloos -
James Propp -
rcs＠xmission.com -
Victor Miller