Fibonacci rings modulo n

From testwiki
Jump to navigation Jump to search

Template:Original research This article by Dan Polansky has a look at Fibonacci rings modulo n. The term Fibonacci ring is introduced in this article and may be terminologically unfortunate; maybe we can figure out a better term later.

There is a decent article on Fibonacci sequence modulo n in Wikipedia. This sequence has the property that it starts from 1, 1, and continues from there using the recursive formula xn+2:=xn+1+xn. By contrast, what I mean by Fibonacci ring is any sequence starting from X, Y, for any X and Y. I call it a ring since, calculating on the modulo space, the sequence is guaranteed to return to where it started, and I find it arbitrary whether I start at the beginning or in the middle. Thus, I imagine the sequence to be of the shape of the letter O, a cycle/ring/loop.

I consider e.g. the sequence starting from 1, 1 and the sequence starting from 1, 2 to be the same ring: it covers the same set of pairs.

The objective of the calculation and analysis is, for each chosen modulus, find all rings (covering all pairs) and notice their properties and regularities, if any. All rings are found when all pairs are covered; it is not the purpose to list all rings taking all X,Y as a start since the result would be a massive duplication as for covered pairs.

To be done: describe the found regularities concerning the ring lengths, e.g. each ring length has to divide the length of the 1,1-ring. Make some notes about prime modulus values. Note how e.g. rings for the modulus 3 are reflected in all the modulus multiples, e.g. the rings for the modulus 15.

Finding the rings can be used as a manual calculation exercise. What is nice about the exercise is that the addition tasks are self-generating, and because of the regularities within the rings and between the rings, there is some level of quick verification/double checking.

Terminology

The term Fibonacci ring is a provisional one and raises some concerns. For one thing, the word ring has a meaning in algebra, a very different one, as per W:Ring (mathematics); the justification for the choice is the visual image of a ring one wears on a finger. For another thing, letting the word Fibonacci refer to sequences other than the 1,1-one is uncustomary; for instance, the sequence starting at 2, 1 and using the same recursive formula is called Lucas numbers per Wikipedia and MathWorld[1].

Bocci and Valle 2024 use the term generalized Fibonacci sequence to refer to a sequence with generalized first two terms[2]. Following this model, I could perhaps use the term generalized Fibonacci ring as more accurate or less misleading.

Rings for modulus 2 through 20

Rings for modulus 2 through 20, output by the Python script below, for an impression of what we are talking about. The ring 0,0 is omitted as trivially present everywhere. 

Modulus 2
---------------
- 0, 1, 1, 0, 1 (3)

Modulus 3
---------------
- 0, 1, 1, 2, 0, 2, 2, 1, 0, 1 (8)

Modulus 4
---------------
- 0, 1, 1, 2, 3, 1, 0, 1 (6)
- 0, 2, 2, 0, 2 (3)
- 0, 3, 3, 2, 1, 3, 0, 3 (6)

Modulus 5
---------------
- 0, 1, 1, 2, 3, 0, 3, 3, 1, 4, 0, 4, 4, 3, 2, 0, 2, 2, 4, 1, 0, 1 (20)
- 1, 3, 4, 2, 1, 3 (4)

Modulus 6
---------------
- 0, 1, 1, 2, 3, 5, 2, 1, 3, 4, 1, 5, 0, 5, 5, 4, 3, 1, 4, 5, 3, 2, 5, 1, 0, 1 (24)
- 0, 2, 2, 4, 0, 4, 4, 2, 0, 2 (8)
- 0, 3, 3, 0, 3 (3)

Modulus 7
---------------
- 0, 1, 1, 2, 3, 5, 1, 6, 0, 6, 6, 5, 4, 2, 6, 1, 0, 1 (16)
- 0, 2, 2, 4, 6, 3, 2, 5, 0, 5, 5, 3, 1, 4, 5, 2, 0, 2 (16)
- 0, 3, 3, 6, 2, 1, 3, 4, 0, 4, 4, 1, 5, 6, 4, 3, 0, 3 (16)

