# [seqfan] Re: You wouldn't believe (fwd) A005178

David Wilson dwilson at gambitcomm.com
Wed Dec 24 00:12:50 CET 2008

```
I observed that A005178(n) is a linear recurrence, which implies that {
a(n) mod k } is eventually periodic (in this case, periodic) for any k.
You have observed the special case that { a(n) mod 100 } is periodic mod
30. But is this particular case specially noteworthy, given that a(n) is
periodic with respect to any modulus? E.g:

{ a(n) mod 1 } has period 1
{ a(n) mod 2 } has period 5
{ a(n) mod 3 } has period 10
{ a(n) mod 4 } has period 10
{ a(n) mod 5 } has period 3
{ a(n) mod 6 } has period 10
{ a(n) mod 7 } has period 12
{ a(n) mod 8 } has period 20
{ a(n) mod 9 } has period 30
{ a(n) mod 10} has period 15

The same is true of any linear recurrrence, e.g., the Fibonacci numbers
or the square numbers or the Pell numbers or the powers of 2 or the
audioactive numbers. They are all periodic with respect to any modulus.
The deep question is, how do you compute the period? Even the period of
{ 2^n mod k }, called the order of 2 mod k, is quite mysterious in some
respects.

Furthermore, many more general types of recurrences can be shown to be
eventually periodic with respect to any modulus. For example, the Fermat
numbers, Sylvester's sequence, and the factorial numbers have this
property as well.

Artur wrote:
> Dear David,
>
> All numbers A005178(n) mod 100 = A005178(n+30) mod 100
> (for every n)
>
>
> Best wishes
> ARTUR
>

```