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

Paolo Lava ppl at spl.at
Fri Dec 26 10:51:54 CET 2008

```Hello to seqfans.

Another consideration. I have studied a little the sequences a(n)=(n^k mod r). If we fix the value for “r” and let “k” to assume the values 1, 2, 3, 4, 5 …. the sequences we obtain repeat themselves according to the following table.
Here period means that [n^k mod r = n^(k+period) mod r] while anti-period shows how many initial “k” we have to take away before the periodicity starts.

“r”            period       anti-period
1		1		0
2 		1		0
3		2		0
4		2		1
5		4		0
6		2		0
7		6		0
8		2		2
9		6		1
10		4		0
11		10		0
12		2		1
13		12		0
14		6		0
15		4		0
16		4		3
17		16		0
18		6		1
19		18		0
20		4		1

Obviously if “r” is prime the period is equal “r-1” (anti-period=0).
The sequence of the periods is A002322 while the sequence of the anti-periods is A066301.

Best wishes

Paolo

--- dwilson at gambitcomm.com wrote:

From: David Wilson <dwilson at gambitcomm.com>
To: Sequence Fanatics <seqfan at list.seqfan.eu>
Subject: [seqfan] Re: You wouldn't believe (fwd) A005178
Date: Tue, 23 Dec 2008 18:12:50 -0500

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
etc. ad infinitum.

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
>

_______________________________________________

Seqfan Mailing list - http://list.seqfan.eu/

_____________________________________________________________
Sign up for a 6mb FREE email from
http://www.spl.at
Take a look at our new message boards!
http://chat.spl.at
```

More information about the SeqFan mailing list