Re: Length of repeating series of digits in rational numbers

johngross wrote:
On Dec 15, 9:50 am, "Ignacio Larrosa Cañestro"
<ilarrosaQUITARMAYUSCU...@xxxxxxxxxxx> wrote:
johngross wrote:
On Dec 15, 8:21 am, "Ignacio Larrosa Cañestro"
<ilarrosaQUITARMAYUSCU...@xxxxxxxxxxx> wrote:
johngross wrote:
Hi all,

Given two integers i,j expressed to an arbitrary radix r;

Is it possible to calculate the length of the repeating digits of
the rational fraction i/j? in advance? without having to actually
work through it until the digits start repeating?

If so, I would very much like to know how.

Thanks in advance.

johngross

The length is the orden k of r mod j. I.e., k is the minimun
exponet as r^k = 1 (mod j). This is a divisor of phi(j), the euler
totient function that says how many numbers less than j are
relative primes to j.

--
Best regards,

Ignacio Larrosa Cañestro
A Coruña (España)
ilarrosaQUITARMAYUSCU...@xxxxxxxxxxx

Hi Ignacio,

Thanks for your very quick response, but I must confess you have
baffled me.

Is 'orden' a specific methematical term, or do you mean 'order'?

I mean order, "orden" is order in spanish.

Could you possibly give me an example, say for

length (256/60 base 5) = ?

Well, I was thinking in r an j coprimes. If they aren't, we must
consider the coprime part j' of j with respect to r.

In our example, 256/60 = 64/15. As j = 15 = 3*5, then j' = 3

Then, the length of the period is k = order(5, 3) = 2, becasuse 5^1
= 2 (mod 3) and 5^2 = 1 (mod 3). Then the order of 5 mod 3 is 2.

The length of the periodic part is then 2. Of course, it could be an
aperiodic part, debt to the presence of commons factors of j and r..

Actually, "{n}" means "expressed in base n",

64/15 {10} = 4 + 4/15 {10} = 4 + (4/5)/3 {10}

= 4 + (4/5)/3 {5} = 4 + 0.4/3 {5}

= 4.1131313... {5}

--
Best regards,

Ignacio Larrosa Cañestro
A Coruña (España)
ilarrosaQUITARMAYUSCU...@xxxxxxxxxxxx Hide quoted text -

- Show quoted text -

Hi once more,

I think I'm getting the idea, but what do I do when I have no coprimes
between j and r?

I am currently trying

17/420 {17} which seems to give me a period of 12 repeating digits


Yes, gcd(420, 17) = 1 and order(420, 17) = 12, because 420^12 = 1 (mod 17),
and 12 is the minimum exponent verifying that. As gcd(420, 17) = 1, the
period begin just at decimal point. To find the decimal expansion, I don't
see any trick in that case; you must make the long division in radix 17 ...

I will writr phi(n) for Euler totient function. Note that 420 = 2^2*3*5*7,
then

phi(420) = phi(2^2)phi(3)phi(5)phi(7) = (2^2 - 2^1)*2*4*6 = 192

a multiple of 12.

and

17/196 {17} for which I haven't been able to detect a period of
repeating digits (at least, to the precision to which I can trust the
Windows calculator to be accurate).

gcd(196, 17) = 1, order (17, 196) = 42

It is high, but it coul be higher:

phi(196) = phi(2^2*7^2) = (2^2 - 2^1)(7^2 - 7^1) = 2*42 = 84

Newly, I don't see eny trick to calculate the expansion.

Well, I did assume that the fractions were write in radix 10, althought you
are interesting in the period in radix 17.


Sorry to bother you again, and thanks for your help so far.

It isn't matter. Best regards,

Ignacio Larrosa Cañestro
A Coruña (España)
ilarrosaQUITARMAYUSCULAS@xxxxxxxxxxx



.

Relevant Pages

  • Re: Length of repeating series of digits in rational numbers
    ... through it until the digits start repeating? ... Thanks for your very quick response, but I must confess you have ...
    (sci.math)
  • Re: Fractions: 1/7 and others like it
    ... six digits repeat in the same order. ... Find all sets of fractions less ... It's all the ones where 1/n has a repeating decimal of period n-1, ... Pre-computers, William Shanks computed k for all primes less than 120000, and in ...
    (rec.puzzles)
  • Re: just 5 quick answers then I can summarise and GO
    ... repeating groups of digits. ... The question is, maybe, what is the longest string of digits in pi (or ... infinite number of times. ...
    (sci.logic)
  • Re: Length of repeating series of digits in rational numbers
    ... Best regards, ... I was thinking in r an j coprimes. ... 17/420 which seems to give me a period of 12 repeating digits ...
    (sci.math)
  • Re: String Pattern Matching algo
    ... the length the repeating string. ... After reporting I., computing k and reporting the k digits and the opening brace, now showing I.b(, you know that the repeating string is at most n characters. ... The two buufer approach may well win on speed; the one buffer approach on space. ...
    (comp.lang.c)