Pisano period: Difference between revisions

Content added Content deleted

Inline

@@ Line 26: / Line 26: @@
 * &nbsp;[[Least common multiple]]
+=={{header|Go}}==
+<lang go>package main
+import "fmt"
+func gcd(a, b uint) uint {
+    if b == 0 {
+        return a
+    }
+    return gcd(b, a%b)
+}
+func lcm(a, b uint) uint {
+    return a / gcd(a, b) * b
+}
+func ipow(x, p uint) uint {
+    prod := uint(1)
+    for p > 0 {
+        if p&1 != 0 {
+            prod *= x
+        }
+        p >>= 1
+        x *= x
+    }
+    return prod
+}
+// Gets the prime decomposition of n.
+func getPrimes(n uint) []uint {
+    var primes []uint
+    for i := uint(2); i <= n; i++ {
+        div := n / i
+        mod := n % i
+        for mod == 0 {
+            primes = append(primes, i)
+            n = div
+            div = n / i
+            mod = n % i
+        }
+    }
+    return primes
+}
+// Not particularly efficient but suffices here.
+func isPrime(n uint) bool {
+    if n%2 == 0 {
+        return n == 2
+    }
+    if n%3 == 0 {
+        return n == 3
+    }
+    primes := getPrimes(n)
+    if len(primes) == 1 && primes[0] == n {
+        return true
+    }
+    return false
+}
+// Calculates the Pisano period of 'm' from first principles.
+func pisanoPeriod(m uint) uint {
+    var p, c uint = 0, 1
+    for i := uint(0); i < m*m; i++ {
+        p, c = c, (p+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 intege.
+func pisanoPrime(p uint, k uint) uint {
+    if !isPrime(p) || k == 0 {
+        return 0 // can't do this one
+    }
+    return pisanoPeriod(ipow(p, k))
+}
+// Calculates the Pisano period of 'm' using pisanoPrime.
+func pisano(m uint) uint {
+    primes := getPrimes(m)
+    primePowers := make(map[uint]uint)
+    for _, p := range primes {
+        primePowers[p]++
+    }
+    var pps []uint
+    for k, v := range primePowers {
+        pps = append(pps, pisanoPrime(k, v))
+    }
+    if len(pps) == 1 {
+        return pps[0]
+    }
+    f := pps[0]
+    for i := 1; i < len(pps); i++ {
+        f = lcm(f, pps[i])
+    }
+    return f
+}
+func main() {
+    for p := uint(2); p < 15; p++ {
+        pp := pisanoPrime(p, 2)
+        if pp > 0 {
+            fmt.Printf("pisanoPrime(%2d: 2) = %d\n", p, pp)
+        }
+    }
+    fmt.Println()
+    for p := uint(2); p < 180; p++ {
+        pp := pisanoPrime(p, 1)
+        if pp > 0 {
+            fmt.Printf("pisanoPrime(%3d: 1) = %d\n", p, pp)
+        }
+    }
+    fmt.Println()
+    fmt.Println("pisano(n) for integers 'n' from 2 to 180 are:")
+    for n := uint(2); n <= 180; n++ {
+        fmt.Printf("%3d ", pisano(n))
+        if n != 2 && (n-1)%15 == 0 {
+            fmt.Println()
+        }
+    }
+    fmt.Println()
+}</lang>
+{{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 2 to 180 are:
+8   6  20  24  16  12  24  60  10  24  28  48  40  24
+24  18  60  16  30  48  24 100  84  72  48  14 120  30
+40  36  80  24  76  18  56  60  40  48  88  30 120  48
+24 112 300  72  84 108  72  20  48  72  42  58 120  60
+48  96 140 120 136  36  48 240  70  24 148 228 200  18
+168  78 120 216 120 168  48 180 264  56  60  44 120 112
+120  96 180  48 196 336 120 300  50  72 208  84  80 108
+72 108  60 152  48  76  72 240  42 168 174 144 120 110
+40  30 500  48 256 192  88 420 130 120 144 408 360  36
+48  46 240  32 210 140  24 140 444 112 228 148 600  50
+72 240  60 168 316  78 216 240  48 216 328 120  40 168
+48 364 180  72 264 348 168 400 120 232 132 178 120
+</pre>
 =={{header|Julia}}==