Modulus 8
---------------
- 0, 1, 1, 2, 3, 5, 0, 5, 5, 2, 7, 1, 0, 1 (12)
- 0, 2, 2, 4, 6, 2, 0, 2 (6)
- 0, 3, 3, 6, 1, 7, 0, 7, 7, 6, 5, 3, 0, 3 (12)
- 0, 4, 4, 0, 4 (3)
- 0, 6, 6, 4, 2, 6, 0, 6 (6)
- 1, 3, 4, 7, 3, 2, 5, 7, 4, 3, 7, 2, 1, 3 (12)
- 1, 4, 5, 1, 6, 7, 5, 4, 1, 5, 6, 3, 1, 4 (12)

Modulus 9
---------------
- 0, 1, 1, 2, 3, 5, 8, 4, 3, 7, 1, 8, 0, 8, 8, 7, 6, 4, 1, 5, 6, 2, 8, 1, 0, 1 (24)
- 0, 2, 2, 4, 6, 1, 7, 8, 6, 5, 2, 7, 0, 7, 7, 5, 3, 8, 2, 1, 3, 4, 7, 2, 0, 2 (24)
- 0, 3, 3, 6, 0, 6, 6, 3, 0, 3 (8)
- 0, 4, 4, 8, 3, 2, 5, 7, 3, 1, 4, 5, 0, 5, 5, 1, 6, 7, 4, 2, 6, 8, 5, 4, 0, 4 (24)

Modulus 10
---------------
- 0, 1, 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, 4, 3, 7, 0, 7, 7, 4, 1, 5, 6, 1, 7, 8, 5, 3, 8, 1, 9, 0, 9, 9, 8, 7, 5, 2, 7, 9, 6, 5, 1, 6, 7, 3, 0, 3, 3, 6, 9, 5, 4, 9, 3, 2, 5, 7, 2, 9, 1, 0, 1 (60)
- 0, 2, 2, 4, 6, 0, 6, 6, 2, 8, 0, 8, 8, 6, 4, 0, 4, 4, 8, 2, 0, 2 (20)
- 0, 5, 5, 0, 5 (3)
- 1, 3, 4, 7, 1, 8, 9, 7, 6, 3, 9, 2, 1, 3 (12)
- 2, 6, 8, 4, 2, 6 (4)

Modulus 11
---------------
- 0, 1, 1, 2, 3, 5, 8, 2, 10, 1, 0, 1 (10)
- 0, 2, 2, 4, 6, 10, 5, 4, 9, 2, 0, 2 (10)
- 0, 3, 3, 6, 9, 4, 2, 6, 8, 3, 0, 3 (10)
- 0, 4, 4, 8, 1, 9, 10, 8, 7, 4, 0, 4 (10)
- 0, 5, 5, 10, 4, 3, 7, 10, 6, 5, 0, 5 (10)
- 0, 6, 6, 1, 7, 8, 4, 1, 5, 6, 0, 6 (10)
- 0, 7, 7, 3, 10, 2, 1, 3, 4, 7, 0, 7 (10)
- 0, 8, 8, 5, 2, 7, 9, 5, 3, 8, 0, 8 (10)
- 0, 9, 9, 7, 5, 1, 6, 7, 2, 9, 0, 9 (10)
- 0, 10, 10, 9, 8, 6, 3, 9, 1, 10, 0, 10 (10)
- 1, 4, 5, 9, 3, 1, 4 (5)
- 1, 8, 9, 6, 4, 10, 3, 2, 5, 7, 1, 8 (10)
- 2, 8, 10, 7, 6, 2, 8 (5)

