Rosetta Code

Pisano period: Difference between revisions

Page Discussion

Pisano period (view source)

Revision as of 19:19, 9 March 2024

69,420 bytes added ,  2 months ago
m
→‎{{header|EasyLang}}
(44 intermediate revisions by 16 users not shown)
Line 1:
{{task|Prime Numbers}}
{{draft task}}[[Category:Mathematics]]
[[Category:Mathematics]]
 
The [[wp:Fibonacci_Number|Fibonacci sequence]] taken modulo 2 is a periodic sequence of period 3 : 0, 1, 1, 0, 1, 1, ...
 
Line 6 ⟶ 8:
Prime numbers are straightforward; the Pisano period of a prime number '''p''' is simply: '''pisano(p)'''. The Pisano period of a composite number '''c''' may be found in different ways. It may be calculated directly: '''pisano(c)''', which works, but may be time consuming to find, especially for larger integers, or, it may be calculated by finding the [[wp:Least common multiple|least common multiple]] of the Pisano periods of each composite component.
 
E.G. Given a Pisano period function: pisano(x), and a least common multiple function lcm(x, y):
 
;E.G.:
'''pisano(m × n)''' is equivalent to '''lcm(pisano(m), pisano(n))''' where '''m''' and '''n''' are '''[[wp:Coprime|coprime]]'''
Given a Pisano period function: pisano(x), and a least common multiple function lcm(x, y):
 
<big>'''pisano(m × n)''' is equivalent to '''lcm(pisano(m), pisano(n))''' where '''m''' and '''n''' are '''[[wp:Coprime|coprime]]'''</big>
A formulae to calculate the pisano period for integer powers k of prime numbers p
A formulae to calculate the pisano period for integer powers &nbsp; '''k''' &nbsp; of prime numbers &nbsp; '''p''' &nbsp; is:
is:
<big>'''pisano(p<sup>k</sup>) == p<sup>(k-1)</sup>pisano(p)''' </big>
 
'''pisano(p<sup>k</sup>) == p<sup>(k-1)</sup>pisano(p)'''
The equation is conjectured, no exceptions have been seen.
 
If a positive integer &nbsp; '''i''' &nbsp; is split into its prime factors, &nbsp; then the second and first equations above can be applied to generate the pisano period.
 
 
;Task
Line 24:
pisanoPrime(p,k) should return the Pisano period of p<sup>k</sup> where p is prime and k is a positive integer.
 
pisano(m) should use pisanoPrime to return the Pisano period of m where m is a primepositive integer.
 
Print pisanoPrime(p,2) for every prime lower than 15.
Line 31:
 
Print pisano(m) for every integer from 1 to 180.
 
;Related tasks
Line 36 ⟶ 37:
* &nbsp;[[Prime decomposition]]
* &nbsp;[[Least common multiple]]
<br><br>
 
=={{header|11l}}==
{{trans|Nim}}
 
<syntaxhighlight lang="11l">F lcm(m, n)
R m I/ gcd(m, n) * n
 
F get_primes(=n)
[Int] r
L(d) 2 .. n
V q = n I/ d
V m = n % d
L m == 0
r.append(d)
n = q
q = n I/ d
m = n % d
R r
 
F is_prime(a)
I a == 2
R 1B
I a < 2 | a % 2 == 0
R 0B
L(i) (3 .. Int(sqrt(a))).step(2)
I a % i == 0
R 0B
R 1B
 
F pisano_period(m)
V p = 0
V c = 1
L(i) 0 .< m * m
p = (p + c) % m
swap(&p, &c)
I p == 0 & c == 1
R i + 1
R 1
 
F pisano_prime(p, k)
R I is_prime(p) {p ^ (k - 1) * pisano_period(p)} E 0
 
F pisano(m)
V primes = get_primes(m)
DefaultDict[Int, Int] prime_powers
L(p) primes
prime_powers[p]++
[Int] pps
L(k, v) prime_powers
pps.append(pisano_prime(k, v))
I pps.empty
R 1
V result = pps[0]
L(i) 1 .< pps.len
result = lcm(result, pps[i])
R result
 
L(p) 2..14
V pp = pisano_prime(p, 2)
I pp > 0
print(‘pisano_prime(#2, 2) = #.’.format(p, pp))
 
print()
L(p) 2..179
V pp = pisano_prime(p, 1)
I pp > 0
print(‘pisano_prime(#3, 1) = #.’.format(p, pp))
 
print()
print(‘pisano(n) for integers 'n' from 1 to 180 are:’)
L(n) 1..180
print(‘#3’.format(pisano(n)), end' I n % 15 == 0 {"\n"} E ‘ ’)</syntaxhighlight>
 
{{out}}
<pre>
pisano_prime( 2, 2) = 6
pisano_prime( 3, 2) = 24
pisano_prime( 5, 2) = 100
pisano_prime( 7, 2) = 112
pisano_prime(11, 2) = 110
pisano_prime(13, 2) = 364
 
pisano_prime( 2, 1) = 3
pisano_prime( 3, 1) = 8
pisano_prime( 5, 1) = 20
pisano_prime( 7, 1) = 16
pisano_prime( 11, 1) = 10
pisano_prime( 13, 1) = 28
pisano_prime( 17, 1) = 36
pisano_prime( 19, 1) = 18
pisano_prime( 23, 1) = 48
pisano_prime( 29, 1) = 14
pisano_prime( 31, 1) = 30
pisano_prime( 37, 1) = 76
pisano_prime( 41, 1) = 40
pisano_prime( 43, 1) = 88
pisano_prime( 47, 1) = 32
pisano_prime( 53, 1) = 108
pisano_prime( 59, 1) = 58
pisano_prime( 61, 1) = 60
pisano_prime( 67, 1) = 136
pisano_prime( 71, 1) = 70
pisano_prime( 73, 1) = 148
pisano_prime( 79, 1) = 78
pisano_prime( 83, 1) = 168
pisano_prime( 89, 1) = 44
pisano_prime( 97, 1) = 196
pisano_prime(101, 1) = 50
pisano_prime(103, 1) = 208
pisano_prime(107, 1) = 72
pisano_prime(109, 1) = 108
pisano_prime(113, 1) = 76
pisano_prime(127, 1) = 256
pisano_prime(131, 1) = 130
pisano_prime(137, 1) = 276
pisano_prime(139, 1) = 46
pisano_prime(149, 1) = 148
pisano_prime(151, 1) = 50
pisano_prime(157, 1) = 316
pisano_prime(163, 1) = 328
pisano_prime(167, 1) = 336
pisano_prime(173, 1) = 348
pisano_prime(179, 1) = 178
 
pisano(n) for integers 'n' from 1 to 180 are:
1 3 8 6 20 24 16 12 24 60 10 24 28 48 40
24 36 24 18 60 16 30 48 24 100 84 72 48 14 120
30 48 40 36 80 24 76 18 56 60 40 48 88 30 120
48 32 24 112 300 72 84 108 72 20 48 72 42 58 120
60 30 48 96 140 120 136 36 48 240 70 24 148 228 200
18 80 168 78 120 216 120 168 48 180 264 56 60 44 120
112 48 120 96 180 48 196 336 120 300 50 72 208 84 80
108 72 72 108 60 152 48 76 72 240 42 168 174 144 120
110 60 40 30 500 48 256 192 88 420 130 120 144 408 360
36 276 48 46 240 32 210 140 24 140 444 112 228 148 600
50 36 72 240 60 168 316 78 216 240 48 216 328 120 40
168 336 48 364 180 72 264 348 168 400 120 232 132 178 120
</pre>
 
=={{header|ALGOL 68}}==
The pisano procedure is based on the Go sample.
<syntaxhighlight lang="algol68">
BEGIN # find the Pisano period of some primes and composites #
 
INT max number = 180; # maximum number we will consider #
# sieve the primes to max number #
[ 1 : max number ]BOOL is prime; FOR i TO UPB is prime DO is prime[ i ] := ODD i OD;
is prime[ 1 ] := FALSE;
is prime[ 2 ] := TRUE;
FOR s FROM 3 BY 2 TO ENTIER sqrt( max number ) DO
IF is prime[ s ] THEN
FOR p FROM s * s BY s TO UPB is prime DO is prime[ p ] := FALSE OD
FI
OD;
 
# returns the Pisano period of m #
PROC pisano = ( INT m )INT:
BEGIN
INT p := 0;
INT c := 1;
INT r := 0;
FOR i FROM 0 TO m * m WHILE r = 0 DO
INT t = p;
p := c;
c := ( t + c ) MOD m;
IF p = 0 AND c = 1 THEN r := i + 1 FI
OD;
IF r = 0 THEN 1 ELSE r FI
END # pisano # ;
 
# returns the Pisano period of p^k or 0 if p is not prime or k < 1 #
PROC pisano prime = ( INT p, k )INT:
IF NOT is prime[ p ] OR k < 1 THEN 0 ELSE p ^ ( k - 1 ) * pisano( p ) FI;
 
print( ( "Pisano period of p^2 where p is a prime < 15:", newline ) );
FOR p TO 15 DO
IF is prime[ p ] THEN print( ( " ", whole( p, 0 ), ":", whole( pisano prime( p, 2 ), 0 ) ) ) FI
OD;
print( ( newline ) );
print( ( "Pisano period of primes up to 180, non-primes shown as ""*"":", newline ) );
FOR p TO 180 DO
IF NOT is prime[ p ]
THEN print( ( " *" ) )
ELSE print( ( whole( pisano prime( p, 1 ), -4 ) ) )
FI;
IF p MOD 10 = 0 THEN print( ( newline ) ) FI
OD;
print( ( newline ) );
print( ( "Pisano period of positive integers up to 180:", newline ) );
FOR n TO 180 DO
print( ( whole( pisano( n ), -4 ) ) );
IF n MOD 10 = 0 THEN print( ( newline ) ) FI
OD
 
END
</syntaxhighlight>
{{out}}
<pre>
Pisano period of p^2 where p is a prime < 15:
2:6 3:24 5:100 7:112 11:110 13:364
Pisano period of primes up to 180, non-primes shown as "*":
* 3 8 * 20 * 16 * * *
10 * 28 * * * 36 * 18 *
* * 48 * * * * * 14 *
30 * * * * * 76 * * *
40 * 88 * * * 32 * * *
* * 108 * * * * * 58 *
60 * * * * * 136 * * *
70 * 148 * * * * * 78 *
* * 168 * * * * * 44 *
* * * * * * 196 * * *
50 * 208 * * * 72 * 108 *
* * 76 * * * * * * *
* * * * * * 256 * * *
130 * * * * * 276 * 46 *
* * * * * * * * 148 *
50 * * * * * 316 * * *
* * 328 * * * 336 * * *
* * 348 * * * * * 178 *
 
Pisano period of positive integers up to 180:
1 3 8 6 20 24 16 12 24 60
10 24 28 48 40 24 36 24 18 60
16 30 48 24 100 84 72 48 14 120
30 48 40 36 80 24 76 18 56 60
40 48 88 30 120 48 32 24 112 300
72 84 108 72 20 48 72 42 58 120
60 30 48 96 140 120 136 36 48 240
70 24 148 228 200 18 80 168 78 120
216 120 168 48 180 264 56 60 44 120
112 48 120 96 180 48 196 336 120 300
50 72 208 84 80 108 72 72 108 60
152 48 76 72 240 42 168 174 144 120
110 60 40 30 500 48 256 192 88 420
130 120 144 408 360 36 276 48 46 240
32 210 140 24 140 444 112 228 148 600
50 36 72 240 60 168 316 78 216 240
48 216 328 120 40 168 336 48 364 180
72 264 348 168 400 120 232 132 178 120
</pre>
 
=={{header|C++}}==
<syntaxhighlight lang="c++">#include <functional>
#include <iostream>
#include <iomanip>
#include <numeric>
#include <vector>
using namespace std;
 
template<typename T>
pair<unsigned, unsigned> floyd(function<T(T)> f, T x0) {
// Floyd's cycle detection algorithm.
auto tortoise = f(x0);
auto hare = f(f(x0));
while (tortoise != hare) {
tortoise = f(tortoise);
hare = f(f(hare));
}
 
// Find the position μ of first repetition.
unsigned mu = 0;
tortoise = x0;
while (tortoise != hare) {
tortoise = f(tortoise);
hare = f(hare);
mu += 1;
}
// Find the length of the shortest cycle starting from x_μ
unsigned lam = 1;
hare = f(tortoise);
while (tortoise != hare) {
hare = f(hare);
lam += 1;
}
return make_pair(lam, mu);
}
 
unsigned pisano_period(unsigned p) {
if (p < 2) return 1;
function<pair<unsigned, unsigned>(pair<unsigned, unsigned>)> f = [&](auto xy) {
return make_pair(xy.second, (xy.first + xy.second) % p);
};
return floyd(f, make_pair(0u, 1u)).first;
}
 
 
bool is_prime(unsigned p) {
if (p < 2) return false;
if (0 == p % 2) return 2 == p;
if (0 == p % 3) return 3 == p;
unsigned d = 5;
while (d * d <= p) {
if (0 == p % d) return false;
d += 2;
if (0 == p % d) return false;
d += 4;
}
return true;
}
 
vector<pair<unsigned, unsigned>> factor(unsigned n) {
vector<pair<unsigned, unsigned>> ans;
if (n < 2) return ans;
auto work = [&](unsigned p) {
if (0 == n % p) {
unsigned k = 1;
n /= p;
while (0 == n % p) {
k += 1;
n /= p;
}
ans.emplace_back(p, k);
}
};
work(2);
work(3);
unsigned d = 5;
while (d <= n) {
work(d);
d += 2;
work(d);
d += 4;
}
return ans;
}
 
long long ipow(long long p, unsigned k) {
long long ans = 1;
while (0 != k) {
if (0 != k % 2) ans *= p;
k /= 2;
p *= p;
}
return ans;
}
 
unsigned pisano_prime(unsigned p, unsigned k) {
if (!is_prime(p) || k == 0) {
return 0;
}
return ipow(p, k - 1) * pisano_period(p);
}
unsigned pisano(unsigned n) {
auto prime_powers{factor(n)};
unsigned ans = 1;
for (auto [p, k]: prime_powers) {
if (1 < ans) {
ans = lcm(ans, pisano_prime(p, k));
} else {
ans = pisano_prime(p, k);
}
}
return ans;
}
int main() {
for (unsigned p = 2; p < 15; ++p) {
auto pp = pisano_prime(p, 2);
if (0 < pp) {
cout << "pisanoPrime(" << setw(2) << p << ": 2) = " << pp << endl;
}
}
cout << endl;
for (unsigned p = 2; p < 180; ++p) {
auto pp = pisano_prime(p, 1);
if (0 < pp) {
cout << "pisanoPrime(" << setw(3) << p << ": 1) = " << pp << endl;
}
}
cout << endl;
cout << "pisano(n) for integers 'n' from 1 to 180 are:" << endl;
for (unsigned n = 1; n <= 180; ++n) {
cout << setw(3) << pisano(n) << " ";
if (0 == n % 15) {
cout << endl;
}
}
return 0;
}</syntaxhighlight>
{{out}}
<pre>pisanoPrime( 2: 2) = 6
pisanoPrime( 3: 2) = 24
pisanoPrime( 5: 2) = 100
pisanoPrime( 7: 2) = 112
pisanoPrime(11: 2) = 110
pisanoPrime(13: 2) = 364
 
pisanoPrime( 2: 1) = 3
pisanoPrime( 3: 1) = 8
pisanoPrime( 5: 1) = 20
pisanoPrime( 7: 1) = 16
pisanoPrime( 11: 1) = 10
pisanoPrime( 13: 1) = 28
pisanoPrime( 17: 1) = 36
pisanoPrime( 19: 1) = 18
pisanoPrime( 23: 1) = 48
pisanoPrime( 29: 1) = 14
pisanoPrime( 31: 1) = 30
pisanoPrime( 37: 1) = 76
pisanoPrime( 41: 1) = 40
pisanoPrime( 43: 1) = 88
pisanoPrime( 47: 1) = 32
pisanoPrime( 53: 1) = 108
pisanoPrime( 59: 1) = 58
pisanoPrime( 61: 1) = 60
pisanoPrime( 67: 1) = 136
pisanoPrime( 71: 1) = 70
pisanoPrime( 73: 1) = 148
pisanoPrime( 79: 1) = 78
pisanoPrime( 83: 1) = 168
pisanoPrime( 89: 1) = 44
pisanoPrime( 97: 1) = 196
pisanoPrime(101: 1) = 50
pisanoPrime(103: 1) = 208
pisanoPrime(107: 1) = 72
pisanoPrime(109: 1) = 108
pisanoPrime(113: 1) = 76
pisanoPrime(127: 1) = 256
pisanoPrime(131: 1) = 130
pisanoPrime(137: 1) = 276
pisanoPrime(139: 1) = 46
pisanoPrime(149: 1) = 148
pisanoPrime(151: 1) = 50
pisanoPrime(157: 1) = 316
pisanoPrime(163: 1) = 328
pisanoPrime(167: 1) = 336
pisanoPrime(173: 1) = 348
pisanoPrime(179: 1) = 178
 
pisano(n) for integers 'n' from 1 to 180 are:
1 3 8 6 20 24 16 12 24 60 10 24 28 48 40
24 36 24 18 60 16 30 48 24 100 84 72 48 14 120
30 48 40 36 80 24 76 18 56 60 40 48 88 30 120
48 32 24 112 300 72 84 108 72 20 48 72 42 58 120
60 30 48 96 140 120 136 36 48 240 70 24 148 228 200
18 80 168 78 120 216 120 168 48 180 264 56 60 44 120
112 48 120 96 180 48 196 336 120 300 50 72 208 84 80
108 72 72 108 60 152 48 76 72 240 42 168 174 144 120
110 60 40 30 500 48 256 192 88 420 130 120 144 408 360
36 276 48 46 240 32 210 140 24 140 444 112 228 148 600
50 36 72 240 60 168 316 78 216 240 48 216 328 120 40
168 336 48 364 180 72 264 348 168 400 120 232 132 178 120</pre>
=={{header|EasyLang}}==
{{trans|Go}}
<syntaxhighlight>
fastfunc isprim num .
if num mod 2 = 0
if num = 2
return 1
.
return 0
.
if num mod 3 = 0
if num = 3
return 1
.
return 0
.
i = 5
while i <= sqrt num
if num mod i = 0
return 0
.
i += 2
if num mod i = 0
return 0
.
i += 4
.
return 1
.
func gcd a b .
if b = 0
return a
.
return gcd b (a mod b)
.
func lcm a b .
return a / gcd a b * b
.
func ipow x p .
prod = 1
while p > 0
if p mod 2 = 1
prod *= x
.
p = p div 2
x *= x
.
return prod
.
proc getprims n . prims[] .
prims[] = [ ]
for i = 2 to n
d = n / i
m = n mod i
if m = 0
prims[] &= i
cnt = 0
while m = 0
cnt += 1
n = d
d = n div i
m = n mod i
.
prims[] &= cnt
.
.
.
func pisanoPeriod m .
c = 1
for i = 1 to m * m
swap p c
c = (p + c) mod m
if p = 0 and c = 1
return i
.
.
return 1
.
func pisanoPrime p k .
if isprim p = 0 or k = 0
return 0
.
return ipow p (k - 1) * pisanoPeriod p
.
func pisano m .
getprims m p[]
for i = 1 step 2 to len p[] - 1
pps[] &= pisanoPrime p[i] p[i + 1]
.
if len pps[] = 0
return 1
.
if len pps[] = 1
return pps[1]
.
f = pps[1]
for i = 2 to len pps[]
f = lcm f pps[i]
.
return f
.
proc main . .
for p = 2 to 14
pp = pisanoPrime p 2
if pp > 0
print "pisanoPrime(" & p & ": 2) = " & pp
.
.
print ""
for p = 2 to 179
pp = pisanoPrime p 1
if pp > 0
print "pisanoPrime(" & p & ": 1) = " & pp
.
.
print ""
numfmt 0 3
print "pisano(n) for integers 'n' from 1 to 180 are:"
for n = 1 to 180
write pisano (n) & " "
if n mod 15 = 0
print ""
.
.
.
main
</syntaxhighlight>
 
=={{header|Factor}}==
{{works with|Factor|0.99 2020-01-23}}
<langsyntaxhighlight lang="factor">USING: formatting fry grouping io kernel math math.functions
math.primes math.primes.factors math.ranges sequences ;
 
Line 65 ⟶ 636:
"n pisano for integers 'n' from 2 to 180:" print
2 180 [a,b] [ pisano ] map 15 group
[ [ "%3d " printf ] each nl ] each</langsyntaxhighlight>
{{out}}
<pre style="height:45ex">
Line 133 ⟶ 704:
 
=={{header|Go}}==
<langsyntaxhighlight lang="go">package main
 
import "fmt"
Line 218 ⟶ 789:
return 0 // can't do this one
}
return pisanoPeriod(ipow(p, k-1) * pisanoPeriod(p)
}
 
Line 268 ⟶ 839:
}
fmt.Println()
}</langsyntaxhighlight>
 
{{out}}
Line 337 ⟶ 908:
 
=={{header|Haskell}}==
<langsyntaxhighlight Haskelllang="haskell">import qualified Data.Text as T
 
main = do
putStrLn $ "PisanoPrime(p,2) for prime p lower than 15"
putStrLn print. see 15 . map (flip `pisanoPrime` 2) . filter isPrime $ [1 .. 15]
putStrLn $ "PisanoPrime(p,1) for prime p lower than 180"
putStrLn print. see 15 . map (flip `pisanoPrime` 1) . filter isPrime $ [1 .. 180]
let ns = [1 .. 180] :: [Int]
let xs = map pisanoPeriod ns
let ys = map pisano ns
let zs = map pisanoConjecture ns
putStrLn $ "Pisano(m) for m from 1 to 180"
putStrLn . see 15 $ map pisano [1 .. 180]
putStrLn $
putStrLn $ "map pisanoPeriod [1..180] == map pisano [1..180] = " ++ (show $ xs == ys)
putStrLn $ "map pisanoPeriod [1..180] == map pisanoConjecturepisano [1..180] = " ++ (show $ ys(xs == zsys)
putStrLn $
"map pisanoPeriod [1..180] == map pisanoConjecture [1..180] = " ++
show (ys == zs)
 
bagOf :: Int -> [a] -> [[a]]
bagOf _ [] = []
bagOf n xs = let (us,vs) = splitAt n xs in us : bagOf n vs
let (us, vs) = splitAt n xs
in us : bagOf n vs
 
see
see :: Show a => Int -> [a] -> String
:: Show a
see n = unlines.map unwords.bagOf n.map (T.unpack.T.justifyRight 3 ' '.T.pack.show)
=> Int -> [a] -> String
see n =
unlines .
map unwords . bagOf n . map (T.unpack . T.justifyRight 3 ' ' . T.pack . show)
 
fibMod
fibMod :: Integral a => a -> [a]
:: Integral a
=> a -> [a]
fibMod 1 = repeat 0
fibMod n = fib
where
where fib = 0 : 1 : zipWith (\x y -> rem (x+y) n) fib (tail fib)
fib = 0 : 1 : zipWith (\x y -> rem (x + y) n) fib (tail fib)
 
pisanoPeriod :: Integral a => a -> a
:: Integral a
pisanoPeriod m | m <= 0 = 0
=> a -> a
pisanoPeriod m
| m <= 0 = 0
pisanoPeriod 1 = 1
pisanoPeriod m = go 1 (tail $ fibMod m)
where
go t (0:1:_) = t
go t (_:xs) = go (succ t) xs
 
powMod
primes :: Integral a => [a]
:: Integral a
primes = 2:3:5:7:[p | p <- [11,13..], isPrime p]
=> a -> a -> a -> a
powMod _ _ k
| k < 0 = error "negative power"
powMod m _ _
| 1 == abs m = 0
powMod m p k
| 1 == abs p = mod v m
where
v
| 1 == p || even k = 1
| otherwise = p
powMod m p k = go p k
where
to x y = mod (x * y) m
go _ 0 = 1
go u 1 = mod u m
go u i
| even i = to w w
| otherwise = to u (to w w)
where
w = go u (quot i 2)
 
-- Fermat primality test
limitDivisor :: Integral a => a -> a
probablyPrime
limitDivisor = floor.(+0.05).sqrt.fromIntegral
:: Integral a
=> a -> Bool
probablyPrime p
| p < 2 || even p = 2 == p
| otherwise = 1 == powMod p 2 (p - 1)
 
primes
isPrime :: Integral a => a -> Bool
:: Integral a
isPrime p | p < 2 = False
=> [a]
primes =
2 :
3 :
5 :
7 :
[ p
| p <- [11,13 ..]
, isPrime p ]
 
limitDivisor
:: Integral a
=> a -> a
limitDivisor = floor . (+ 0.05) . sqrt . fromIntegral
 
isPrime
:: Integral a
=> a -> Bool
isPrime p
| not $ probablyPrime p = False
isPrime p = go primes
where
stop = limitDivisor p
go (n:_) | stop < n = True
go (n:ns) =| ifstop 0 == rem p< n then False else go= nsTrue
go (n:ns) = (0 /= rem p n) && go ns
go [] = True
 
factor
factor :: Integral a => a -> [(a,a)]
:: Integral a
factor n | n <= 1 = []
factor n => ifa null ans then-> [(na,1 a)] else ans
factor n
where
| n ans <= go1 n= primes[]
factor n = go n primes
fun x d c = if 0 /= rem x d then (x,c) else fun (quot x d) d (succ c)
where
go 1 _ = []
fun x d c
| 0 /= rem x d = (x, c)
| otherwise = fun (quot x d) d (succ c)
go 1 _ = []
go _ [] = []
go x (d:ds) | 0 /= rem x d = go x $ dropWhile ((0 /=).rem x) ds
go | 0 /= rem x (d:ds) = letgo (u,c)x =$ fundropWhile (quot(0 x d/=) d. 1rem in (d,cx):go u ds
go x (d:ds) =
let (u, c) = fun (quot x d) d 1
in (d, c) : go u ds
 
pisanoPrime :: Integral a => a -> a -> a
:: Integral a
pisanoPrime p k | p <= 0 || k < 0 = 0
=> a -> a -> a
pisanoPrime p k = pisanoPeriod $ p^k
pisanoPrime p k
| p <= 0 || k < 0 = 0
pisanoPrime p k = pisanoPeriod $ p ^ k
 
pisano
pisano :: Integral a => a -> a
:: Integral a
pisano m | m < 1 = 0
=> a -> a
pisano m
| m < 1 = 0
pisano 1 = 1
pisano m = foldl1 lcm . map (uncurry pisanoPrime) $ factor m
 
pisanoConjecture :: Integral a => a -> a
:: Integral a
pisanoConjecture m | m < 1 = 0
=> a -> a
pisanoConjecture m
| m < 1 = 0
pisanoConjecture 1 = 1
pisanoConjecture m = foldl1 lcm . map (uncurry pisanoPrime') $ factor m
where
where pisanoPrime' p k = (p^(k-1))*(pisanoPeriod p)</lang>
pisanoPrime' p k = (p ^ (k - 1)) * pisanoPeriod p</syntaxhighlight>
{{out}}
<pre>PisanoPrime(p,2) for prime p lower than 15
[ 6, 24, 100, 112, 110, 364]
 
PisanoPrime(p,1) for prime p lower than 180
3 8 20 16 10 28 36 18 48 14 30 76 40 88 32
[3,8,20,16,10,28,36,18,48,14,30,76,40,88,32,108,58,60,136,70,148,78,168,44,196,50,208,72,108,76,256,130,276,46,148,50,316,328,336,348,178]
108 58 60 136 70 148 78 168 44 196 50 208 72 108 76
256 130 276 46 148 50 316 328 336 348 178
 
Pisano(m) for m from 1 to 180
1 3 8 6 20 24 16 12 24 60 10 24 28 48 40
Line 434 ⟶ 1,088:
map pisanoPeriod [1..180] == map pisano [1..180] = True
map pisanoPeriod [1..180] == map pisanoConjecture [1..180] = True</pre>
 
=={{header|Java}}==
 
Use efficient algorithm to calculate period.
 
<syntaxhighlight lang="java">
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;
 
public class PisanoPeriod {
 
public static void main(String[] args) {
System.out.printf("Print pisano(p^2) for every prime p lower than 15%n");
for ( long i = 2 ; i < 15 ; i++ ) {
if ( isPrime(i) ) {
long n = i*i;
System.out.printf("pisano(%d) = %d%n", n, pisano(n));
}
}
 
System.out.printf("%nPrint pisano(p) for every prime p lower than 180%n");
for ( long n = 2 ; n < 180 ; n++ ) {
if ( isPrime(n) ) {
System.out.printf("pisano(%d) = %d%n", n, pisano(n));
}
}
 
System.out.printf("%nPrint pisano(n) for every integer from 1 to 180%n");
for ( long n = 1 ; n <= 180 ; n++ ) {
System.out.printf("%3d ", pisano(n));
if ( n % 10 == 0 ) {
System.out.printf("%n");
}
}
 
}
private static final boolean isPrime(long test) {
if ( test == 2 ) {
return true;
}
if ( test % 2 == 0 ) {
return false;
}
for ( long i = 3 ; i <= Math.sqrt(test) ; i += 2 ) {
if ( test % i == 0 ) {
return false;
}
}
return true;
}
 
private static Map<Long,Long> PERIOD_MEMO = new HashMap<>();
static {
PERIOD_MEMO.put(2L, 3L);
PERIOD_MEMO.put(3L, 8L);
PERIOD_MEMO.put(5L, 20L);
}
// See http://webspace.ship.edu/msrenault/fibonacci/fib.htm
private static long pisano(long n) {
if ( PERIOD_MEMO.containsKey(n) ) {
return PERIOD_MEMO.get(n);
}
if ( n == 1 ) {
return 1;
}
Map<Long,Long> factors = getFactors(n);
// Special cases
// pisano(2^k) = 3*n/2
if ( factors.size() == 1 & factors.get(2L) != null && factors.get(2L) > 0 ) {
long result = 3 * n / 2;
PERIOD_MEMO.put(n, result);
return result;
}
// pisano(5^k) = 4*n
if ( factors.size() == 1 & factors.get(5L) != null && factors.get(5L) > 0 ) {
long result = 4*n;
PERIOD_MEMO.put(n, result);
return result;
}
// pisano(2*5^k) = 6*n
if ( factors.size() == 2 & factors.get(2L) != null && factors.get(2L) == 1 && factors.get(5L) != null && factors.get(5L) > 0 ) {
long result = 6*n;
PERIOD_MEMO.put(n, result);
return result;
}
List<Long> primes = new ArrayList<>(factors.keySet());
long prime = primes.get(0);
if ( factors.size() == 1 && factors.get(prime) == 1 ) {
List<Long> divisors = new ArrayList<>();
if ( n % 10 == 1 || n % 10 == 9 ) {
for ( long divisor : getDivisors(prime-1) ) {
if ( divisor % 2 == 0 ) {
divisors.add(divisor);
}
}
}
else {
List<Long> pPlus1Divisors = getDivisors(prime+1);
for ( long divisor : getDivisors(2*prime+2) ) {
if ( ! pPlus1Divisors.contains(divisor) ) {
divisors.add(divisor);
}
}
}
Collections.sort(divisors);
for ( long divisor : divisors ) {
if ( fibModIdentity(divisor, prime) ) {
PERIOD_MEMO.put(prime, divisor);
return divisor;
}
}
throw new RuntimeException("ERROR 144: Divisor not found.");
}
long period = (long) Math.pow(prime, factors.get(prime)-1) * pisano(prime);
for ( int i = 1 ; i < primes.size() ; i++ ) {
prime = primes.get(i);
period = lcm(period, (long) Math.pow(prime, factors.get(prime)-1) * pisano(prime));
}
PERIOD_MEMO.put(n, period);
return period;
}
// Use Matrix multiplication to compute Fibonacci numbers.
private static boolean fibModIdentity(long n, long mod) {
long aRes = 0;
long bRes = 1;
long cRes = 1;
long aBase = 0;
long bBase = 1;
long cBase = 1;
while ( n > 0 ) {
if ( n % 2 == 1 ) {
long temp1 = 0, temp2 = 0, temp3 = 0;
if ( aRes > SQRT || aBase > SQRT || bRes > SQRT || bBase > SQRT || cBase > SQRT || cRes > SQRT ) {
temp1 = (multiply(aRes, aBase, mod) + multiply(bRes, bBase, mod)) % mod;
temp2 = (multiply(aBase, bRes, mod) + multiply(bBase, cRes, mod)) % mod;
temp3 = (multiply(bBase, bRes, mod) + multiply(cBase, cRes, mod)) % mod;
}
else {
temp1 = ((aRes*aBase % mod) + (bRes*bBase % mod)) % mod;
temp2 = ((aBase*bRes % mod) + (bBase*cRes % mod)) % mod;
temp3 = ((bBase*bRes % mod) + (cBase*cRes % mod)) % mod;
}
aRes = temp1;
bRes = temp2;
cRes = temp3;
}
n >>= 1L;
long temp1 = 0, temp2 = 0, temp3 = 0;
if ( aBase > SQRT || bBase > SQRT || cBase > SQRT ) {
temp1 = (multiply(aBase, aBase, mod) + multiply(bBase, bBase, mod)) % mod;
temp2 = (multiply(aBase, bBase, mod) + multiply(bBase, cBase, mod)) % mod;
temp3 = (multiply(bBase, bBase, mod) + multiply(cBase, cBase, mod)) % mod;
}
else {
temp1 = ((aBase*aBase % mod) + (bBase*bBase % mod)) % mod;
temp2 = ((aBase*bBase % mod) + (bBase*cBase % mod)) % mod;
temp3 = ((bBase*bBase % mod) + (cBase*cBase % mod)) % mod;
}
aBase = temp1;
bBase = temp2;
cBase = temp3;
}
return aRes % mod == 0 && bRes % mod == 1 && cRes % mod == 1;
}
 
private static final long SQRT = (long) Math.sqrt(Long.MAX_VALUE);
 
// Result is a*b % mod, without overflow.
public static final long multiply(long a, long b, long modulus) {
//System.out.println(" multiply : a = " + a + ", b = " + b + ", mod = " + modulus);
long x = 0;
long y = a % modulus;
long t;
while ( b > 0 ) {
if ( b % 2 == 1 ) {
t = x + y;
x = (t > modulus ? t-modulus : t);
}
t = y << 1;
y = (t > modulus ? t-modulus : t);
b >>= 1;
}
//System.out.println(" multiply : answer = " + (x % modulus));
return x % modulus;
}
 
private static final List<Long> getDivisors(long number) {
List<Long> divisors = new ArrayList<>();
long sqrt = (long) Math.sqrt(number);
for ( long i = 1 ; i <= sqrt ; i++ ) {
if ( number % i == 0 ) {
divisors.add(i);
long div = number / i;
if ( div != i ) {
divisors.add(div);
}
}
}
return divisors;
}
 
public static long lcm(long a, long b) {
return a*b/gcd(a,b);
}
 
public static long gcd(long a, long b) {
if ( b == 0 ) {
return a;
}
return gcd(b, a%b);
}
 
private static final Map<Long,Map<Long,Long>> allFactors = new TreeMap<Long,Map<Long,Long>>();
static {
Map<Long,Long> factors = new TreeMap<Long,Long>();
factors.put(2L, 1L);
allFactors.put(2L, factors);
}
 
public static Long MAX_ALL_FACTORS = 100000L;
 
public static final Map<Long,Long> getFactors(Long number) {
if ( allFactors.containsKey(number) ) {
return allFactors.get(number);
}
Map<Long,Long> factors = new TreeMap<Long,Long>();
if ( number % 2 == 0 ) {
Map<Long,Long> factorsdDivTwo = getFactors(number/2);
factors.putAll(factorsdDivTwo);
factors.merge(2L, 1L, (v1, v2) -> v1 + v2);
if ( number < MAX_ALL_FACTORS ) {
allFactors.put(number, factors);
}
return factors;
}
boolean prime = true;
long sqrt = (long) Math.sqrt(number);
for ( long i = 3 ; i <= sqrt ; i += 2 ) {
if ( number % i == 0 ) {
prime = false;
factors.putAll(getFactors(number/i));
factors.merge(i, 1L, (v1, v2) -> v1 + v2);
if ( number < MAX_ALL_FACTORS ) {
allFactors.put(number, factors);
}
return factors;
}
}
if ( prime ) {
factors.put(number, 1L);
if ( number < MAX_ALL_FACTORS ) {
allFactors.put(number, factors);
}
}
return factors;
}
 
}
</syntaxhighlight>
{{out}}
<pre>
Print pisano(p^2) for every prime p lower than 15
pisano(4) = 6
pisano(9) = 24
pisano(25) = 100
pisano(49) = 112
pisano(121) = 110
pisano(169) = 364
 
Print pisano(p) for every prime p lower than 180
pisano(2) = 3
pisano(3) = 8
pisano(5) = 20
pisano(7) = 16
pisano(11) = 10
pisano(13) = 28
pisano(17) = 36
pisano(19) = 18
pisano(23) = 48
pisano(29) = 14
pisano(31) = 30
pisano(37) = 76
pisano(41) = 40
pisano(43) = 88
pisano(47) = 32
pisano(53) = 108
pisano(59) = 58
pisano(61) = 60
pisano(67) = 136
pisano(71) = 70
pisano(73) = 148
pisano(79) = 78
pisano(83) = 168
pisano(89) = 44
pisano(97) = 196
pisano(101) = 50
pisano(103) = 208
pisano(107) = 72
pisano(109) = 108
pisano(113) = 76
pisano(127) = 256
pisano(131) = 130
pisano(137) = 276
pisano(139) = 46
pisano(149) = 148
pisano(151) = 50
pisano(157) = 316
pisano(163) = 328
pisano(167) = 336
pisano(173) = 348
pisano(179) = 178
 
Print pisano(n) for every integer from 1 to 180
1 3 8 6 20 24 16 12 24 60
10 24 28 48 40 24 36 24 18 60
16 30 48 24 100 84 72 48 14 120
30 48 40 36 80 24 76 18 56 60
40 48 88 30 120 48 32 24 112 300
72 84 108 72 20 48 72 42 58 120
60 30 48 96 140 120 136 36 48 240
70 24 148 228 200 18 80 168 78 120
216 120 168 48 180 264 56 60 44 120
112 48 120 96 180 48 196 336 120 300
50 72 208 84 80 108 72 72 108 60
152 48 76 72 240 42 168 174 144 120
110 60 40 30 500 48 256 192 88 420
130 120 144 408 360 36 276 48 46 240
32 210 140 24 140 444 112 228 148 600
50 36 72 240 60 168 316 78 216 240
48 216 328 120 40 168 336 48 364 180
72 264 348 168 400 120 232 132 178 120
</pre>
 
=={{header|JavaScript}}==
{{Trans|Lua}}
<syntaxhighlight lang="javascript">
{ // find the Pisano period of some primes and composites
 
const maxNumber = 180
// sieve the primes to maxNumber
let isPrime = []
for( let i = 1; i <= maxNumber; i ++ ){ isPrime[ i ] = i % 2 != 0 }
isPrime[ 1 ] = false
isPrime[ 2 ] = true
const rootMaxNumber = Math.floor( Math.sqrt( maxNumber ) )
for( let s = 3; s <= rootMaxNumber; s += 2 )
{
if( isPrime[ s ] )
{
for( let p = s * s; p <= maxNumber; p += s ){ isPrime[ p ] = false }
}
}
 
function pisano( m ) // returns the Pisano period of m
{
let p = 0, c = 1
for( let i = 0; i < ( m * m ); i ++ )
{
[ p, c ] = [ c, ( p + c ) % m ]
if( p == 0 && c == 1 ){ return i + 1 }
}
return 1
}
 
// returns the Pisano period of p^k or 0 if p is not prime or k < 1
function pisanoPrime( p, k )
{
return ( ! isPrime[ p ] || k < 1 ) ? 0 : Math.floor( p ** ( k - 1 ) ) * pisano( p )
}
 
function d4( n ) // returns n formatted in 4 characcters
{
return n.toString().padStart( 4 )
}
 
console.log( "Pisano period of p^2 where p is a prime < 15:" )
let list = ""
for( let p = 1; p < 15; p ++ )
{
if( isPrime[ p ] ){ list += " " + p + ":" + pisanoPrime( p, 2 ) }
}
console.log( list )
console.log( "Pisano period of primes up to 180, non-primes shown as \"*\":" )
list = ""
for( p = 1; p <= 180; p ++ )
{
list += ( ! isPrime[ p ] ? " *" : d4( pisanoPrime( p, 1 ) ) )
if( p % 10 == 0 ){ list += "\n" }
}
console.log( list )
console.log( "Pisano period of positive integers up to 180:" )
list = ""
for( let n = 1; n <= 180; n ++ )
{
list += d4( pisano( n ) )
if( n % 10 == 0 ){ list += "\n" }
}
console.log( list )
 
}
</syntaxhighlight>
{{out}}
<pre>
Pisano period of p^2 where p is a prime < 15:
2:6 3:24 5:100 7:112 11:110 13:364
Pisano period of primes up to 180, non-primes shown as "*":
* 3 8 * 20 * 16 * * *
10 * 28 * * * 36 * 18 *
* * 48 * * * * * 14 *
30 * * * * * 76 * * *
40 * 88 * * * 32 * * *
* * 108 * * * * * 58 *
60 * * * * * 136 * * *
70 * 148 * * * * * 78 *
* * 168 * * * * * 44 *
* * * * * * 196 * * *
50 * 208 * * * 72 * 108 *
* * 76 * * * * * * *
* * * * * * 256 * * *
130 * * * * * 276 * 46 *
* * * * * * * * 148 *
50 * * * * * 316 * * *
* * 328 * * * 336 * * *
* * 348 * * * * * 178 *
 
Pisano period of positive integers up to 180:
1 3 8 6 20 24 16 12 24 60
10 24 28 48 40 24 36 24 18 60
16 30 48 24 100 84 72 48 14 120
30 48 40 36 80 24 76 18 56 60
40 48 88 30 120 48 32 24 112 300
72 84 108 72 20 48 72 42 58 120
60 30 48 96 140 120 136 36 48 240
70 24 148 228 200 18 80 168 78 120
216 120 168 48 180 264 56 60 44 120
112 48 120 96 180 48 196 336 120 300
50 72 208 84 80 108 72 72 108 60
152 48 76 72 240 42 168 174 144 120
110 60 40 30 500 48 256 192 88 420
130 120 144 408 360 36 276 48 46 240
32 210 140 24 140 444 112 228 148 600
50 36 72 240 60 168 316 78 216 240
48 216 328 120 40 168 336 48 364 180
72 264 348 168 400 120 232 132 178 120
</pre>
 
=={{header|Julia}}==
<langsyntaxhighlight lang="julia">using Primes
 
const pisanos = Dict{Int, Int}()
Line 470 ⟶ 1,580:
println("\nPisano(n) for n from 2 to 180:\n", [pisano(i) for i in 2:180])
println("\nPisano(n) using pisanoPrime for n from 2 to 180:\n", [pisanotask(i) for i in 2:180])
</langsyntaxhighlight>{{out}}
<pre>
pisanoPrime(2, 2) = 6
Line 527 ⟶ 1,637:
</pre>
 
=={{header|Perl 6Lua}}==
{{Trans|ALGOL 68}}
{{works with|Rakudo|2020.02}}
<syntaxhighlight lang="lua">
Didn't bother making two differently named routines, just made a multi that will auto dispatch to the correct candidate.
do -- find the Pisano period of some primes and composites
<lang perl6>use Prime::Factor;
 
local maxNumber = 180
constant @fib := 1,1,*+*…*;
-- sieve the primes to maxNumber
local isPrime = {}
for i = 1, maxNumber do isPrime[ i ] = i % 2 ~= 0 end
isPrime[ 1 ] = false
isPrime[ 2 ] = true
for s = 3, math.floor( math.sqrt( maxNumber ) ), 2 do
if isPrime[ s ] then
for p = s * s, maxNumber, s do isPrime[ p ] = false end
end
end
 
local function pisano( m ) -- returns the Pisano period of m
my %cache;
local p, c = 0, 1
for i = 0, ( m * m ) - 1 do
p, c = c, ( p + c ) % m
if p == 0 and c == 1 then return i + 1 end
end
return 1
end
 
-- returns the Pisano period of p^k or 0 if p is not prime or k < 1
multi pisano-period (Int $p where *.is-prime, Int $k where * > 0 = 1 ) {
local function pisanoPrime( p, k )
return %cache{"$p|$k"} if %cache{"$p|$k"};
return ( not isPrime[ p ] or k < 1 ) and 0 or math.floor( p ^ ( k - 1 ) * pisano( p ) )
my $fibmod = @fib.map: * % $p**$k;
end
%cache{"$p|$k"} = (1..*).first: { !$fibmod[$_-1] and ($fibmod[$_] == 1) }
 
local function d4( n ) -- returns n formatted in 4 characcters
return string.format( "%4d", n )
end
 
io.write( "Pisano period of p^2 where p is a prime < 15:\n" )
for p = 1, 15 do
if isPrime[ p ] then io.write( " "..p..":"..pisanoPrime( p, 2 ) ) end
end
io.write( "\nPisano period of primes up to 180, non-primes shown as \"*\":\n" )
for p = 1, 180 do
io.write( not isPrime[ p ] and " *" or d4( pisanoPrime( p, 1 ) ) )
if p % 10 == 0 then io.write( "\n" ) end
end
io.write( "\nPisano period of positive integers up to 180:\n" )
for n = 1, 180 do
io.write( d4( pisano( n ) ) )
if n % 10 == 0 then io.write( "\n" ) end
end
 
end
</syntaxhighlight>
{{out}}
<pre>
Pisano period of p^2 where p is a prime < 15:
2:6 3:24 5:100 7:112 11:110 13:364
Pisano period of primes up to 180, non-primes shown as "*":
* 3 8 * 20 * 16 * * *
10 * 28 * * * 36 * 18 *
* * 48 * * * * * 14 *
30 * * * * * 76 * * *
40 * 88 * * * 32 * * *
* * 108 * * * * * 58 *
60 * * * * * 136 * * *
70 * 148 * * * * * 78 *
* * 168 * * * * * 44 *
* * * * * * 196 * * *
50 * 208 * * * 72 * 108 *
* * 76 * * * * * * *
* * * * * * 256 * * *
130 * * * * * 276 * 46 *
* * * * * * * * 148 *
50 * * * * * 316 * * *
* * 328 * * * 336 * * *
* * 348 * * * * * 178 *
 
Pisano period of positive integers up to 180:
1 3 8 6 20 24 16 12 24 60
10 24 28 48 40 24 36 24 18 60
16 30 48 24 100 84 72 48 14 120
30 48 40 36 80 24 76 18 56 60
40 48 88 30 120 48 32 24 112 300
72 84 108 72 20 48 72 42 58 120
60 30 48 96 140 120 136 36 48 240
70 24 148 228 200 18 80 168 78 120
216 120 168 48 180 264 56 60 44 120
112 48 120 96 180 48 196 336 120 300
50 72 208 84 80 108 72 72 108 60
152 48 76 72 240 42 168 174 144 120
110 60 40 30 500 48 256 192 88 420
130 120 144 408 360 36 276 48 46 240
32 210 140 24 140 444 112 228 148 600
50 36 72 240 60 168 316 78 216 240
48 216 328 120 40 168 336 48 364 180
72 264 348 168 400 120 232 132 178 120
</pre>
 
 
=={{header|Mathematica}}/{{header|Wolfram Language}}==
{{trans|Julia}}
<syntaxhighlight>
ClearAll["Global`*"];
 
pisanos = <||>;
pisano[p_] := Module[{lastn, n, i}, If[p < 2, Return[1]];
i = pisanos[p];
If[i > 0, Return[i]];
lastn = 0; n = 1;
For[i = 1, i <= p^2, i++, {lastn, n} = {n, Mod[lastn + n, p]};
If[lastn == 0 && n == 1, pisanos[p] = i;
Return[i]]];
Return[1]]
 
pisanoprime[p_, k_] := Module[{}, Assert[PrimeQ[p]];
p^(k - 1)*pisano[p]]
 
pisanotask[n_] := Module[{factors}, factors = FactorInteger[n];
Map[pisanoprime[#[[1]], #[[2]]] &, factors] // Apply[LCM, #] &]
 
Do[If[PrimeQ[i],
Print["pisanoPrime[", i, ", 2] = ", pisanoprime[i, 2]]], {i, 1, 15}]
 
Do[If[PrimeQ[i],
Print["pisanoPrime[", i, ", 1] = ", pisanoprime[i, 1]]], {i, 1, 180}]
 
Print["\nPisano[n] for n from 2 to 180:"];
Print[Table[pisano[i], {i, 2, 180}]]
 
Print["\nPisano[n] using pisanoPrime for n from 2 to 180:"];
Print[Table[pisanotask[i], {i, 2, 180}]]
</syntaxhighlight>
{{out}}
<pre>
pisanoPrime[2, 2] = 6
pisanoPrime[3, 2] = 24
pisanoPrime[5, 2] = 100
pisanoPrime[7, 2] = 112
pisanoPrime[11, 2] = 110
pisanoPrime[13, 2] = 364
pisanoPrime[2, 1] = 3
pisanoPrime[3, 1] = 8
pisanoPrime[5, 1] = 20
pisanoPrime[7, 1] = 16
pisanoPrime[11, 1] = 10
pisanoPrime[13, 1] = 28
pisanoPrime[17, 1] = 36
pisanoPrime[19, 1] = 18
pisanoPrime[23, 1] = 48
pisanoPrime[29, 1] = 14
pisanoPrime[31, 1] = 30
pisanoPrime[37, 1] = 76
pisanoPrime[41, 1] = 40
pisanoPrime[43, 1] = 88
pisanoPrime[47, 1] = 32
pisanoPrime[53, 1] = 108
pisanoPrime[59, 1] = 58
pisanoPrime[61, 1] = 60
pisanoPrime[67, 1] = 136
pisanoPrime[71, 1] = 70
pisanoPrime[73, 1] = 148
pisanoPrime[79, 1] = 78
pisanoPrime[83, 1] = 168
pisanoPrime[89, 1] = 44
pisanoPrime[97, 1] = 196
pisanoPrime[101, 1] = 50
pisanoPrime[103, 1] = 208
pisanoPrime[107, 1] = 72
pisanoPrime[109, 1] = 108
pisanoPrime[113, 1] = 76
pisanoPrime[127, 1] = 256
pisanoPrime[131, 1] = 130
pisanoPrime[137, 1] = 276
pisanoPrime[139, 1] = 46
pisanoPrime[149, 1] = 148
pisanoPrime[151, 1] = 50
pisanoPrime[157, 1] = 316
pisanoPrime[163, 1] = 328
pisanoPrime[167, 1] = 336
pisanoPrime[173, 1] = 348
pisanoPrime[179, 1] = 178
 
Pisano[n] for n from 2 to 180:
{3, 8, 6, 20, 24, 16, 12, 24, 60, 10, 24, 28, 48, 40, 24, 36, 24, 18, 60, 16, 30, 48, 24, 100, 84, 72, 48, 14, 120, 30, 48, 40, 36, 80, 24, 76, 18, 56, 60, 40, 48, 88, 30, 120, 48, 32, 24, 112, 300, 72, 84, 108, 72, 20, 48, 72, 42, 58, 120, 60, 30, 48, 96, 140, 120, 136, 36, 48, 240, 70, 24, 148, 228, 200, 18, 80, 168, 78, 120, 216, 120, 168, 48, 180, 264, 56, 60, 44, 120, 112, 48, 120, 96, 180, 48, 196, 336, 120, 300, 50, 72, 208, 84, 80, 108, 72, 72, 108, 60, 152, 48, 76, 72, 240, 42, 168, 174, 144, 120, 110, 60, 40, 30, 500, 48, 256, 192, 88, 420, 130, 120, 144, 408, 360, 36, 276, 48, 46, 240, 32, 210, 140, 24, 140, 444, 112, 228, 148, 600, 50, 36, 72, 240, 60, 168, 316, 78, 216, 240, 48, 216, 328, 120, 40, 168, 336, 48, 364, 180, 72, 264, 348, 168, 400, 120, 232, 132, 178, 120}
 
Pisano[n] using pisanoPrime for n from 2 to 180:
{3, 8, 6, 20, 24, 16, 12, 24, 60, 10, 24, 28, 48, 40, 24, 36, 24, 18, 60, 16, 30, 48, 24, 100, 84, 72, 48, 14, 120, 30, 48, 40, 36, 80, 24, 76, 18, 56, 60, 40, 48, 88, 30, 120, 48, 32, 24, 112, 300, 72, 84, 108, 72, 20, 48, 72, 42, 58, 120, 60, 30, 48, 96, 140, 120, 136, 36, 48, 240, 70, 24, 148, 228, 200, 18, 80, 168, 78, 120, 216, 120, 168, 48, 180, 264, 56, 60, 44, 120, 112, 48, 120, 96, 180, 48, 196, 336, 120, 300, 50, 72, 208, 84, 80, 108, 72, 72, 108, 60, 152, 48, 76, 72, 240, 42, 168, 174, 144, 120, 110, 60, 40, 30, 500, 48, 256, 192, 88, 420, 130, 120, 144, 408, 360, 36, 276, 48, 46, 240, 32, 210, 140, 24, 140, 444, 112, 228, 148, 600, 50, 36, 72, 240, 60, 168, 316, 78, 216, 240, 48, 216, 328, 120, 40, 168, 336, 48, 364, 180, 72, 264, 348, 168, 400, 120, 232, 132, 178, 120}
 
</pre>
 
 
=={{header|Nim}}==
{{trans|Go}}
<syntaxhighlight lang="nim">import math, strformat, tables
 
func primes(n: Positive): seq[int] =
## Return the list of prime divisors of "n".
var n = n.int
for d in 2..n:
var q = n div d
var m = n mod d
while m == 0:
result.add d
n = q
q = n div d
m = n mod d
 
func isPrime(n: Positive): bool =
## Return true if "n" is prime.
if n < 2: return false
if n mod 2 == 0: return n == 2
if n mod 3 == 0: return n == 3
var d = 5
while d <= sqrt(n.toFloat).int:
if n mod d == 0: return false
inc d, 2
if n mod d == 0: return false
inc d, 4
result = true
 
func pisanoPeriod(m: Positive): int =
## Calculate the Pisano period of 'm' from first principles.
var p = 0
var c = 1
for i in 0..<m*m:
p = (p + c) mod m
swap p, c
if p == 0 and c == 1: return i + 1
result = 1
 
func pisanoPrime(p, k: Positive): int =
## Calculate the Pisano period of p^k where 'p' is prime and 'k' is a positive integer.
if p.isPrime: p^(k-1) * p.pisanoPeriod() else: 0
 
func pisano(m: Positive): int =
## Calculate the Pisano period of 'm' using pisanoPrime.
let primes = m.primes
var primePowers = primes.toCountTable
var pps: seq[int]
for k, v in primePowers.pairs:
pps.add pisanoPrime(k, v)
if pps.len == 0: return 1
result = pps[0]
for i in 1..pps.high:
result = lcm(result, pps[i])
 
 
when isMainModule:
 
for p in 2..14:
let pp = pisanoPrime(p, 2)
if pp > 0:
echo &"pisanoPrime({p:2}, 2) = {pp}"
 
echo()
for p in 2..179:
let pp = pisanoPrime(p, 1)
if pp > 0:
echo &"pisanoPrime({p:3}, 1) = {pp}"
 
echo()
echo "pisano(n) for integers 'n' from 1 to 180 are:"
for n in 1..180:
stdout.write &"{pisano(n):3}", if n mod 15 == 0: '\n' else: ' '</syntaxhighlight>
 
{{out}}
<pre>pisanoPrime( 2, 2) = 6
pisanoPrime( 3, 2) = 24
pisanoPrime( 5, 2) = 100
pisanoPrime( 7, 2) = 112
pisanoPrime(11, 2) = 110
pisanoPrime(13, 2) = 364
 
pisanoPrime( 2, 1) = 3
pisanoPrime( 3, 1) = 8
pisanoPrime( 5, 1) = 20
pisanoPrime( 7, 1) = 16
pisanoPrime( 11, 1) = 10
pisanoPrime( 13, 1) = 28
pisanoPrime( 17, 1) = 36
pisanoPrime( 19, 1) = 18
pisanoPrime( 23, 1) = 48
pisanoPrime( 29, 1) = 14
pisanoPrime( 31, 1) = 30
pisanoPrime( 37, 1) = 76
pisanoPrime( 41, 1) = 40
pisanoPrime( 43, 1) = 88
pisanoPrime( 47, 1) = 32
pisanoPrime( 53, 1) = 108
pisanoPrime( 59, 1) = 58
pisanoPrime( 61, 1) = 60
pisanoPrime( 67, 1) = 136
pisanoPrime( 71, 1) = 70
pisanoPrime( 73, 1) = 148
pisanoPrime( 79, 1) = 78
pisanoPrime( 83, 1) = 168
pisanoPrime( 89, 1) = 44
pisanoPrime( 97, 1) = 196
pisanoPrime(101, 1) = 50
pisanoPrime(103, 1) = 208
pisanoPrime(107, 1) = 72
pisanoPrime(109, 1) = 108
pisanoPrime(113, 1) = 76
pisanoPrime(127, 1) = 256
pisanoPrime(131, 1) = 130
pisanoPrime(137, 1) = 276
pisanoPrime(139, 1) = 46
pisanoPrime(149, 1) = 148
pisanoPrime(151, 1) = 50
pisanoPrime(157, 1) = 316
pisanoPrime(163, 1) = 328
pisanoPrime(167, 1) = 336
pisanoPrime(173, 1) = 348
pisanoPrime(179, 1) = 178
 
pisano(n) for integers 'n' from 1 to 180 are:
1 3 8 6 20 24 16 12 24 60 10 24 28 48 40
24 36 24 18 60 16 30 48 24 100 84 72 48 14 120
30 48 40 36 80 24 76 18 56 60 40 48 88 30 120
48 32 24 112 300 72 84 108 72 20 48 72 42 58 120
60 30 48 96 140 120 136 36 48 240 70 24 148 228 200
18 80 168 78 120 216 120 168 48 180 264 56 60 44 120
112 48 120 96 180 48 196 336 120 300 50 72 208 84 80
108 72 72 108 60 152 48 76 72 240 42 168 174 144 120
110 60 40 30 500 48 256 192 88 420 130 120 144 408 360
36 276 48 46 240 32 210 140 24 140 444 112 228 148 600
50 36 72 240 60 168 316 78 216 240 48 216 328 120 40
168 336 48 364 180 72 264 348 168 400 120 232 132 178 120</pre>
 
 
=={{header|PARI/GP}}==
{{trans|Mathematica/Wolfram_Language}}
<syntaxhighlight lang="PARI/GP">
\\ Initialize an associative array equivalently
pisanos = Map();
 
\\ Function to calculate the Pisano period for a given prime p
pisano(p) = {
local(lastn, n, i);
if (p < 2, return(1));
if (mapisdefined(pisanos, p),
return(mapget(pisanos, p));
);
lastn = 0; n = 1;
for (i = 1, p^2,
[lastn, n] = [n, Mod(lastn + n, p)];
if (lastn == 0 && n == 1,
mapput(pisanos, p, i);
return(i);
);
);
return(1);
}
 
\\ Function to calculate Pisano period for a prime p and a power k
multi pisano-period (Int $p where * > 0, Int $k where * > 0 = 1 ) {
pisanoprime(p, k) = {
[lcm] prime-factors($p).squish.map: { samewith $_, $k }
my(i = pisano(p));
if (!isprime(p), error("p must be prime"));
p^(k-1) * i;
}
 
\\ Function to calculate Pisano period for a composite number n
pisanotask(n) = {
my(factors = factor(n));
\\print("factors=" factors);
\\apply(x -> print("x=" x), factors);
lcm( vector(#factors~, i, pisanoprime(factors[i, 1], factors[i, 2])) );
}
 
{
put "Pisano period (p, 2) for primes less than 50";
\\ Print Pisano periods for prime numbers up to 15 with k=2
put (map { pisano-period($_, 2) }, ^50 .grep: *.is-prime )».fmt('%4d');
for (i = 1, 15,
if (isprime(i),
print("pisanoPrime[" i ", 2] = " pisanoprime(i, 2))
);
);
 
put "\nPisano\ periodPrint (p,Pisano 1)periods for primesprime lessnumbers thanup to 180"; with k=1
for (i = 1, 180,
.put for (map { pisano-period($_, 1) }, ^180 .grep: *.is-prime )».fmt('%4d').batch(15);
if (isprime(i),
print("pisanoPrime[" i ", 1] = " pisanoprime(i, 1))
);
);
 
put "\nPisano\ periodPrint (p,Pisano 1)periods for integersnumbers 12 to 180";
print("\nPisano[n] for n from 2 to 180:");
.put for (1..180).map( { pisano-period($_) } )».fmt('%4d').batch(15);</lang>
print(vector(179, i, pisano(i+1)));
 
\\ Print Pisano periods using pisanotask for numbers 2 to 180
print("\nPisano[n] using pisanoPrime for n from 2 to 180:");
print(vector(179, i, pisanotask(i+1)));
}
</syntaxhighlight>
{{out}}
<pre>
<pre>Pisano period (p, 2) for primes less than 50
pisanoPrime[2, 2] = 6
6 24 100 112 110 364 612 342 1104 406 930 2812 1640 3784 1504
pisanoPrime[3, 2] = 24
pisanoPrime[5, 2] = 100
pisanoPrime[7, 2] = 112
pisanoPrime[11, 2] = 110
pisanoPrime[13, 2] = 364
pisanoPrime[2, 1] = 3
pisanoPrime[3, 1] = 8
pisanoPrime[5, 1] = 20
pisanoPrime[7, 1] = 16
pisanoPrime[11, 1] = 10
pisanoPrime[13, 1] = 28
pisanoPrime[17, 1] = 36
pisanoPrime[19, 1] = 18
pisanoPrime[23, 1] = 48
pisanoPrime[29, 1] = 14
pisanoPrime[31, 1] = 30
pisanoPrime[37, 1] = 76
pisanoPrime[41, 1] = 40
pisanoPrime[43, 1] = 88
pisanoPrime[47, 1] = 32
pisanoPrime[53, 1] = 108
pisanoPrime[59, 1] = 58
pisanoPrime[61, 1] = 60
pisanoPrime[67, 1] = 136
pisanoPrime[71, 1] = 70
pisanoPrime[73, 1] = 148
pisanoPrime[79, 1] = 78
pisanoPrime[83, 1] = 168
pisanoPrime[89, 1] = 44
pisanoPrime[97, 1] = 196
pisanoPrime[101, 1] = 50
pisanoPrime[103, 1] = 208
pisanoPrime[107, 1] = 72
pisanoPrime[109, 1] = 108
pisanoPrime[113, 1] = 76
pisanoPrime[127, 1] = 256
pisanoPrime[131, 1] = 130
pisanoPrime[137, 1] = 276
pisanoPrime[139, 1] = 46
pisanoPrime[149, 1] = 148
pisanoPrime[151, 1] = 50
pisanoPrime[157, 1] = 316
pisanoPrime[163, 1] = 328
pisanoPrime[167, 1] = 336
pisanoPrime[173, 1] = 348
pisanoPrime[179, 1] = 178
 
Pisano[n] periodfor (p, 1) forn primesfrom less2 thanto 180:
[3, 8, 6, 20, 24, 16, 12, 24, 60, 10, 24, 28, 48, 40, 24, 36, 24, 18, 60, 16, 30, 48, 24, 100, 84, 72, 48, 14, 120, 30, 48, 40, 36, 80, 24, 76, 18, 56, 60, 40, 48, 88, 30, 120, 48, 32, 24, 112, 300, 72, 84, 108, 72, 20, 48, 72, 42, 58, 120, 60, 30, 48, 96, 140, 120, 136, 36, 48, 240, 70, 24, 148, 228, 200, 18, 80, 168, 78, 120, 216, 120, 168, 48, 180, 264, 56, 60, 44, 120, 112, 48, 120, 96, 180, 48, 196, 336, 120, 300, 50, 72, 208, 84, 80, 108, 72, 72, 108, 60, 152, 48, 76, 72, 240, 42, 168, 174, 144, 120, 110, 60, 40, 30, 500, 48, 256, 192, 88, 420, 130, 120, 144, 408, 360, 36, 276, 48, 46, 240, 32, 210, 140, 24, 140, 444, 112, 228, 148, 600, 50, 36, 72, 240, 60, 168, 316, 78, 216, 240, 48, 216, 328, 120, 40, 168, 336, 48, 364, 180, 72, 264, 348, 168, 400, 120, 232, 132, 178, 120]
3 8 20 16 10 28 36 18 48 14 30 76 40 88 32
108 58 60 136 70 148 78 168 44 196 50 208 72 108 76
256 130 276 46 148 50 316 328 336 348 178
 
Pisano[n] periodusing (p, 1)pisanoPrime for integersn from 12 to 180:
[3, 8, 6, 20, 24, 16, 12, 24, 60, 10, 24, 28, 48, 40, 24, 36, 24, 18, 60, 16, 30, 48, 24, 100, 84, 72, 48, 14, 120, 30, 48, 40, 36, 80, 24, 76, 18, 56, 60, 40, 48, 88, 30, 120, 48, 32, 24, 112, 300, 72, 84, 108, 72, 20, 48, 72, 42, 58, 120, 60, 30, 48, 96, 140, 120, 136, 36, 48, 240, 70, 24, 148, 228, 200, 18, 80, 168, 78, 120, 216, 120, 168, 48, 180, 264, 56, 60, 44, 120, 112, 48, 120, 96, 180, 48, 196, 336, 120, 300, 50, 72, 208, 84, 80, 108, 72, 72, 108, 60, 152, 48, 76, 72, 240, 42, 168, 174, 144, 120, 110, 60, 40, 30, 500, 48, 256, 192, 88, 420, 130, 120, 144, 408, 360, 36, 276, 48, 46, 240, 32, 210, 140, 24, 140, 444, 112, 228, 148, 600, 50, 36, 72, 240, 60, 168, 316, 78, 216, 240, 48, 216, 328, 120, 40, 168, 336, 48, 364, 180, 72, 264, 348, 168, 400, 120, 232, 132, 178, 120]
1 3 8 3 20 24 16 3 8 60 10 24 28 48 40
3 36 24 18 60 16 30 48 24 20 84 8 48 14 120
30 3 40 36 80 24 76 18 56 60 40 48 88 30 40
48 32 24 16 60 72 84 108 24 20 48 72 42 58 120
60 30 16 3 140 120 136 36 48 240 70 24 148 228 40
18 80 168 78 60 8 120 168 48 180 264 56 30 44 120
112 48 120 96 180 24 196 48 40 60 50 72 208 84 80
108 72 24 108 60 152 48 76 72 240 42 56 174 144 120
10 60 40 30 20 48 256 3 88 420 130 120 144 408 40
36 276 48 46 240 32 210 140 24 140 444 16 228 148 120
50 18 72 240 60 168 316 78 216 60 48 24 328 120 40
168 336 48 28 180 72 264 348 168 80 30 232 132 178 120</pre>
 
</pre>
=={{header|Phix}}==
<lang Phix>function pisano_period(integer m)
-- Calculates the Pisano period of 'm' from first principles. (copied from Go)
integer p = 0, c = 1
for i=0 to m*m-1 do
{p, c} = {c, mod(p+c,m)}
if p == 0 and c == 1 then
return i + 1
end if
end for
return 1
end function
function pisanoPrime(integer p, k)
if not is_prime(p) or k=0 then ?9/0 end if
return power(p,k-1)*pisano_period(p)
end function
function pisano(integer m)
-- Calculates the Pisano period of 'm' using pisanoPrime.
sequence s = prime_factors(m, true, get_maxprime(m))&0,
pps = {}
integer k = 1, p = s[1]
for i=2 to length(s) do
integer n = s[i]
if n!=p then
pps = append(pps,pisanoPrime(p,k))
{k,p} = {1,n}
else
k += 1
end if
end for
return lcm(pps)
end function
procedure p(integer k, lim)
-- test harness
printf(1,"pisanoPrimes")
integer pdx = 1, c = 0
while true do
integer p = get_prime(pdx)
if p>=lim then exit end if
c += 1
if c=7 then puts(1,"\n ") c = 1
elsif pdx>1 then puts(1,", ") end if
printf(1,"(%3d,%d)=%3d",{p,k,pisanoPrime(p,k)})
pdx += 1
end while
printf(1,"\n")
end procedure
p(2,15)
p(1,180)
 
=={{header|Perl}}==
sequence p180 = {}
{{trans|Sidef}}
for n=2 to 180 do p180 &= pisano(n) end for
{{libheader|ntheory}}
printf(1,"pisano(2..180):\n")
<syntaxhighlight lang="perl">use strict;
pp(p180,{pp_IntFmt,"%4d",pp_IntCh,false})
use warnings;
use feature 'say';
use ntheory qw(primes factor_exp lcm);
 
sub pisano_period_pp {
printf(1,"\nTiming comparison:\n")
my($a, $b, $n, $k) = (0, 1, $_[0]**$_[1]);
for i=1 to 2 do
atomwhile t0 = time(++$k) {
($a, $b) = ($b, ($a+$b) % $n);
string fn = {"pisano_period","pisano"}[i],
return $k if via$a == {"",",0 viaand pisanoPrime()"}[i]$b == 1;
}
integer f = routine_id(fn)
}
for n=2 to 10000 do
 
{} = f(n)
sub pisano_period {
end for
(lcm map { pisano_period_pp($$_[0],$$_[1]) } factor_exp($_[0])) or 1;
t0 = time()-t0
}
printf(1,"%s(2..10000)%s:%s\n",{fn,via,elapsed(t0)})
 
end for</lang>
sub display { (sprintf "@{['%5d' x @_]}", @_) =~ s/(.{75})/$1\n/gr }
 
say "Pisano periods for squares of primes p <= 50:\n", display( map { pisano_period_pp($_, 2) } @{primes(1, 50)} ),
"\nPisano periods for primes p <= 180:\n", display( map { pisano_period_pp($_, 1) } @{primes(1, 180)} ),
"\n\nPisano periods for integers n from 1 to 180:\n", display( map { pisano_period ($_ ) } 1..180 );</syntaxhighlight>
{{out}}
<pre>Pisano periods for squares of primes p <= 50:
6 24 100 112 110 364 612 342 1104 406 930 2812 1640 3784 1504
 
Pisano periods for primes p <= 180:
3 8 20 16 10 28 36 18 48 14 30 76 40 88 32
108 58 60 136 70 148 78 168 44 196 50 208 72 108 76
256 130 276 46 148 50 316 328 336 348 178
 
Pisano periods for integers n from 1 to 180:
1 3 8 6 20 24 16 12 24 60 10 24 28 48 40
24 36 24 18 60 16 30 48 24 100 84 72 48 14 120
30 48 40 36 80 24 76 18 56 60 40 48 88 30 120
48 32 24 112 300 72 84 108 72 20 48 72 42 58 120
60 30 48 96 140 120 136 36 48 240 70 24 148 228 200
18 80 168 78 120 216 120 168 48 180 264 56 60 44 120
112 48 120 96 180 48 196 336 120 300 50 72 208 84 80
108 72 72 108 60 152 48 76 72 240 42 168 174 144 120
110 60 40 30 500 48 256 192 88 420 130 120 144 408 360
36 276 48 46 240 32 210 140 24 140 444 112 228 148 600
50 36 72 240 60 168 316 78 216 240 48 216 328 120 40
168 336 48 364 180 72 264 348 168 400 120 232 132 178 120</pre>
 
=={{header|Phix}}==
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">pisano_period</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- Calculates the Pisano period of 'm' from first principles. (copied from Go)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">*</span><span style="color: #000000;">m</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">c</span><span style="color: #0000FF;">,</span> <span style="color: #7060A8;">mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">+</span><span style="color: #000000;">c</span><span style="color: #0000FF;">,</span><span style="color: #000000;">m</span><span style="color: #0000FF;">)}</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">==</span> <span style="color: #000000;">0</span> <span style="color: #008080;">and</span> <span style="color: #000000;">c</span> <span style="color: #0000FF;">==</span> <span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">i</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">pisanoPrime</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #7060A8;">is_prime</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">or</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #0000FF;">?</span><span style="color: #000000;">9</span><span style="color: #0000FF;">/</span><span style="color: #000000;">0</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">k</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)*</span><span style="color: #000000;">pisano_period</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">pisano</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- Calculates the Pisano period of 'm' using pisanoPrime.</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #000000;">1</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">prime_factors</span><span style="color: #0000FF;">(</span><span style="color: #000000;">m</span><span style="color: #0000FF;">,</span> <span style="color: #004600;">true</span><span style="color: #0000FF;">,</span> <span style="color: #7060A8;">get_maxprime</span><span style="color: #0000FF;">(</span><span style="color: #000000;">m</span><span style="color: #0000FF;">))&</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">pps</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">p</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">pps</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pps</span><span style="color: #0000FF;">,</span><span style="color: #000000;">pisanoPrime</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">k</span><span style="color: #0000FF;">))</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">k</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">else</span>
<span style="color: #000000;">k</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #7060A8;">lcm</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pps</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">lim</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- test harness</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"pisanoPrimes"</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">pdx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">get_prime</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pdx</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">lim</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">c</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">=</span><span style="color: #000000;">7</span> <span style="color: #008080;">then</span> <span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n "</span><span style="color: #0000FF;">)</span> <span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">pdx</span><span style="color: #0000FF;">></span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> <span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">", "</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"(%3d,%d)=%3d"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">k</span><span style="color: #0000FF;">,</span><span style="color: #000000;">pisanoPrime</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">k</span><span style="color: #0000FF;">)})</span>
<span style="color: #000000;">pdx</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #000000;">p</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">15</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">p</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">180</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">p180</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">180</span> <span style="color: #008080;">do</span> <span style="color: #000000;">p180</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">pisano</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"pisano(1..180):\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">pp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p180</span><span style="color: #0000FF;">,{</span><span style="color: #004600;">pp_IntFmt</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%4d"</span><span style="color: #0000FF;">,</span><span style="color: #004600;">pp_IntCh</span><span style="color: #0000FF;">,</span><span style="color: #004600;">false</span><span style="color: #0000FF;">})</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
Line 658 ⟶ 2,206:
(127,1)=256, (131,1)=130, (137,1)=276, (139,1)= 46, (149,1)=148, (151,1)= 50
(157,1)=316, (163,1)=328, (167,1)=336, (173,1)=348, (179,1)=178
pisano(21..180):
{ 1, 3, 8, 6, 20, 24, 16, 12, 24, 60, 10, 24, 28, 48, 40, 24,
24, 36, 24, 18, 60, 16, 30, 48, 24, 100, 84, 72, 48, 14, 120, 30,
30, 48, 40, 36, 80, 24, 76, 18, 56, 60, 40, 48, 88, 30, 120, 48,
48, 32, 24, 112, 300, 72, 84, 108, 72, 20, 48, 72, 42, 58, 120, 60,
60, 30, 48, 96, 140, 120, 136, 36, 48, 240, 70, 24, 148, 228, 200, 18,
18, 80, 168, 78, 120, 216, 120, 168, 48, 180, 264, 56, 60, 44, 120, 112,
112, 48, 120, 96, 180, 48, 196, 336, 120, 300, 50, 72, 208, 84, 80, 108,
108, 72, 72, 108, 60, 152, 48, 76, 72, 240, 42, 168, 174, 144, 120, 110,
110, 60, 40, 30, 500, 48, 256, 192, 88, 420, 130, 120, 144, 408, 360, 36,
36, 276, 48, 46, 240, 32, 210, 140, 24, 140, 444, 112, 228, 148, 600, 50,
50, 36, 72, 240, 60, 168, 316, 78, 216, 240, 48, 216, 328, 120, 40, 168,
168, 336, 48, 364, 180, 72, 264, 348, 168, 400, 120, 232, 132, 178, 120}
 
Timing comparison:
pisano_period(2..10000):8.9s
pisano(2..10000), via pisanoPrime():3.4s
</pre>
 
Line 680 ⟶ 2,224:
Uses the [[wp:SymPy|SymPy]] library.
 
<langsyntaxhighlight lang="python">from sympy import isprime, lcm, factorint, primerange
from functools import reduce
 
Line 719 ⟶ 2,263:
print("\nPisano period (p) for integers 1 to 180")
for i in range(1, 181):
print(" %3d" % pisano2(i), end="" if i % 10 else "\n")</langsyntaxhighlight>
 
{{out}}
Line 747 ⟶ 2,291:
48 216 328 120 40 168 336 48 364 180
72 264 348 168 400 120 232 132 178 120</pre>
 
=={{header|Quackery}}==
 
<code>primefactors</code> is defined at [[Prime decomposition#Quackery]].
 
<code>lcm</code> is defined at [[Least common multiple#Quackery]].
 
<syntaxhighlight lang="Quackery"> [ dip number$
over size -
space swap of
swap join echo$ ] is recho ( n n --> )
 
[ witheach
[ 4 recho
i^ 1+ 10 mod
0 = if cr ] ] is prettyecho ( [ --> )
 
[ primefactors size 1 = ] is isprime ( n --> b )
 
[ dup [] = if done
[] [] rot
witheach
[ over [] = iff
join done
over 0 peek over = iff
join done
dip [ nested join ]
nested ]
nested join ] is runs ( [ --> [ )
 
[ stack ] is modulus ( --> s )
 
[ dip dup 1 - **
swap dup 2 < iff
[ 2drop 1 ] done
modulus put
0 temp put
0 1
[ 1 temp tally
tuck +
modulus share mod
dup 1 = until
over 0 = until ]
2drop
modulus release
temp take * ] is pisanoprime ( n n --> n )
 
[ dup 2 < iff
[ drop 1 ] done
primefactors
runs
[] swap
witheach
[ dup 0 peek
swap size
pisanoprime
join ]
behead swap
witheach lcm ] is pisano ( n --> n )
 
[] 15 times
[ i^ isprime if
[ i^ 2 pisanoprime
join ] ]
prettyecho
cr cr
[] 180 times
[ i^ isprime if
[ i^ 1 pisanoprime
join ] ]
prettyecho
cr cr
[] 180 times
[ i^ 1+ pisano join ]
prettyecho</syntaxhighlight>
 
{{out}}
 
<pre> 6 24 100 112 110 364
 
3 8 20 16 10 28 36 18 48 14
30 76 40 88 32 108 58 60 136 70
148 78 168 44 196 50 208 72 108 76
256 130 276 46 148 50 316 328 336 348
178
 
1 3 8 6 20 24 16 12 24 60
10 24 28 48 40 24 36 24 18 60
16 30 48 24 100 84 72 48 14 120
30 48 40 36 80 24 76 18 56 60
40 48 88 30 120 48 32 24 112 300
72 84 108 72 20 48 72 42 58 120
60 30 48 96 140 120 136 36 48 240
70 24 148 228 200 18 80 168 78 120
216 120 168 48 180 264 56 60 44 120
112 48 120 96 180 48 196 336 120 300
50 72 208 84 80 108 72 72 108 60
152 48 76 72 240 42 168 174 144 120
110 60 40 30 500 48 256 192 88 420
130 120 144 408 360 36 276 48 46 240
32 210 140 24 140 444 112 228 148 600
50 36 72 240 60 168 316 78 216 240
48 216 328 120 40 168 336 48 364 180
72 264 348 168 400 120 232 132 178 120
</pre>
 
=={{header|Raku}}==
(formerly Perl 6)
{{works with|Rakudo|2020.02}}
Didn't bother making two differently named routines, just made a multi that will auto dispatch to the correct candidate.
<syntaxhighlight lang="raku" line>use Prime::Factor;
 
constant @fib := 1,1,*+*…*;
 
my %cache;
 
multi pisano-period (Int $p where *.is-prime, Int $k where * > 0 = 1) {
return %cache{"$p|$k"} if %cache{"$p|$k"};
my $fibmod = @fib.map: * % $p**$k;
%cache{"$p|$k"} = (1..*).first: { !$fibmod[$_-1] and ($fibmod[$_] == 1) }
}
 
multi pisano-period (Int $p where * > 0 ) {
[lcm] prime-factors($p).Bag.map: { samewith .key, .value }
}
 
 
put "Pisano period (p, 2) for primes less than 50";
put (map { pisano-period($_, 2) }, ^50 .grep: *.is-prime )».fmt('%4d');
 
put "\nPisano period (p, 1) for primes less than 180";
.put for (map { pisano-period($_, 1) }, ^180 .grep: *.is-prime )».fmt('%4d').batch(15);
 
put "\nPisano period (p, 1) for integers 1 to 180";
.put for (1..180).map( { pisano-period($_) } )».fmt('%4d').batch(15);</syntaxhighlight>
{{out}}
<pre>Pisano period (p, 2) for primes less than 50
6 24 100 112 110 364 612 342 1104 406 930 2812 1640 3784 1504
 
Pisano period (p, 1) for primes less than 180
3 8 20 16 10 28 36 18 48 14 30 76 40 88 32
108 58 60 136 70 148 78 168 44 196 50 208 72 108 76
256 130 276 46 148 50 316 328 336 348 178
 
Pisano period (p, 1) for integers 1 to 180
1 3 8 6 20 24 16 12 24 60 10 24 28 48 40
24 36 24 18 60 16 30 48 24 100 84 72 48 14 120
30 48 40 36 80 24 76 18 56 60 40 48 88 30 120
48 32 24 112 300 72 84 108 72 20 48 72 42 58 120
60 30 48 96 140 120 136 36 48 240 70 24 148 228 200
18 80 168 78 120 216 120 168 48 180 264 56 60 44 120
112 48 120 96 180 48 196 336 120 300 50 72 208 84 80
108 72 72 108 60 152 48 76 72 240 42 168 174 144 120
110 60 40 30 500 48 256 192 88 420 130 120 144 408 360
36 276 48 46 240 32 210 140 24 140 444 112 228 148 600
50 36 72 240 60 168 316 78 216 240 48 216 328 120 40
168 336 48 364 180 72 264 348 168 400 120 232 132 178 120</pre>
 
=={{header|REXX}}==
<langsyntaxhighlight lang="rexx">/*REXX pgm calculates pisano period for a range of N, and pisanoPrime(N,m) [for primes]*/
numeric digits 500 /*ensure enough decimal digits for Fib.*/
parse arg lim1lim.1 lim2 lim3lim.2 lim.3 . /*obtain optional arguments from the CL*/
if lim1lim.1=='' | lim1lim.1=="," then lim1lim.1= 15 - 1 /*Not specified? Then use the default.*/
if lim2lim.2=='' | lim2lim.2=="," then lim2lim.2= 180 - 1 /* " " " " " " */
if lim3lim.3=='' | lim3lim.3=="," then lim3lim.3= 180 /* " " " " " " */
call fibFib /*generate some " " Fibonacci numbers. */
do i=1 for max(lim1lim.1, lim2lim.2, lim3lim.3); call pisano(i) /*find some pisano #speriods.*/
end /*i*/; w= length(i)
 
do pj=1 for lim12; if#= \isPrimeword(p)2 1, then iterate /*Not prime? Then skip this number*/j)
do p=1 for lim.j; if \isPrime(p) then iterate /*Not prime? Skip this number.*/
say ' pisanoPrime('right(p, length(lim1))", 2) = "right(pisanoPrime(p, 2), 5)
say ' pisanoPrime('right(p, w)", "#') = 'right( pisanoPrime(p, #), 5)
end /*pp*/
end /*p*/; say
say
end /*j*/
do p=1 for lim2; if \isPrime(p) then iterate /*Not prime? Then skip this number*/
 
say ' pisanoPrime('right(p, length(lim2))", 1) = "right(pisanoPrime(p, 1), 5)
say center(' pisano numbers for 1──►'lim.3" ", 20*4 - 1, "═") /*display a title.*/
end /*pp*/
say
say center(' pisano numbers for 1──►'lim3" ", 20*4 - 1, "═") /*display a title. */
$=
do j=1 for lim3lim.3; $= $ right(@.j, 3w) /*append pisano number to the $ list.*/
if j//20==0 then do; say substr($, 2); $=; end /*only display twenty20 numbers to a line*/
end end/*j*/
end
say substr($, 2) /*possible display any residuals──►term*/
exit 0 /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
isPrimefib: procedure expose fib.; parse arg #x; iffib.=.; #<2 then return 0; if wordpos(#,x==''2 3 5 7 11')\==0 then returnx= 11000
fib.0= 0; fib.1= 1; if #//2==0 then return 0; do k=3 by 2 while k*k<=#; if #//kfib.x\==0. then return 0fib.x
do k=2 for x-1; a= k-1; b= k-2; end /* fib.k*/= fib.a + fib.b
return 1 end /*primalityk*/; test for smallish primesreturn fib. */k
/*──────────────────────────────────────────────────────────────────────────────────────*/
fibisPrime: procedureparse exposearg fib.n; parseif argn<11 x; fib.=.;then ifreturn pos(n, x==''2 3 5 7')>0; if n//2==0 then x=return 10000
fib.0= 0; fib.1= 1; do k=3 by 2 while k*k<=n; if n//k==0 then return 0; end /*k*/; if fib.x\==. then return fib.x1
do j=2 for x-1; _= j-1; __= j-2; fib.j= fib.__ + fib._
end /*j*/; return fib.j
/*──────────────────────────────────────────────────────────────────────────────────────*/
pisano: procedure expose @. fib.; parse arg m; if m==1 then do; @.m=1; return 1; end
do jk=1; _= jk+1; if fib.jk//m==0 & fib._//m==1 then leave
end /*jk*/; @.m= k; return k
@.m= j; return j
/*──────────────────────────────────────────────────────────────────────────────────────*/
pisanoPrime: procedure expose @. fib.; parse arg m,n; return pisano(m**(n-1) * pisano(m)</langsyntaxhighlight>
{{out|output|text=&nbsp; when using the default inputs:}}
 
Line 797 ⟶ 2,492:
 
<pre style="font-size:75%">
pisanoPrime( 2, 2) = 6
pisanoPrime( 3, 2) = 24
pisanoPrime( 5, 2) = 100
pisanoPrime( 7, 2) = 112
pisanoPrime( 11, 2) = 110
pisanoPrime( 13, 2) = 364
 
pisanoPrime( 2, 1) = 3
Line 856 ⟶ 2,551:
32 210 140 24 140 444 112 228 148 600 50 36 72 240 60 168 316 78 216 240
48 216 328 120 40 168 336 48 364 180 72 264 348 168 400 120 232 132 178 120
</pre>
 
=={{header|RPL}}==
{{works with|HP|49}}
« → n
« 1 0 1
'''DO''' ROT 1 + UNROT SWAP OVER + n MOD
'''UNTIL''' DUP2 + 1 == '''END'''
DROP2
» » '<span style="color:blue">PSNPERIOD</span>' STO ''<span style="color:grey">@ ( n → period(n) )</span>''
« OVER <span style="color:blue">PSNPERIOD</span> UNROT 1 - ^ *
» '<span style="color:blue">PSNPRIME</span>' STO ''<span style="color:grey">@ ( p k → pisano(p^k) )</span>''
« '''IF''' DUP 1 ≠ '''THEN'''
FACTORS 1
1 PICK3 SIZE '''FOR''' j
OVER j GETI UNROT GET <span style="color:blue">PSNPRIME</span> LCM
2 '''STEP'''
NIP
'''END'''
» '<span style="color:blue">PISANO</span>' STO ''<span style="color:grey">@ ( n → pisano(n) )</span>''
« { } 2
'''WHILE''' DUP 15 < '''REPEAT'''
DUP 2 <span style="color:blue">PSNPRIME</span> ROT SWAP + SWAP NEXTPRIME
'''END''' DROP
'''WHILE''' DUP 180 < '''REPEAT'''
DUP 1 <span style="color:blue">PSNPRIME</span> ROT SWAP + SWAP NEXTPRIME
'''END''' DROP
« n <span style="color:blue">PISANO</span> » 'n' 1 180 1 SEQ
» '<span style="color:blue">TASK</span>' STO
{{out}}
<pre>
3: { 6 24 100 112 110 364 }
2: { 3 8 20 16 10 28 36 18 48 14 30 76 40 88 32 108 58 60 136 70 148 78 168 44 196 50 208 72 108 76 256 130 276 46 148 50 316 328 336 348 178 }
1: { 1 3 8 6 20 24 16 12 24 60 10 24 28 48 40 24 36 24 18 60 16 30 48 24 100 84 72 48 14 120 30 48 40 36 80 24 76 18 56 60 40 48 88 30 120 48 32 24 112 300 72 84 108 72 20 48 72 42 58 120 60 30 48 96 140 120 136 36 48 240 70 24 148 228 200 18 80 168 78 120 216 120 168 48 180 264 56 60 44 120 112 48 120 96 180 48 196 336 120 300 50 72 208 84 80 108 72 72 108 60 152 48 76 72 240 42 168 174 144 120 110 60 40 30 500 48 256 192 88 420 130 120 144 408 360 36 276 48 46 240 32 210 140 24 140 444 112 228 148 600 50 36 72 240 60 168 316 78 216 240 48 216 328 120 40 168 336 48 364 180 72 264 348 168 400 120 232 132 178 120 }
</pre>
 
=={{header|Sidef}}==
<langsyntaxhighlight lang="ruby">func pisano_period_pp(p,k) is cached {
 
assert(k.is_pos, "k = #{k} must be positive")
Line 882 ⟶ 2,614:
say 180.primes.map {|p| pisano_period_pp(p, 1) }
 
say "\nPisano periods for integers n from 21 to 180:"
say pisano_period.map(21..180)</langsyntaxhighlight>
{{out}}
<pre>
Line 892 ⟶ 2,624:
[3, 8, 20, 16, 10, 28, 36, 18, 48, 14, 30, 76, 40, 88, 32, 108, 58, 60, 136, 70, 148, 78, 168, 44, 196, 50, 208, 72, 108, 76, 256, 130, 276, 46, 148, 50, 316, 328, 336, 348, 178]
 
Pisano periods for integers n from 21 to 180:
[1, 3, 8, 6, 20, 24, 16, 12, 24, 60, 10, 24, 28, 48, 40, 24, 36, 24, 18, 60, 16, 30, 48, 24, 100, 84, 72, 48, 14, 120, 30, 48, 40, 36, 80, 24, 76, 18, 56, 60, 40, 48, 88, 30, 120, 48, 32, 24, 112, 300, 72, 84, 108, 72, 20, 48, 72, 42, 58, 120, 60, 30, 48, 96, 140, 120, 136, 36, 48, 240, 70, 24, 148, 228, 200, 18, 80, 168, 78, 120, 216, 120, 168, 48, 180, 264, 56, 60, 44, 120, 112, 48, 120, 96, 180, 48, 196, 336, 120, 300, 50, 72, 208, 84, 80, 108, 72, 72, 108, 60, 152, 48, 76, 72, 240, 42, 168, 174, 144, 120, 110, 60, 40, 30, 500, 48, 256, 192, 88, 420, 130, 120, 144, 408, 360, 36, 276, 48, 46, 240, 32, 210, 140, 24, 140, 444, 112, 228, 148, 600, 50, 36, 72, 240, 60, 168, 316, 78, 216, 240, 48, 216, 328, 120, 40, 168, 336, 48, 364, 180, 72, 264, 348, 168, 400, 120, 232, 132, 178, 120]
</pre>
 
By assuming that '''Wall-Sun-Sun primes''' do not exist, we can compute the Pisano period more efficiently, as illustrated below on Fermat numbers '''F_n = 2^(2^n) + 1''':
<langsyntaxhighlight lang="ruby">func pisano_period_pp(p, k=1) {
(p - kronecker(5, p)).divisors.first_by {|d| fibmod(d, p) == 0 } * p**(k-1)
}
Line 918 ⟶ 2,650:
for k in (1..8) {
say ("Pisano(F_#{k}) = ", pisano_period(2**(2**k) + 1))
}</langsyntaxhighlight>
{{out}}
<pre>
Line 929 ⟶ 2,661:
Pisano(F_7) = 28356863910078205764000346543980814080
Pisano(F_8) = 3859736307910542962840356678888855900560939475751238269689837480239178278912
</pre>
 
=={{header|Wren}}==
{{trans|Go}}
{{libheader|Wren-math}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="wren">import "./math" for Int
import "./fmt" for Fmt
 
// Calculates the Pisano period of 'm' from first principles.
var pisanoPeriod = Fn.new { |m|
var p = 0
var c = 1
for (i in 0...m*m) {
var t = p
p = c
c = (t + c) % m
if (p == 0 && c == 1) return i + 1
}
return 1
}
 
// Calculates the Pisano period of p^k where 'p' is prime and 'k' is a positive integer.
var pisanoPrime = Fn.new { |p, k|
if (!Int.isPrime(p) || k == 0) return 0 // can't do this one
return p.pow(k-1) * pisanoPeriod.call(p)
}
 
// Calculates the Pisano period of 'm' using pisanoPrime.
var pisano = Fn.new { |m|
var primes = Int.primeFactors(m)
var primePowers = {}
for (p in primes) {
var v = primePowers[p]
primePowers[p] = v ? v + 1 : 1
}
var pps = []
for (me in primePowers) pps.add(pisanoPrime.call(me.key, me.value))
if (pps.count == 0) return 1
if (pps.count == 1) return pps[0]
var f = pps[0]
var i = 1
while (i < pps.count) {
f = Int.lcm(f, pps[i])
i = i + 1
}
return f
}
 
for (p in 2..14) {
var pp = pisanoPrime.call(p, 2)
if (pp > 0) Fmt.print("pisanoPrime($2d: 2) = $d", p, pp)
}
System.print()
for (p in 2..179) {
var pp = pisanoPrime.call(p, 1)
if (pp > 0) Fmt.print("pisanoPrime($3d: 1) = $d", p, pp)
}
System.print("\npisano(n) for integers 'n' from 1 to 180 are:")
for (n in 1..180) {
Fmt.write("$3d ", pisano.call(n))
if (n != 1 && n%15 == 0) System.print()
}
System.print()</syntaxhighlight>
 
{{out}}
<pre>
pisanoPrime( 2: 2) = 6
pisanoPrime( 3: 2) = 24
pisanoPrime( 5: 2) = 100
pisanoPrime( 7: 2) = 112
pisanoPrime(11: 2) = 110
pisanoPrime(13: 2) = 364
 
pisanoPrime( 2: 1) = 3
pisanoPrime( 3: 1) = 8
pisanoPrime( 5: 1) = 20
pisanoPrime( 7: 1) = 16
pisanoPrime( 11: 1) = 10
pisanoPrime( 13: 1) = 28
pisanoPrime( 17: 1) = 36
pisanoPrime( 19: 1) = 18
pisanoPrime( 23: 1) = 48
pisanoPrime( 29: 1) = 14
pisanoPrime( 31: 1) = 30
pisanoPrime( 37: 1) = 76
pisanoPrime( 41: 1) = 40
pisanoPrime( 43: 1) = 88
pisanoPrime( 47: 1) = 32
pisanoPrime( 53: 1) = 108
pisanoPrime( 59: 1) = 58
pisanoPrime( 61: 1) = 60
pisanoPrime( 67: 1) = 136
pisanoPrime( 71: 1) = 70
pisanoPrime( 73: 1) = 148
pisanoPrime( 79: 1) = 78
pisanoPrime( 83: 1) = 168
pisanoPrime( 89: 1) = 44
pisanoPrime( 97: 1) = 196
pisanoPrime(101: 1) = 50
pisanoPrime(103: 1) = 208
pisanoPrime(107: 1) = 72
pisanoPrime(109: 1) = 108
pisanoPrime(113: 1) = 76
pisanoPrime(127: 1) = 256
pisanoPrime(131: 1) = 130
pisanoPrime(137: 1) = 276
pisanoPrime(139: 1) = 46
pisanoPrime(149: 1) = 148
pisanoPrime(151: 1) = 50
pisanoPrime(157: 1) = 316
pisanoPrime(163: 1) = 328
pisanoPrime(167: 1) = 336
pisanoPrime(173: 1) = 348
pisanoPrime(179: 1) = 178
 
pisano(n) for integers 'n' from 1 to 180 are:
1 3 8 6 20 24 16 12 24 60 10 24 28 48 40
24 36 24 18 60 16 30 48 24 100 84 72 48 14 120
30 48 40 36 80 24 76 18 56 60 40 48 88 30 120
48 32 24 112 300 72 84 108 72 20 48 72 42 58 120
60 30 48 96 140 120 136 36 48 240 70 24 148 228 200
18 80 168 78 120 216 120 168 48 180 264 56 60 44 120
112 48 120 96 180 48 196 336 120 300 50 72 208 84 80
108 72 72 108 60 152 48 76 72 240 42 168 174 144 120
110 60 40 30 500 48 256 192 88 420 130 120 144 408 360
36 276 48 46 240 32 210 140 24 140 444 112 228 148 600
50 36 72 240 60 168 316 78 216 240 48 216 328 120 40
168 336 48 364 180 72 264 348 168 400 120 232 132 178 120
</pre>
 
=={{header|zkl}}==
{{libheader|GMP}} GNU Multiple Precision Arithmetic Library for prime testing
<langsyntaxhighlight lang="zkl">var [const] BI=Import("zklBigNum"); // libGMP
 
fcn pisanoPeriod(p){
Line 947 ⟶ 2,808:
_assert_(BI(p).probablyPrime(), "%s is not a prime number".fmt(p));
pisanoPeriod(p.pow(k))
}</langsyntaxhighlight>
<langsyntaxhighlight lang="zkl">println("Pisano period (p, 2) for primes less than 50:");
[1..50].pump(List,BI,"probablyPrime",Void.Filter, pisanoPrime.fp1(2))
.concat(" "," ").println();
Line 954 ⟶ 2,815:
println("Pisano period (p, 1) for primes less than 180:");
[1..180].pump(List,BI,"probablyPrime",Void.Filter, pisanoPrime.fp1(1))
.pump(Void,T(Void.Read,14,False),fcn{ vm.arglist.apply("%4d".fmt).concat().println() });</langsyntaxhighlight>
{{out}}
<pre>
Line 964 ⟶ 2,825:
256 130 276 46 148 50 316 328 336 348 178
</pre>
<langsyntaxhighlight lang="zkl">fcn pisano(m){
primeFactors(m).pump(Dictionary().incV) //18 --> (2,3,3) --> ("2":1, "3":2)
.reduce(fcn(z,[(k,v])){ lcm(z,pisanoPrime(k.toInt(),v)) },1)
Line 982 ⟶ 2,843:
if(n!=m) acc.append(n/m); // opps, missed last factor
else acc;
}</langsyntaxhighlight>
<langsyntaxhighlight lang="zkl">println("Pisano(m) for integers 1 to 180:");
[1..180].pump(List, pisano, "%4d".fmt)
.pump(Void,T(Void.Read,14,False),fcn{ vm.arglist.concat().println() });</langsyntaxhighlight>
{{out}}
<pre>
Chkas
1,983

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/298806...361479"