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.