Arjen Markus (21 march 2023) We all know "Pi day, right? The 14th of march. The Dutch firm Vortech presents a yearly challenge to celebrate this date and this year it is about Pisano periods - https://www.vortech.nl/en/the-pi-day-challenge-2023/ . They ask you to send in your quickest and shortest Python code to determine the Pisano period of a given number n. You can read about these numbers on this page: https://en.wikipedia.org/wiki/Pisano_period/ . I read it to get acquainted with this idea and among others it contains the interesting bit of information that the Pisano period for a number n never exceeds 6n. You can get it even sharper if n is not of the form 2*5**m.
Well, the challenge now is to find the period within these 6n (or 4n) possibilities. It turns out to be rather easy, as shown in the code below.
# pisano.tcl --
# Try to determine the Pisano period - Fibonacci numbers modulo n give a periodic sequence
#
# Generate the first 12n Fibonacci numbers modulo n: this should always contain at least two copies
# of the periodic sequence.
set n [lindex $argv 0]
set nterms [expr {6 * $n}]
set fnm2 0
set fnm1 1
set residues [list $fnm2 $fnm1]
for {set i 2} {$i < $nterms} {incr i} {
lappend residues [expr {($fnm1 + $fnm2) % $n}]
set fnm2 $fnm1
set fnm1 [lindex $residues end]
}
puts $residues
puts [llength $residues]
# Now determine the period:
# - Start with the smallest sublist and check if it is repeated
# - If not, increase the length until you find a sublist that is repeated (we know it will be there)
#
for {set period 1} {$period <= 6*$n} {incr period} {
set repeat [expr {6*$n / $period}]
set repeatedList [concat {*}[lrepeat $repeat [lrange $residues 0 [expr {$period-1}]]]]
set checkRange [expr {[llength $repeatedList] - 1}]
#puts "$repeatedList -- [lrange $residues 0 $checkRange]"
if { $repeatedList == [lrange $residues 0 $checkRange] } {
puts "$period -- [lrange $residues 0 [expr {$period-1}]]"
break
}
}My solution is probably hors concours: it is not in Python and I have no idea how fast it is. It is short though :). If you take out all the comments and empty lines, as well as the unnecessary puts's, you end up with 19 lines of code.