Pisano period: Difference between revisions

=={{header|11l}}==

{{trans|Nim}}

<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 ‘ ’)</lang>

{{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>