Pisano periods - fun with Fibonacci numbers

Difference between version 0 and 1 - Previous - Next
[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.

<<categories>>Mathematics | Toys