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 

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.

Relevant Pages

  • Re: Mod 2011
    ... and work in the ring of integers modulo q. ... The sequence always starts: ... investigate whether square roots of -1 are in any way relevant. ... I don't see a pattern. ...
    (sci.math)
  • Re: Mod 2011
    ... and work in the ring of integers modulo q. ... The sequence always starts: ... What's the difference between primes in sequences and above? ... for those primes congruent 1 mod 3. ...
    (sci.math)
  • Re: Mod 2011
    ... and work in the ring of integers modulo q. ... The sequence always starts: ... What's the difference between primes in sequences and above? ... for those primes congruent 1 mod 3. ...
    (sci.math)
  • JSH: But why? Questioning primes.
    ... why would primes care what residue they have modulo ... then EVERY random sequence of two elements only can be ... then huge areas of funding in the math field collapse. ...
    (sci.physics)
  • Re: expansion of a rational number in base b: statistical properties
    ... >> I'm trying to find information on the statistical properties of the ... > All rational numbers' expansions, in any base, eventually become ... > that the length of the period divides (denominator/gcd(denominator, ... The elements of a set do not have any sequence. ...
    (sci.crypt)
Quantcast