The Fibonacci series starts with [0, 1, 1, 2, ...] and has ever increasing numbers further down the series.
If you take these numbers modulo n
, then the series will eventually become periodical.
This is called the Pisano period π(n). The series of Pisano numbers for n = [1, 2, 3, ...] is A001175.
Write a function get_pisano_numbers()
in Python, which for a list of numbers n
returns
the corresponding list of π(n)
. For example, get_pisano_numbers([1,3])
would return [1,8]
.
The winner is the function that is both the shortest and the fastest.
- The software used is Python 3.11. Only modules from the standard library can be used, no numpy or other dependencies.
- A submission should be a standalone
.py
file. - The score is the sum of the file size in bytes and the time to execute
get_pisano_numbers()
in miliseconds. Lower score wins. - Before scoring, the .py files are processed by
autopep8 --max-line-length 99999
, in order to limit tricks with removal of whitespace to some degree. - The input is a list of randomly chosen numbers from the range 2..6000. The list is 400 numbers long and the same for each submission.
- The code is executed on a 16 core AMD CPU.
As an example there are two implementations in the repository, together with a test script that executes them and prints a score.
Output of test.py
:
NAME RESULT TIME SIZE SCORE
pisano_example1 PASS 0 33004 33004
pisano_example2 PASS 397668 794 398462
The first example includes all Pisano periods for 1..6000 hardcoded in the source. This makes the execution very fast, but has a high score because of the file size.
The second example calculates all the requested numbers. This is a lot smaller, but execution takes a very long time.