Modulus 12
---------------
- 0, 1, 1, 2, 3, 5, 8, 1, 9, 10, 7, 5, 0, 5, 5, 10, 3, 1, 4, 5, 9, 2, 11, 1, 0, 1 (24)
- 0, 2, 2, 4, 6, 10, 4, 2, 6, 8, 2, 10, 0, 10, 10, 8, 6, 2, 8, 10, 6, 4, 10, 2, 0, 2 (24)
- 0, 3, 3, 6, 9, 3, 0, 3 (6)
- 0, 4, 4, 8, 0, 8, 8, 4, 0, 4 (8)
- 0, 6, 6, 0, 6 (3)
- 0, 7, 7, 2, 9, 11, 8, 7, 3, 10, 1, 11, 0, 11, 11, 10, 9, 7, 4, 11, 3, 2, 5, 7, 0, 7 (24)
- 0, 9, 9, 6, 3, 9, 0, 9 (6)
- 1, 3, 4, 7, 11, 6, 5, 11, 4, 3, 7, 10, 5, 3, 8, 11, 7, 6, 1, 7, 8, 3, 11, 2, 1, 3 (24)
- 1, 5, 6, 11, 5, 4, 9, 1, 10, 11, 9, 8, 5, 1, 6, 7, 1, 8, 9, 5, 2, 7, 9, 4, 1, 5 (24)

Modulus 13
---------------
- 0, 1, 1, 2, 3, 5, 8, 0, 8, 8, 3, 11, 1, 12, 0, 12, 12, 11, 10, 8, 5, 0, 5, 5, 10, 2, 12, 1, 0, 1 (28)
- 0, 2, 2, 4, 6, 10, 3, 0, 3, 3, 6, 9, 2, 11, 0, 11, 11, 9, 7, 3, 10, 0, 10, 10, 7, 4, 11, 2, 0, 2 (28)
- 0, 4, 4, 8, 12, 7, 6, 0, 6, 6, 12, 5, 4, 9, 0, 9, 9, 5, 1, 6, 7, 0, 7, 7, 1, 8, 9, 4, 0, 4 (28)
- 1, 3, 4, 7, 11, 5, 3, 8, 11, 6, 4, 10, 1, 11, 12, 10, 9, 6, 2, 8, 10, 5, 2, 7, 9, 3, 12, 2, 1, 3 (28)
- 1, 4, 5, 9, 1, 10, 11, 8, 6, 1, 7, 8, 2, 10, 12, 9, 8, 4, 12, 3, 2, 5, 7, 12, 6, 5, 11, 3, 1, 4 (28)
- 1, 5, 6, 11, 4, 2, 6, 8, 1, 9, 10, 6, 3, 9, 12, 8, 7, 2, 9, 11, 7, 5, 12, 4, 3, 7, 10, 4, 1, 5 (28)

Modulus 14
---------------
- 0, 1, 1, 2, 3, 5, 8, 13, 7, 6, 13, 5, 4, 9, 13, 8, 7, 1, 8, 9, 3, 12, 1, 13, 0, 13, 13, 12, 11, 9, 6, 1, 7, 8, 1, 9, 10, 5, 1, 6, 7, 13, 6, 5, 11, 2, 13, 1, 0, 1 (48)
- 0, 2, 2, 4, 6, 10, 2, 12, 0, 12, 12, 10, 8, 4, 12, 2, 0, 2 (16)
- 0, 3, 3, 6, 9, 1, 10, 11, 7, 4, 11, 1, 12, 13, 11, 10, 7, 3, 10, 13, 9, 8, 3, 11, 0, 11, 11, 8, 5, 13, 4, 3, 7, 10, 3, 13, 2, 1, 3, 4, 7, 11, 4, 1, 5, 6, 11, 3, 0, 3 (48)
- 0, 4, 4, 8, 12, 6, 4, 10, 0, 10, 10, 6, 2, 8, 10, 4, 0, 4 (16)
- 0, 5, 5, 10, 1, 11, 12, 9, 7, 2, 9, 11, 6, 3, 9, 12, 7, 5, 12, 3, 1, 4, 5, 9, 0, 9, 9, 4, 13, 3, 2, 5, 7, 12, 5, 3, 8, 11, 5, 2, 7, 9, 2, 11, 13, 10, 9, 5, 0, 5 (48)
- 0, 6, 6, 12, 4, 2, 6, 8, 0, 8, 8, 2, 10, 12, 8, 6, 0, 6 (16)
- 0, 7, 7, 0, 7 (3)

