Tested to use blist instead of the python standard list. Blist is a binary structure (binary tree / b-tree / b+-tree, don't know which) and is supposed to be a faster direct replacement for list. But it turned out to not be any advantage at all. The built in list performs as well in our cases. So I tweaked the functions as well as I could and added some "figurative" sequences. These "figurative" number sequences all have graphical interpretations. Maybe some people with deeper knowledge of Python can make better performing functions. Here comes the total list of final implementations. Note that some (but not all) functions are doubled. In that case one is for generating "the n-th number" in a sequence and the other for generating a list with the n first numbers in the same sequence:
from itertools import groupby, combinations import math # Some integer sequences that have at least one graphical representation # In all these functions "seq" is the generated sequence def fibn(start, length, n): '''Function to generate the n-th number sequence generalization of the Fibonacci number sequence. start == 1 and n == 2 => Fibonacci number sequence n == 3 => "Tribonacci" number sequence n == 4 => "Tetranacci" number sequence and so on ... start == 2 and n == ... (test it) A generalization of your gen_fib function ''' if n < 2: return [] seq = [0]*length seq[n-1] = start b = 0 while seq[-1] == 0: seq[b+n] = sum(seq[b:b+n]) b += 1 return seq def lucas(n): # https://en.wikipedia.org/wiki/Lucas_number seq = [0]*n seq[0], seq[1] = 2, 1 b = 2 while seq[-1] == 0: seq[b] = seq[b-1]+seq[b-2] b += 1 return seq def partitions_count(n): ''' Help function for partitions, found on stackoverflow.com Gives the number of ways of writing the integer n as a sum of positive integers, where the order of addends is not considered significant. ''' dic = {} def p(n, k): '''Gives the number of ways of writing n as a sum of exactly k terms or, equivalently, the number of partitions into parts of which the largest is exactly k. ''' if n < k: return 0 if n == k: return 1 if k == 0: return 0 key = str(n) + ',' + str(k) try: temp = dic[key] except: temp = p(n-1, k-1) + p(n-k, k) dic[key] = temp finally: return temp partitions_count = 0 for k in range(n + 1): partitions_count += p(n, k) return partitions_count def partitions(n): # https://en.wikipedia.org/wiki/Partition_number # The help function partitions_count was found on stackoverflow.com ''' seq = [0]*n b = 0 while seq[-1] == 0: seq[b] = partitions_count(i) b += 1 return seq def catalan_number(n): # https://en.wikipedia.org/wiki/Catalan_number # Returns the n-th catalan number return math.comb(2*n, n) - math.comb(2*n, n+1) def catalan(n): # https://en.wikipedia.org/wiki/Catalan_number # Returns a list of the n first catalan numbers seq = [] for i in range(n+1): seq.append(math.comb(2*i, i) - math.comb(2*i, i+1)) return seq def lazy_caterers_number(n): # https://en.wikipedia.org/wiki/Lazy_caterer%27s_sequenc # calculate the n-th lazy caterer's number return (n*n + n + 2) // 2 def lazy_caterers(n): # https://en.wikipedia.org/wiki/Lazy_caterer%27s_sequence # Generate a list with the n first lazy caterer's numbers seq = [] for i in range(n+1): seq.append((i*i + i + 2) // 2) return seq def pell(n): # https://en.wikipedia.org/wiki/Pell_number seq = [0, 1] while len(seq) < n: seq.append(2*seq[-1] + seq[-2]) return seq[0:n] def padovan(n): # https://en.wikipedia.org/wiki/Padovan_sequence seq = [1, 1, 1] while len(seq) < n+1: seq.append(seq[-2]+seq[-3]) return seq[0:n+1] def lucky_numbers(n): # https://en.wikipedia.org/wiki/Lucky_number seq = range(-1,n*n+9,2) i = 2 while seq[i:]: seq=sorted(set(seq)-set(seq[seq[i]::seq[i]])) i += 1 return seq[1:n+1] def motzkin(n): # https://en.wikipedia.org/wiki/Motzkin_number seq = [0]*(n+1) seq[0] = 1 for i in range(1, n+1): seq[i] = seq[i-1] for j in range(i-1): seq[i] = seq[i] + seq[j] * seq[i-j-2] return seq def wedderburn_etherington(n): # https://en.wikipedia.org/wiki/Wedderburn%E2%80%93Etherington_number # Found this on GeeksForGeeks, twisted it to generate a list store = dict() def w_e(n): if (n <= 2): return store[n] if (n % 2 == 0): x = n // 2 ans = 0 for i in range(1, x): ans += store[i] * store[n - i] ans += (store[x] * (store[x] + 1)) // 2 store[n] = ans return ans else: x = (n + 1) // 2 ans = 0 for i in range(1, x): ans += store[i] * store[n - i] store[n] = ans return ans store[0] = 0 store[1] = 1 store[2] = 1 for i in range(n): w_e(i) return list(store.values())[0:n] def perrin(n): # https://en.wikipedia.org/wiki/Perrin_number seq = [3, 0, 2] while len(seq) < n + 1: seq.append(seq[-2]+seq[-3]) return seq[0:n+1] def pronic_number(n): # https://en.wikipedia.org/wiki/Pronic_number # return the n-th pronic number return n * (n + 1) def pronic(n): # https://en.wikipedia.org/wiki/Pronic_number # Return a list with the n first pronic numbers i = 1 seq = [] while len(seq) < n: seq.append(i * (i + 1)) i += 1 return seq def look_and_say(n): # https://en.wikipedia.org/wiki/Look-and-say_sequence seq = ['1'] for i in range(n): seq.append(''.join(str(len(list(group))) + key for key, group in groupby(seq[-1]))) return seq def arithmetic(n): # https://en.wikipedia.org/wiki/Arithmetic_number seq = [] x = 1 while len(seq) < n: divisors = [i for i in range(1,x+1) if not x % i] if sum(divisors) % len(divisors) == 0: seq.append(x) x += 1 return seq def deficient(n): # https://en.wikipedia.org/wiki/Deficient_number seq = [] x = 1 while len(seq) < n: divisorsum = sum([i for i in range(1,x+1) if not x % i]) if divisorsum < 2 * x: seq.append(x) x += 1 return seq def abundant(n): # https://en.wikipedia.org/wiki/Deficient_number seq = [] x = 1 while len(seq) < n: divisorsum = sum([i for i in range(1,x+1) if not x % i]) if divisorsum > 2 * x: seq.append(x) x += 1 return seq def practical(n): # https://en.wikipedia.org/wiki/Practical_number nums = [] def is_practical(k): divs = [i for i in range(1, k) if k % i == 0] sums = set() for i in range(1, len(divs)+1): length_i_combs = combinations(divs, i) for combi in length_i_combs: sums.add(sum(combi)) return all([i in sums for i in nums]) ps = [] m = 1 while len(ps) < n: if is_practical(m): ps.append(m) nums.append(m) m += 1 return ps def recaman(n): # https://en.wikipedia.org/wiki/Recam%C3%A1n%27s_sequence seq = [0] x = 1 while len(seq) < n: next = seq[x - 1] - x if next > 0 and next not in seq: seq.append(next) else: seq.append(seq[x - 1] + x) x += 1 return seq def fortunate(n): # https://en.wikipedia.org/wiki/Fortunate_number pprod = 2 lastp = 2 seq = [0]*n k = 0 while seq[-1] == 0: nextp = next_prime(pprod + 2) seq[k] = nextp-pprod lastp = next_prime(lastp) pprod *= lastp k += 1 return seq #### ---- "primos" method for finding the next prime ---- #### # see: https://codegolf.stackexchange.com/questions/10701/fastest-code-to-find-the-next-prime # legendre symbol (a|m) # note: returns m-1 if a is a non-residue, instead of -1 def legendre(a, m): return pow(a, (m-1) >> 1, m) # strong probable prime def is_sprp(n, b=2): d = n-1 s = 0 while d&1 == 0: s += 1 d >>= 1 x = pow(b, d, n) if x == 1 or x == n-1: return True for r in range(1, s): x = (x * x)%n if x == 1: return False elif x == n-1: return True return False # lucas probable prime # assumes D = 1 (mod 4), (D|n) = -1 def is_lucas_prp(n, D): P = 1 Q = (1-D) >> 2 # n+1 = 2**r*s where s is odd s = n+1 r = 0 while s&1 == 0: r += 1 s >>= 1 # calculate the bit reversal of (odd) s # e.g. 19 (10011) <=> 25 (11001) t = 0 while s > 0: if s&1: t += 1 s -= 1 else: t <<= 1 s >>= 1 # use the same bit reversal process to calculate the sth Lucas number # keep track of q = Q**n as we go U = 0 V = 2 q = 1 # mod_inv(2, n) inv_2 = (n+1) >> 1 while t > 0: if t&1 == 1: # U, V of n+1 U, V = ((U + V) * inv_2)%n, ((D*U + V) * inv_2)%n q = (q * Q)%n t -= 1 else: # U, V of n*2 U, V = (U * V)%n, (V * V - 2 * q)%n q = (q * q)%n t >>= 1 # double s until we have the 2**r*sth Lucas number while r > 0: U, V = (U * V)%n, (V * V - 2 * q)%n q = (q * q)%n r -= 1 # primality check # if n is prime, n divides the n+1st Lucas number, given the assumptions return U == 0 # primes less than 212 small_primes = set([ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,101,103,107,109,113, 127,131,137,139,149,151,157,163,167,173, 179,181,191,193,197,199,211]) # pre-calced sieve of eratosthenes for n = 2, 3, 5, 7 indices = [ 1, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,101,103,107,109,113,121,127,131, 137,139,143,149,151,157,163,167,169,173, 179,181,187,191,193,197,199,209] # distances between sieve values offsets = [ 10, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 6, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2,10, 2] max_int = 2147483647 # an 'almost certain' primality check def is_prime(n): if n < 212: return n in small_primes for p in small_primes: if n%p == 0: return False # if n is a 32-bit integer, perform full trial division if n <= max_int: i = 211 while i*i < n: for o in offsets: i += o if n%i == 0: return False return True # Baillie-PSW # this is technically a probabalistic test, but there are no known pseudoprimes if not is_sprp(n): return False a = 5 s = 2 while legendre(a, n) != n-1: s = -s a = s-a return is_lucas_prp(n, a) # next prime strictly larger than n def next_prime(n): if n < 2: return 2 # first odd larger than n n = (n + 1) | 1 if n < 212: while True: if n in small_primes: return n n += 2 # find our position in the sieve rotation via binary search x = int(n%210) s = 0 e = 47 m = 24 while m != e: if indices[m] < x: s = m m = (s + e + 1) >> 1 else: e = m m = (s + e) >> 1 i = int(n + (indices[m] - x)) # adjust offsets offs = offsets[m:]+offsets[:m] while True: for o in offs: if is_prime(i): return i i += o ############ end of primos method ############## def triangular_number(n): # https://en.wikipedia.org/wiki/Triangular_number # number of objects that can form equilateral triangles return (n*n + n) // 2 def triangular(n): # https://en.wikipedia.org/wiki/Triangular_number # numbers of objects that can form equilateral triangles if n == 0: return [0] seq=[0]*n for i in range(1, n): seq[i] = (i*i + i) // 2 return seq def tetrahedral_number(n): # https://en.wikipedia.org/wiki/Tetrahedral_number # generate the n-th tetrahedral number, numbers # of objects that form tetrahedron pyramids return (n+1)*(n+2)*(n+3)//6 def tetrahedral(n): # https://en.wikipedia.org/wiki/Tetrahedral_number # generate the n first tetrahedral numbers seq = [0]*n i = 1 while seq[-1] == 0: seq[i] = (i+1)*(i+2)*(i+3)//6 i += 1 return seq def pyramidal_number(n): # https://en.wikipedia.org/wiki/Square_pyramidal_number # generate the n-th square pyramidal number, these are # numbers of object that form sqare based pyramids or # that represents the number of stacked spheres in a # pyramid with a square base return (2*n**3+3*n**2+n)//6 def pyramidal(n): # https://en.wikipedia.org/wiki/Square_pyramidal_number # generate the n first pyramidal numbers seq = [0]*n i = 1 while seq[-1] == 0: seq[i] = (2*i**3+3*i**2+i)//6 i += 1 return seq def star_number(n): # https://en.wikipedia.org/wiki/Star_number # number of object to form a (filled) centered hexagram (six-pointed star), return 6*n*(n-1)+1 def star(n): # https://en.wikipedia.org/wiki/Star_number # generate the n first star numbers seq = [0]*n i = 1 while seq[-1] == 0: seq[i] = 6*i*(i-1)+1 i += 1 return seq def octangula_number(n): # https://en.wikipedia.org/wiki/Stella_octangula_number # number of object to form a stella octangula return 2*n**3-n def octangula(n): # https://en.wikipedia.org/wiki/Stella_octangula_number # generate the n first octangula numbers seq = [0]*n i = 1 while seq[-1] == 0: seq[i] = 2*i**3-i i += 1 return seq