A106290 Number of different orbit lengths of the 5-step recursion mod n.

1, 3, 4, 4, 2, 9, 2, 6, 7, 6, 2, 11, 2, 6, 8, 8, 2, 9, 3, 8, 8, 6, 4, 12, 3, 6, 10, 8, 3, 18, 2, 10, 8, 6, 4, 11, 2, 6, 8, 12, 2, 18, 4, 8, 14, 9, 4, 16, 3, 9, 8, 8, 2, 12, 4, 12, 10, 6, 3, 22

Offset

1,2

Comments

Consider the 5-step recursion x(k) = (x(k-1)+x(k-2)+x(k-3)+x(k-4)+x(k-5)) mod n. For any of the n^5 initial conditions x(1), x(2), x(3), x(4) and x(5) in Zn, the recursion has a finite period. Each of these n^5 vectors belongs to exactly one orbit. In general, there are only a few different orbit lengths for each n. For n=8, there are 6 different lengths: 1, 2, 3, 6, 12 and 24. The maximum possible length of an orbit is A106303(n), the period of the Fibonacci 5-step sequence mod n.

Links

Table of n, a(n) for n=1..60.

Eric Weisstein's World of Mathematics, Fibonacci n-Step Number.

Prog

(Python)
from itertools import count, product
def A106290(n):
    bset, tset = set(), set()
    for t in product(range(n), repeat=5):
        t2 = t
        for c in count(1):
            t2 = t2[1:] + (sum(t2)%n, )
            if t == t2:
                bset.add(c)
                tset.add(t)
                break
            if t2 in tset:
                tset.add(t)
                break
    return len(bset) # Chai Wah Wu, Feb 22 2022

Crossrefs

Cf. A106287 (orbits of 5-step sequences), A106309 (primes that yield a simple orbit structure in 5-step recursions).

Sequence in context: A358449 A209329 A353156 * A249618 A073498 A105736

Adjacent sequences: A106287 A106288 A106289 * A106291 A106292 A106293

Keyword

nonn,more

Author

T. D. Noe, May 02 2005

Status

approved