Modulus 15
---------------
- 0, 1, 1, 2, 3, 5, 8, 13, 6, 4, 10, 14, 9, 8, 2, 10, 12, 7, 4, 11, 0, 11, 11, 7, 3, 10, 13, 8, 6, 14, 5, 4, 9, 13, 7, 5, 12, 2, 14, 1, 0, 1 (40)
- 0, 2, 2, 4, 6, 10, 1, 11, 12, 8, 5, 13, 3, 1, 4, 5, 9, 14, 8, 7, 0, 7, 7, 14, 6, 5, 11, 1, 12, 13, 10, 8, 3, 11, 14, 10, 9, 4, 13, 2, 0, 2 (40)
- 0, 3, 3, 6, 9, 0, 9, 9, 3, 12, 0, 12, 12, 9, 6, 0, 6, 6, 12, 3, 0, 3 (20)
- 0, 4, 4, 8, 12, 5, 2, 7, 9, 1, 10, 11, 6, 2, 8, 10, 3, 13, 1, 14, 0, 14, 14, 13, 12, 10, 7, 2, 9, 11, 5, 1, 6, 7, 13, 5, 3, 8, 11, 4, 0, 4 (40)
- 0, 5, 5, 10, 0, 10, 10, 5, 0, 5 (8)
- 0, 8, 8, 1, 9, 10, 4, 14, 3, 2, 5, 7, 12, 4, 1, 5, 6, 11, 2, 13, 0, 13, 13, 11, 9, 5, 14, 4, 3, 7, 10, 2, 12, 14, 11, 10, 6, 1, 7, 8, 0, 8 (40)
- 1, 3, 4, 7, 11, 3, 14, 2, 1, 3 (8)
- 1, 8, 9, 2, 11, 13, 9, 7, 1, 8 (8)
- 1, 13, 14, 12, 11, 8, 4, 12, 1, 13 (8)
- 2, 6, 8, 14, 7, 6, 13, 4, 2, 6 (8)
- 3, 9, 12, 6, 3, 9 (4)

Modulus 16
---------------
- 0, 1, 1, 2, 3, 5, 8, 13, 5, 2, 7, 9, 0, 9, 9, 2, 11, 13, 8, 5, 13, 2, 15, 1, 0, 1 (24)
- 0, 2, 2, 4, 6, 10, 0, 10, 10, 4, 14, 2, 0, 2 (12)
- 0, 3, 3, 6, 9, 15, 8, 7, 15, 6, 5, 11, 0, 11, 11, 6, 1, 7, 8, 15, 7, 6, 13, 3, 0, 3 (24)
- 0, 4, 4, 8, 12, 4, 0, 4 (6)
- 0, 5, 5, 10, 15, 9, 8, 1, 9, 10, 3, 13, 0, 13, 13, 10, 7, 1, 8, 9, 1, 10, 11, 5, 0, 5 (24)
- 0, 6, 6, 12, 2, 14, 0, 14, 14, 12, 10, 6, 0, 6 (12)
- 0, 7, 7, 14, 5, 3, 8, 11, 3, 14, 1, 15, 0, 15, 15, 14, 13, 11, 8, 3, 11, 14, 9, 7, 0, 7 (24)
- 0, 8, 8, 0, 8 (3)
- 0, 12, 12, 8, 4, 12, 0, 12 (6)
- 1, 3, 4, 7, 11, 2, 13, 15, 12, 11, 7, 2, 9, 11, 4, 15, 3, 2, 5, 7, 12, 3, 15, 2, 1, 3 (24)
- 1, 4, 5, 9, 14, 7, 5, 12, 1, 13, 14, 11, 9, 4, 13, 1, 14, 15, 13, 12, 9, 5, 14, 3, 1, 4 (24)
- 1, 5, 6, 11, 1, 12, 13, 9, 6, 15, 5, 4, 9, 13, 6, 3, 9, 12, 5, 1, 6, 7, 13, 4, 1, 5 (24)
- 1, 11, 12, 7, 3, 10, 13, 7, 4, 11, 15, 10, 9, 3, 12, 15, 11, 10, 5, 15, 4, 3, 7, 10, 1, 11 (24)
- 2, 6, 8, 14, 6, 4, 10, 14, 8, 6, 14, 4, 2, 6 (12)
- 2, 8, 10, 2, 12, 14, 10, 8, 2, 10, 12, 6, 2, 8 (12)

