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

Author

T. D. Noe, May 02 2005

Keywords

• nonn
• more

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

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

Crossrefs

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

Programs

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