r""" Python module for OEIS sequence number A046734. Period of A000213 (tribonacci numbers) mod n. Examples of use. ----------------------------------------------------------------------- >>> from a046734 import * >>> print a046734_list(14) [1, 1, 13, 4, 31, 13, 48, 8, 39, 31, 110, 52, 168, 48] >>> print a046734_offset 1 >>> for x in a046734_list_pairs(6): ... print x ... (1, 1) (2, 1) (3, 13) (4, 4) (5, 31) (6, 13) >>> print a046734(4) 4 ----------------------------------------------------------------------- """ from itertools import islice, izip, count __all__ = ('a046734_offset', 'a046734_list', 'a046734_list_pairs', 'a046734', 'a046734_gen') __author__ = 'Nick Hobson ' a046734_offset = offset = 1 def a046734_gen(prange): """Generator function for OEIS sequence A046734.""" n = prange[len(prange) - 1] for i in xrange(1, min(3,n+1)): yield 1 if n < 3: return last = [[1, 1, 1] for d in xrange(n+1)] value = [0] * (n+1) # Create a set containing each number in prange. s = set(d for d in prange) y = prange[0] for k in count(3): # Check each element for which the period has not yet been # established (i.e., still in s). If the element has # recycled to (1, 1, 1), add it to set sm (to be removed # from s), and store the period. sm = set() for d in s: last[d][k%3] += last[d][(k+1)%3] + last[d][(k+2)%3] if last[d][0]%d == last[d][1]%d == last[d][2]%d == 1: sm.add(d) value[d] = k - 2 s -= sm # Periodically reduce each element modulo d. if k % 20 == 3: for d in s: for j in xrange(len(last[d])): last[d][j] %= d # Yield as many consecutive values as possible this time around. while y <= n and value[y] > 0: yield value[y] y += 1 # Return once all terms have been yielded. if y > n: return def a046734_list(n): """Returns a list of the first n >= 0 terms.""" if n < 0: raise ValueError, 'Input must be a non-negative integer' return list(a046734_gen(xrange(3, n+1))) def a046734_list_pairs(n): """Returns a list of tuples (n, a(n)) of the first n >= 0 terms.""" if n < 0: raise ValueError, 'Input must be a non-negative integer' return list(izip(xrange(offset, n+offset), a046734_gen(xrange(3, n+1)))) def a046734(n): """Returns the term with index n >= 1; offset 1.""" if n < offset: raise ValueError, 'Input must be an integer >= offset = ' + str(offset) return list(a046734_gen(xrange(n, n+1))).pop()