Modulus 17
---------------
- 0, 1, 1, 2, 3, 5, 8, 13, 4, 0, 4, 4, 8, 12, 3, 15, 1, 16, 0, 16, 16, 15, 14, 12, 9, 4, 13, 0, 13, 13, 9, 5, 14, 2, 16, 1, 0, 1 (36)
- 0, 2, 2, 4, 6, 10, 16, 9, 8, 0, 8, 8, 16, 7, 6, 13, 2, 15, 0, 15, 15, 13, 11, 7, 1, 8, 9, 0, 9, 9, 1, 10, 11, 4, 15, 2, 0, 2 (36)
- 0, 3, 3, 6, 9, 15, 7, 5, 12, 0, 12, 12, 7, 2, 9, 11, 3, 14, 0, 14, 14, 11, 8, 2, 10, 12, 5, 0, 5, 5, 10, 15, 8, 6, 14, 3, 0, 3 (36)
- 0, 6, 6, 12, 1, 13, 14, 10, 7, 0, 7, 7, 14, 4, 1, 5, 6, 11, 0, 11, 11, 5, 16, 4, 3, 7, 10, 0, 10, 10, 3, 13, 16, 12, 11, 6, 0, 6 (36)
- 1, 3, 4, 7, 11, 1, 12, 13, 8, 4, 12, 16, 11, 10, 4, 14, 1, 15, 16, 14, 13, 10, 6, 16, 5, 4, 9, 13, 5, 1, 6, 7, 13, 3, 16, 2, 1, 3 (36)
- 1, 4, 5, 9, 14, 6, 3, 9, 12, 4, 16, 3, 2, 5, 7, 12, 2, 14, 16, 13, 12, 8, 3, 11, 14, 8, 5, 13, 1, 14, 15, 12, 10, 5, 15, 3, 1, 4 (36)
- 1, 7, 8, 15, 6, 4, 10, 14, 7, 4, 11, 15, 9, 7, 16, 6, 5, 11, 16, 10, 9, 2, 11, 13, 7, 3, 10, 13, 6, 2, 8, 10, 1, 11, 12, 6, 1, 7 (36)
- 1, 9, 10, 2, 12, 14, 9, 6, 15, 4, 2, 6, 8, 14, 5, 2, 7, 9, 16, 8, 7, 15, 5, 3, 8, 11, 2, 13, 15, 11, 9, 3, 12, 15, 10, 8, 1, 9 (36)

