Pisano period: Difference between revisions
Content added Content deleted
m (→{{header|Phix}}: syntax coloured) |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
Line 42: | Line 42: | ||
{{trans|Nim}} |
{{trans|Nim}} |
||
< |
<syntaxhighlight lang="11l">F lcm(m, n) |
||
R m I/ gcd(m, n) * n |
R m I/ gcd(m, n) * n |
||
Line 109: | Line 109: | ||
print(‘pisano(n) for integers 'n' from 1 to 180 are:’) |
print(‘pisano(n) for integers 'n' from 1 to 180 are:’) |
||
L(n) 1..180 |
L(n) 1..180 |
||
print(‘#3’.format(pisano(n)), end' I n % 15 == 0 {"\n"} E ‘ ’)</ |
print(‘#3’.format(pisano(n)), end' I n % 15 == 0 {"\n"} E ‘ ’)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 179: | Line 179: | ||
=={{header|Factor}}== |
=={{header|Factor}}== |
||
{{works with|Factor|0.99 2020-01-23}} |
{{works with|Factor|0.99 2020-01-23}} |
||
< |
<syntaxhighlight lang="factor">USING: formatting fry grouping io kernel math math.functions |
||
math.primes math.primes.factors math.ranges sequences ; |
math.primes math.primes.factors math.ranges sequences ; |
||
Line 204: | Line 204: | ||
"n pisano for integers 'n' from 2 to 180:" print |
"n pisano for integers 'n' from 2 to 180:" print |
||
2 180 [a,b] [ pisano ] map 15 group |
2 180 [a,b] [ pisano ] map 15 group |
||
[ [ "%3d " printf ] each nl ] each</ |
[ [ "%3d " printf ] each nl ] each</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre style="height:45ex"> |
<pre style="height:45ex"> |
||
Line 272: | Line 272: | ||
=={{header|Go}}== |
=={{header|Go}}== |
||
< |
<syntaxhighlight lang="go">package main |
||
import "fmt" |
import "fmt" |
||
Line 407: | Line 407: | ||
} |
} |
||
fmt.Println() |
fmt.Println() |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 476: | Line 476: | ||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
< |
<syntaxhighlight lang="haskell">import qualified Data.Text as T |
||
main = do |
main = do |
||
Line 630: | Line 630: | ||
pisanoConjecture m = foldl1 lcm . map (uncurry pisanoPrime') $ factor m |
pisanoConjecture m = foldl1 lcm . map (uncurry pisanoPrime') $ factor m |
||
where |
where |
||
pisanoPrime' p k = (p ^ (k - 1)) * pisanoPeriod p</ |
pisanoPrime' p k = (p ^ (k - 1)) * pisanoPeriod p</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>PisanoPrime(p,2) for prime p lower than 15 |
<pre>PisanoPrime(p,2) for prime p lower than 15 |
||
Line 661: | Line 661: | ||
Use efficient algorithm to calculate period. |
Use efficient algorithm to calculate period. |
||
<syntaxhighlight lang="java"> |
|||
<lang Java> |
|||
import java.util.ArrayList; |
import java.util.ArrayList; |
||
import java.util.Collections; |
import java.util.Collections; |
||
Line 925: | Line 925: | ||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,001: | Line 1,001: | ||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
< |
<syntaxhighlight lang="julia">using Primes |
||
const pisanos = Dict{Int, Int}() |
const pisanos = Dict{Int, Int}() |
||
Line 1,035: | Line 1,035: | ||
println("\nPisano(n) for n from 2 to 180:\n", [pisano(i) for i in 2:180]) |
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]) |
println("\nPisano(n) using pisanoPrime for n from 2 to 180:\n", [pisanotask(i) for i in 2:180]) |
||
</ |
</syntaxhighlight>{{out}} |
||
<pre> |
<pre> |
||
pisanoPrime(2, 2) = 6 |
pisanoPrime(2, 2) = 6 |
||
Line 1,094: | Line 1,094: | ||
=={{header|Nim}}== |
=={{header|Nim}}== |
||
{{trans|Go}} |
{{trans|Go}} |
||
< |
<syntaxhighlight lang="nim">import math, strformat, tables |
||
func primes(n: Positive): seq[int] = |
func primes(n: Positive): seq[int] = |
||
Line 1,164: | Line 1,164: | ||
echo "pisano(n) for integers 'n' from 1 to 180 are:" |
echo "pisano(n) for integers 'n' from 1 to 180 are:" |
||
for n in 1..180: |
for n in 1..180: |
||
stdout.write &"{pisano(n):3}", if n mod 15 == 0: '\n' else: ' '</ |
stdout.write &"{pisano(n):3}", if n mod 15 == 0: '\n' else: ' '</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,233: | Line 1,233: | ||
{{trans|Sidef}} |
{{trans|Sidef}} |
||
{{libheader|ntheory}} |
{{libheader|ntheory}} |
||
< |
<syntaxhighlight lang="perl">use strict; |
||
use warnings; |
use warnings; |
||
use feature 'say'; |
use feature 'say'; |
||
Line 1,254: | Line 1,254: | ||
say "Pisano periods for squares of primes p <= 50:\n", display( map { pisano_period_pp($_, 2) } @{primes(1, 50)} ), |
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)} ), |
"\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 );</ |
"\n\nPisano periods for integers n from 1 to 180:\n", display( map { pisano_period ($_ ) } 1..180 );</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>Pisano periods for squares of primes p <= 50: |
<pre>Pisano periods for squares of primes p <= 50: |
||
Line 1,279: | Line 1,279: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
<!--< |
<!--<syntaxhighlight lang="phix">(phixonline)--> |
||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
<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: #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> |
||
Line 1,338: | Line 1,338: | ||
<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;">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> |
<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}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,367: | Line 1,367: | ||
Uses the [[wp:SymPy|SymPy]] library. |
Uses the [[wp:SymPy|SymPy]] library. |
||
< |
<syntaxhighlight lang="python">from sympy import isprime, lcm, factorint, primerange |
||
from functools import reduce |
from functools import reduce |
||
Line 1,406: | Line 1,406: | ||
print("\nPisano period (p) for integers 1 to 180") |
print("\nPisano period (p) for integers 1 to 180") |
||
for i in range(1, 181): |
for i in range(1, 181): |
||
print(" %3d" % pisano2(i), end="" if i % 10 else "\n")</ |
print(" %3d" % pisano2(i), end="" if i % 10 else "\n")</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,439: | Line 1,439: | ||
{{works with|Rakudo|2020.02}} |
{{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. |
Didn't bother making two differently named routines, just made a multi that will auto dispatch to the correct candidate. |
||
<lang |
<syntaxhighlight lang="raku" line>use Prime::Factor; |
||
constant @fib := 1,1,*+*…*; |
constant @fib := 1,1,*+*…*; |
||
Line 1,463: | Line 1,463: | ||
put "\nPisano period (p, 1) for integers 1 to 180"; |
put "\nPisano period (p, 1) for integers 1 to 180"; |
||
.put for (1..180).map( { pisano-period($_) } )».fmt('%4d').batch(15);</ |
.put for (1..180).map( { pisano-period($_) } )».fmt('%4d').batch(15);</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>Pisano period (p, 2) for primes less than 50 |
<pre>Pisano period (p, 2) for primes less than 50 |
||
Line 1,488: | Line 1,488: | ||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
< |
<syntaxhighlight 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.*/ |
numeric digits 500 /*ensure enough decimal digits for Fib.*/ |
||
parse arg lim.1 lim.2 lim.3 . /*obtain optional arguments from the CL*/ |
parse arg lim.1 lim.2 lim.3 . /*obtain optional arguments from the CL*/ |
||
Line 1,524: | Line 1,524: | ||
end /*k*/; @.m= k; return k |
end /*k*/; @.m= k; return k |
||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
||
pisanoPrime: procedure expose @. fib.; parse arg m,n; return m**(n-1) * pisano(m)</ |
pisanoPrime: procedure expose @. fib.; parse arg m,n; return m**(n-1) * pisano(m)</syntaxhighlight> |
||
{{out|output|text= when using the default inputs:}} |
{{out|output|text= when using the default inputs:}} |
||
Line 1,592: | Line 1,592: | ||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
< |
<syntaxhighlight lang="ruby">func pisano_period_pp(p,k) is cached { |
||
assert(k.is_pos, "k = #{k} must be positive") |
assert(k.is_pos, "k = #{k} must be positive") |
||
Line 1,616: | Line 1,616: | ||
say "\nPisano periods for integers n from 1 to 180:" |
say "\nPisano periods for integers n from 1 to 180:" |
||
say pisano_period.map(1..180)</ |
say pisano_period.map(1..180)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,630: | Line 1,630: | ||
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''': |
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''': |
||
< |
<syntaxhighlight lang="ruby">func pisano_period_pp(p, k=1) { |
||
(p - kronecker(5, p)).divisors.first_by {|d| fibmod(d, p) == 0 } * p**(k-1) |
(p - kronecker(5, p)).divisors.first_by {|d| fibmod(d, p) == 0 } * p**(k-1) |
||
} |
} |
||
Line 1,651: | Line 1,651: | ||
for k in (1..8) { |
for k in (1..8) { |
||
say ("Pisano(F_#{k}) = ", pisano_period(2**(2**k) + 1)) |
say ("Pisano(F_#{k}) = ", pisano_period(2**(2**k) + 1)) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,668: | Line 1,668: | ||
{{libheader|Wren-math}} |
{{libheader|Wren-math}} |
||
{{libheader|Wren-fmt}} |
{{libheader|Wren-fmt}} |
||
< |
<syntaxhighlight lang="ecmascript">import "/math" for Int |
||
import "/fmt" for Fmt |
import "/fmt" for Fmt |
||
Line 1,725: | Line 1,725: | ||
if (n != 1 && n%15 == 0) System.print() |
if (n != 1 && n%15 == 0) System.print() |
||
} |
} |
||
System.print()</ |
System.print()</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,795: | Line 1,795: | ||
=={{header|zkl}}== |
=={{header|zkl}}== |
||
{{libheader|GMP}} GNU Multiple Precision Arithmetic Library for prime testing |
{{libheader|GMP}} GNU Multiple Precision Arithmetic Library for prime testing |
||
< |
<syntaxhighlight lang="zkl">var [const] BI=Import("zklBigNum"); // libGMP |
||
fcn pisanoPeriod(p){ |
fcn pisanoPeriod(p){ |
||
Line 1,809: | Line 1,809: | ||
_assert_(BI(p).probablyPrime(), "%s is not a prime number".fmt(p)); |
_assert_(BI(p).probablyPrime(), "%s is not a prime number".fmt(p)); |
||
pisanoPeriod(p.pow(k)) |
pisanoPeriod(p.pow(k)) |
||
}</ |
}</syntaxhighlight> |
||
< |
<syntaxhighlight lang="zkl">println("Pisano period (p, 2) for primes less than 50:"); |
||
[1..50].pump(List,BI,"probablyPrime",Void.Filter, pisanoPrime.fp1(2)) |
[1..50].pump(List,BI,"probablyPrime",Void.Filter, pisanoPrime.fp1(2)) |
||
.concat(" "," ").println(); |
.concat(" "," ").println(); |
||
Line 1,816: | Line 1,816: | ||
println("Pisano period (p, 1) for primes less than 180:"); |
println("Pisano period (p, 1) for primes less than 180:"); |
||
[1..180].pump(List,BI,"probablyPrime",Void.Filter, pisanoPrime.fp1(1)) |
[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() });</ |
.pump(Void,T(Void.Read,14,False),fcn{ vm.arglist.apply("%4d".fmt).concat().println() });</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,826: | Line 1,826: | ||
256 130 276 46 148 50 316 328 336 348 178 |
256 130 276 46 148 50 316 328 336 348 178 |
||
</pre> |
</pre> |
||
< |
<syntaxhighlight lang="zkl">fcn pisano(m){ |
||
primeFactors(m).pump(Dictionary().incV) //18 --> (2,3,3) --> ("2":1, "3":2) |
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) |
.reduce(fcn(z,[(k,v])){ lcm(z,pisanoPrime(k.toInt(),v)) },1) |
||
Line 1,844: | Line 1,844: | ||
if(n!=m) acc.append(n/m); // opps, missed last factor |
if(n!=m) acc.append(n/m); // opps, missed last factor |
||
else acc; |
else acc; |
||
}</ |
}</syntaxhighlight> |
||
< |
<syntaxhighlight lang="zkl">println("Pisano(m) for integers 1 to 180:"); |
||
[1..180].pump(List, pisano, "%4d".fmt) |
[1..180].pump(List, pisano, "%4d".fmt) |
||
.pump(Void,T(Void.Read,14,False),fcn{ vm.arglist.concat().println() });</ |
.pump(Void,T(Void.Read,14,False),fcn{ vm.arglist.concat().println() });</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |