## Pisano periods - fun with Fibonacci numbers

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.

 Category Mathematics Category Toys