Modulus 18
---------------
- 0, 1, 1, 2, 3, 5, 8, 13, 3, 16, 1, 17, 0, 17, 17, 16, 15, 13, 10, 5, 15, 2, 17, 1, 0, 1 (24)
- 0, 2, 2, 4, 6, 10, 16, 8, 6, 14, 2, 16, 0, 16, 16, 14, 12, 8, 2, 10, 12, 4, 16, 2, 0, 2 (24)
- 0, 3, 3, 6, 9, 15, 6, 3, 9, 12, 3, 15, 0, 15, 15, 12, 9, 3, 12, 15, 9, 6, 15, 3, 0, 3 (24)
- 0, 4, 4, 8, 12, 2, 14, 16, 12, 10, 4, 14, 0, 14, 14, 10, 6, 16, 4, 2, 6, 8, 14, 4, 0, 4 (24)
- 0, 5, 5, 10, 15, 7, 4, 11, 15, 8, 5, 13, 0, 13, 13, 8, 3, 11, 14, 7, 3, 10, 13, 5, 0, 5 (24)
- 0, 6, 6, 12, 0, 12, 12, 6, 0, 6 (8)
- 0, 7, 7, 14, 3, 17, 2, 1, 3, 4, 7, 11, 0, 11, 11, 4, 15, 1, 16, 17, 15, 14, 11, 7, 0, 7 (24)
- 0, 8, 8, 16, 6, 4, 10, 14, 6, 2, 8, 10, 0, 10, 10, 2, 12, 14, 8, 4, 12, 16, 10, 8, 0, 8 (24)
- 0, 9, 9, 0, 9 (3)
- 1, 4, 5, 9, 14, 5, 1, 6, 7, 13, 2, 15, 17, 14, 13, 9, 4, 13, 17, 12, 11, 5, 16, 3, 1, 4 (24)
- 1, 5, 6, 11, 17, 10, 9, 1, 10, 11, 3, 14, 17, 13, 12, 7, 1, 8, 9, 17, 8, 7, 15, 4, 1, 5 (24)
- 1, 7, 8, 15, 5, 2, 7, 9, 16, 7, 5, 12, 17, 11, 10, 3, 13, 16, 11, 9, 2, 11, 13, 6, 1, 7 (24)
- 1, 9, 10, 1, 11, 12, 5, 17, 4, 3, 7, 10, 17, 9, 8, 17, 7, 6, 13, 1, 14, 15, 11, 8, 1, 9 (24)
- 1, 12, 13, 7, 2, 9, 11, 2, 13, 15, 10, 7, 17, 6, 5, 11, 16, 9, 7, 16, 5, 3, 8, 11, 1, 12 (24)
- 1, 13, 14, 9, 5, 14, 1, 15, 16, 13, 11, 6, 17, 5, 4, 9, 13, 4, 17, 3, 2, 5, 7, 12, 1, 13 (24)

Modulus 19
---------------
- 0, 1, 1, 2, 3, 5, 8, 13, 2, 15, 17, 13, 11, 5, 16, 2, 18, 1, 0, 1 (18)
- 0, 2, 2, 4, 6, 10, 16, 7, 4, 11, 15, 7, 3, 10, 13, 4, 17, 2, 0, 2 (18)
- 0, 3, 3, 6, 9, 15, 5, 1, 6, 7, 13, 1, 14, 15, 10, 6, 16, 3, 0, 3 (18)
- 0, 4, 4, 8, 12, 1, 13, 14, 8, 3, 11, 14, 6, 1, 7, 8, 15, 4, 0, 4 (18)
- 0, 5, 5, 10, 15, 6, 2, 8, 10, 18, 9, 8, 17, 6, 4, 10, 14, 5, 0, 5 (18)
- 0, 6, 6, 12, 18, 11, 10, 2, 12, 14, 7, 2, 9, 11, 1, 12, 13, 6, 0, 6 (18)
- 0, 7, 7, 14, 2, 16, 18, 15, 14, 10, 5, 15, 1, 16, 17, 14, 12, 7, 0, 7 (18)
- 0, 8, 8, 16, 5, 2, 7, 9, 16, 6, 3, 9, 12, 2, 14, 16, 11, 8, 0, 8 (18)
- 0, 9, 9, 18, 8, 7, 15, 3, 18, 2, 1, 3, 4, 7, 11, 18, 10, 9, 0, 9 (18)
- 0, 10, 10, 1, 11, 12, 4, 16, 1, 17, 18, 16, 15, 12, 8, 1, 9, 10, 0, 10 (18)
- 0, 11, 11, 3, 14, 17, 12, 10, 3, 13, 16, 10, 7, 17, 5, 3, 8, 11, 0, 11 (18)
- 0, 12, 12, 5, 17, 3, 1, 4, 5, 9, 14, 4, 18, 3, 2, 5, 7, 12, 0, 12 (18)
- 0, 13, 13, 7, 1, 8, 9, 17, 7, 5, 12, 17, 10, 8, 18, 7, 6, 13, 0, 13 (18)
- 0, 14, 14, 9, 4, 13, 17, 11, 9, 1, 10, 11, 2, 13, 15, 9, 5, 14, 0, 14 (18)
- 0, 15, 15, 11, 7, 18, 6, 5, 11, 16, 8, 5, 13, 18, 12, 11, 4, 15, 0, 15 (18)
- 0, 16, 16, 13, 10, 4, 14, 18, 13, 12, 6, 18, 5, 4, 9, 13, 3, 16, 0, 16 (18)
- 0, 17, 17, 15, 13, 9, 3, 12, 15, 8, 4, 12, 16, 9, 6, 15, 2, 17, 0, 17 (18)
- 0, 18, 18, 17, 16, 14, 11, 6, 17, 4, 2, 6, 8, 14, 3, 17, 1, 18, 0, 18 (18)
- 1, 5, 6, 11, 17, 9, 7, 16, 4, 1, 5 (9)
- 1, 15, 16, 12, 9, 2, 11, 13, 5, 18, 4, 3, 7, 10, 17, 8, 6, 14, 1, 15 (18)
- 2, 10, 12, 3, 15, 18, 14, 13, 8, 2, 10 (9)

