-
Notifications
You must be signed in to change notification settings - Fork 0
/
Pisano_Period.js
43 lines (33 loc) · 1.45 KB
/
Pisano_Period.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
// ---------------------------------Descripton-----------------------------------------
// The Fibonacci numbers are the numbers in the integer sequence:
// 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, ...
// Defined by the recurrence relation
// Fib(0) = 0
// Fib(1) = 1
// Fib(2) = 1
// Fib(i) = Fib(i-1) + Fib(i-2)
// For any integer n, the sequence of Fibonacci numbers Fib(i) taken modulo n is periodic. The Pisano period, denoted Pisano(n), is the length of the period of this sequence.
// For example, the sequence of Fibonacci numbers modulo 3 begins:
// 0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, 2, 2, 1, ...
// This sequence has period 8. The repeating patter is 0, 1, 1, 2, 0, 2, 2, 1 So Pisano(3) = 8
// Your task is to write the Pisano function that takes an integer n and outputs the length of pisano period.
// ------------------------------------------------------------------------------------
const pisano = (n) => {
let previous = 0;
let current = 1;
let period = 0;
for (let i = 0; i < n * n; i++) {
let temp = (previous + current) % n;
previous = current;
current = temp;
period++;
if (previous === 0 && current === 1) {
return period;
}
}
}
// Example usage:
console.log(pisano(3)); // Output: 8
console.log(pisano(4)); // Output: 6
console.log(pisano(5)); // Output: 20
console.log(pisano(6)); // Output: 24