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