Modulus 20
---------------
- 0, 1, 1, 2, 3, 5, 8, 13, 1, 14, 15, 9, 4, 13, 17, 10, 7, 17, 4, 1, 5, 6, 11, 17, 8, 5, 13, 18, 11, 9, 0, 9, 9, 18, 7, 5, 12, 17, 9, 6, 15, 1, 16, 17, 13, 10, 3, 13, 16, 9, 5, 14, 19, 13, 12, 5, 17, 2, 19, 1, 0, 1 (60)
- 0, 2, 2, 4, 6, 10, 16, 6, 2, 8, 10, 18, 8, 6, 14, 0, 14, 14, 8, 2, 10, 12, 2, 14, 16, 10, 6, 16, 2, 18, 0, 18, 18, 16, 14, 10, 4, 14, 18, 12, 10, 2, 12, 14, 6, 0, 6, 6, 12, 18, 10, 8, 18, 6, 4, 10, 14, 4, 18, 2, 0, 2 (60)
- 0, 3, 3, 6, 9, 15, 4, 19, 3, 2, 5, 7, 12, 19, 11, 10, 1, 11, 12, 3, 15, 18, 13, 11, 4, 15, 19, 14, 13, 7, 0, 7, 7, 14, 1, 15, 16, 11, 7, 18, 5, 3, 8, 11, 19, 10, 9, 19, 8, 7, 15, 2, 17, 19, 16, 15, 11, 6, 17, 3, 0, 3 (60)
- 0, 4, 4, 8, 12, 0, 12, 12, 4, 16, 0, 16, 16, 12, 8, 0, 8, 8, 16, 4, 0, 4 (20)
- 0, 5, 5, 10, 15, 5, 0, 5 (6)
- 0, 10, 10, 0, 10 (3)
- 0, 11, 11, 2, 13, 15, 8, 3, 11, 14, 5, 19, 4, 3, 7, 10, 17, 7, 4, 11, 15, 6, 1, 7, 8, 15, 3, 18, 1, 19, 0, 19, 19, 18, 17, 15, 12, 7, 19, 6, 5, 11, 16, 7, 3, 10, 13, 3, 16, 19, 15, 14, 9, 3, 12, 15, 7, 2, 9, 11, 0, 11 (60)
- 0, 13, 13, 6, 19, 5, 4, 9, 13, 2, 15, 17, 12, 9, 1, 10, 11, 1, 12, 13, 5, 18, 3, 1, 4, 5, 9, 14, 3, 17, 0, 17, 17, 14, 11, 5, 16, 1, 17, 18, 15, 13, 8, 1, 9, 10, 19, 9, 8, 17, 5, 2, 7, 9, 16, 5, 1, 6, 7, 13, 0, 13 (60)
- 0, 15, 15, 10, 5, 15, 0, 15 (6)
- 1, 3, 4, 7, 11, 18, 9, 7, 16, 3, 19, 2, 1, 3 (12)
- 1, 8, 9, 17, 6, 3, 9, 12, 1, 13, 14, 7, 1, 8 (12)
- 1, 18, 19, 17, 16, 13, 9, 2, 11, 13, 4, 17, 1, 18 (12)
- 2, 6, 8, 14, 2, 16, 18, 14, 12, 6, 18, 4, 2, 6 (12)
- 3, 14, 17, 11, 8, 19, 7, 6, 13, 19, 12, 11, 3, 14 (12)
- 4, 12, 16, 8, 4, 12 (4)

