A072123 Remainder when Fibonacci(n) is divided by prime(n).

1, 1, 2, 3, 5, 8, 13, 2, 11, 26, 27, 33, 28, 33, 46, 33, 4, 22, 27, 20, 69, 15, 22, 88, 44, 92, 100, 21, 76, 21, 69, 41, 116, 134, 44, 76, 70, 117, 80, 157, 129, 87, 73, 27, 157, 1, 5, 208, 27, 108, 1, 203, 230, 19, 112, 143, 206, 258, 31, 3, 146, 266, 117, 213, 211, 168

Offset: 1

Author

Randy L. Ekl, Jun 20 2002

Keywords

• easy
• nonn

Comments

For k=0..8, a(10^k) = 1, 26, 55, 5965, 99584, 728618, 2256590, 61329731, 1081853265. - Zak Seidov, Dec 23 2014

Examples

			a(8) = F(8) mod prime(8) = 21 mod 19 = 2.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..10000 (first 1000 terms from Zak Seidov)

Crossrefs

Cf. A000040, A000045, A075702 (locations of 0 in this sequence), A121104.

Programs

Magma

[Fibonacci(n) mod NthPrime(n): n in [1..120]]; // Vincenzo Librandi, Nov 19 2015

Maple

seq(combinat[fibonacci](n) mod ithprime(n), n=1..1000); # Robert Israel, Dec 24 2014

Mathematica

Table[Mod[Fibonacci[n],Prime[n]],{n,70}] (* Harvey P. Dale, Jan 25 2011 *)

PARI

fibmod(n, m)=((Mod([1, 1; 1, 0], m))^n)[1, 2]
a(n)=lift(fibmod(n,prime(n))) \\ Charles R Greathouse IV, Jun 19 2017

Formula

a(n) = F(n) mod prime(n), where F(n) is the n-th Fibonacci number and prime(n) is the n-th prime number.