Re: How to know the maximum of digit a number can get before his cycle repeat?
From: David Wagner (daw_at_taverner.cs.berkeley.edu)
Date: 12/10/04
- Next message: ondrej.mikle_at_gmail.com: "Re: first question"
- Previous message: Mok-Kong Shen: "Re: [OT] Linked list fixup [was: Fast DES IP]"
- In reply to: John Savard: "Re: How to know the maximum of digit a number can get before his cycle repeat?"
- Next in thread: Raymond H.: "Re: How to know the maximum of digit a number can get before his cycle repeat?"
- Reply: Raymond H.: "Re: How to know the maximum of digit a number can get before his cycle repeat?"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Date: Fri, 10 Dec 2004 16:58:33 +0000 (UTC)
John Savard wrote:
>[...] a base-10 shift register [...]
>I am not certain, but I believe that the period of chain addition has to
>be either 99 or some factor of 99, such as 3, 9, or 11.
Hmm. I'm thinking it has to be a factor of 60.
Here is my reasoning. I'm using the Chinese remainder theorem.
Modulo 2, the period divides 3, and in fact, the sequence is
either 0000... or 011011011... or some rotation thereof.
Modulo 5, the period divides 20, and in fact, the sequence is
either 0000..., 13421342..., 0112303314044320224101123..., or some
rotation thereof. The reason that the sequence is not full-length
(i.e., period 20) is that x^2 - x - 1 is not irreducible over Z/5Z;
in fact, x^2 - x - 1 = (x-3)^2 modulo 5.
Consequently, the period modulo 10 has to be a divisor of
lcm(3,20) = 60.
- Next message: ondrej.mikle_at_gmail.com: "Re: first question"
- Previous message: Mok-Kong Shen: "Re: [OT] Linked list fixup [was: Fast DES IP]"
- In reply to: John Savard: "Re: How to know the maximum of digit a number can get before his cycle repeat?"
- Next in thread: Raymond H.: "Re: How to know the maximum of digit a number can get before his cycle repeat?"
- Reply: Raymond H.: "Re: How to know the maximum of digit a number can get before his cycle repeat?"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Relevant Pages
|