Lengths found: 3, 4, 5, 6, 8, 9, 10, 12, 16, 18, 20, 24, 28, 36, 40, 48, 60,

Python script

import sys, argparse

def main():  
  parser = argparse.ArgumentParser(description="Explores Fibonacci sequence modulo n and related rings.")
  addarg = parser.add_argument
  addarg("maxmodulus", help="Maximum modulus to explore.", type=int, default=10, nargs="?")
  addarg("-one", help="Single modulus to explore.", type=int, nargs="?")
  args = parser.parse_args()

  if args.one is not None:
    lengthsFound = set()
    print ("Modulus " + str(args.one))
    print ("---------------")
    processModulus(args.one, lengthsFound)
    print()
    return
  else:
    lengthsFound = set()
    for m in range(2, args.maxmodulus + 1):
      print ("Modulus " + str(m))
      print ("---------------")
      processModulus(m, lengthsFound)
      print()
    print("Lengths found: ", end="")
    for i in sorted(lengthsFound):
      print(str(i) + ", ", end="")
  
def processModulus(modulus, lengthsFound):
  pairsFound = set()
  pairFoundCount = 0
  for x in range(0, modulus):
    for y in range(1, modulus):
      if not (x, y) in pairsFound:
        length = processRing(x, y, modulus, pairsFound)
        pairFoundCount += length
        lengthsFound.add(length)

def processRing(n1s, n2s, m, pairsFound):
  n1, n2 = n1s, n2s
  pairFoundCount = 0
  print("- ", end="")
  while True:
    pairFoundCount += 1
    pairsFound.add((n1, n2))
    print(str(n1) + ", ", end="")
    n3 = (n2 + n1) % m
    n2, n1 = n3, n2
    if n1 == n1s and n2 == n2s: break
  print(str(n1) + ", " + str(n2), end="")
  print(" (" + str(pairFoundCount) + ")")
  return pairFoundCount

if __name__ == "__main__":
  main()

Large language models

I asked Google Gemini the following:

  • What is the Fibonacci sequence modulo 5?
    • It gave a correct answer.
  • What is the Fibonacci sequence modulo 10?
    • It gave a correct answer.
  • What is the Fibonacci sequence modulo 11 and what are other sequences using the same recursive formula but starting at values different from 1,1, e.g. 3,3?
    • It gave an impressive, possibly correct answer (I did only quick verification). I have no idea how it can do so well.

I then got even more impressive answer by the following sequence of queries:

  • What is the Fibonacci sequence modulo 11 and what are other sequences using the same recursive formula but starting at values different from 1,1, e.g. 3,3?
  • Can you list all such generalized sequences modulo 11?
  • I mean actually listing, not giving an algorithm.
  • Can you list not all sequences but only so many sequences that all pairs are in at least one sequence?

The results appear too good to be true. That this is a result of mere seeking patterns in word sequences by means of artificial neural networks is hard to believe.

References

  1. ↑ https://mathworld.wolfram.com/LucasNumber.html
  2. ↑ Fully generalized Fibonacci series modulo n as music sequence generators by Bocci and Valle, 2024, iris.unito.it

Further reading

Retrieved from "https://en.wikiversity.beta.math.wmflabs.org/w/index.php?title=Fibonacci_rings_modulo_n&oldid=3636"