Pisano period: Difference between revisions

Content added Content deleted
Line 1,543: Line 1,543:
48 216 328 120 40 168 336 48 364 180
48 216 328 120 40 168 336 48 364 180
72 264 348 168 400 120 232 132 178 120
72 264 348 168 400 120 232 132 178 120
</pre>

=={{header|jq}}==
'''Adapted from [[#Wren|Wren]]'''

'''Works with jq, the C implementation of jq'''

'''Works with gojq, the Go implementation of jq'''
<syntaxhighlight lang="jq">
### In case gojq is used:
# Require $n > 0
def _nwise($n):
def _n: if length <= $n then . else .[:$n] , (.[$n:] | _n) end;
if $n <= 0 then "nwise: argument should be non-negative" else _n end;

### Generic utilities

def lpad($len): tostring | ($len - length) as $l | (" " * $l) + .;

def lcm($m; $n):
# The helper function takes advantage of jq's tail-recursion optimization
def _lcm:
# state is [m, n, i]
if (.[2] % .[1]) == 0 then .[2] else (.[0:2] + [.[2] + $m]) | _lcm end;
[$m, $n, $m] | _lcm;

# Preserve integer accuracy as much as the implementation of jq allows
def power($b): . as $in | reduce range(0;$b) as $i (1; . * $in);

def is_prime:
. as $n
| if ($n < 2) then false
elif ($n % 2 == 0) then $n == 2
elif ($n % 3 == 0) then $n == 3
elif ($n % 5 == 0) then $n == 5
elif ($n % 7 == 0) then $n == 7
elif ($n % 11 == 0) then $n == 11
elif ($n % 13 == 0) then $n == 13
elif ($n % 17 == 0) then $n == 17
elif ($n % 19 == 0) then $n == 19
else sqrt as $s
| 23
| until( . > $s or ($n % . == 0); . + 2)
| . > $s
end;

# Emit an array of the prime factors of . in order using a wheel with basis [2, 3, 5]
# e.g. 44 | primeFactors => [2,2,11]
def primeFactors:
def out($i): until (.n % $i != 0; .factors += [$i] | .n = ((.n/$i)|floor) );
if . < 2 then []
else [4, 2, 4, 2, 4, 6, 2, 6] as $inc
| { n: .,
factors: [] }
| out(2)
| out(3)
| out(5)
| .k = 7
| .i = 0
| until(.k * .k > .n;
if .n % .k == 0
then .factors += [.k]
| .n = ((.n/.k)|floor)
else .k += $inc[.i]
| .i = ((.i + 1) % 8)
end)
| if .n > 1 then .factors += [ .n ] else . end
| .factors
end;

# Calculate the Pisano period of . from first principles.
def pisanoPeriod:
. as $m
| {p: 0, c: 1}
| first(foreach range(0; $m*$m) as $i (.;
.p as $t
| .p = .c
| .c = ($t + .c) % $m;
select(.p == 0 and .c == 1) | $i + 1
)) // 1;

# Calculate the Pisano period of $p^$k where $p is prime and $k is a positive integer.
def pisanoPrime($p; $k):
$p
| if (is_prime|not) or $k == 0 then 0 # no can do
else ( power($k-1) * pisanoPeriod )
end;

# Calculate the Pisano period of . using pisanoPrime/2.
def pisano:
. as $m
| (reduce primeFactors[] as $p ({}; .[$p|tostring] += 1)
| to_entries | map([(.key|tonumber), .value]) ) as $primePowers
| (reduce $primePowers[] as [$p, $n] ([];
. + [ pisanoPrime($p;$n) ] ) ) as $pps
| ($pps|length) as $ppsl
| if $ppsl == 0 then 1
elif $ppsl == 1 then $pps[0]
else {f: $pps[0], i: 1}
| until(.i >= $ppsl;
.f = lcm(.f; $pps[.i])
| .i += 1)
| .f
end;

def examples:
(range( 2; 15)
| pisanoPrime(.; 2) as $pp
| select($pp > 0)
| "pisanoPrime(\(.); 2) = \($pp)" ),
"",
(range( 2; 180)
| pisanoPrime(.; 1) as $pp
| select($pp > 0)
| "pisanoPrime(\(.);1) = \($pp)" )
;

examples,
"\npisano(n) for integers 'n' from 1 to 180 are:",
( [range(1; 181) | pisano ]
| _nwise(15)
| map(lpad(3))
| join(" "))
</syntaxhighlight>
{{output}}
<pre style="height:20lh;overflow:auto>
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>
</pre>


Line 1,581: Line 1,769:
println("\nPisano(n) using pisanoPrime for n from 2 to 180:\n", [pisanotask(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])
</syntaxhighlight>{{out}}
</syntaxhighlight>{{out}}
<pre style="height:20lh;overflow:auto>
<pre>
pisanoPrime(2, 2) = 6
pisanoPrime(2, 2) = 6
pisanoPrime(3, 2) = 24
pisanoPrime(3, 2) = 24
Retrieved from "https://rosettacode.org/wiki/Pisano_period"