Mar-12-2021, 04:40 PM
wow... later today I'll grab some sample code for a panda3d project and look it over and get plot 3d points I want. I can do the GUI with pygame. I'll start with "regen" button.
[PyGame] Fibonacci graphics ideas?
|
Mar-12-2021, 04:40 PM
wow... later today I'll grab some sample code for a panda3d project and look it over and get plot 3d points I want. I can do the GUI with pygame. I'll start with "regen" button.
Mar-14-2021, 08:57 AM
I implemented a method to generate fortunate numbers but it was too slow due to my naive implementation of checking primes and to find the smallest prime larger than a certain number, which is required for fortunate number generation. So I looked around and found an astonishingly quick method on codegolf.stackexchange where "fortunately" the winner, "primo", used Python. It is a probability based method that speeds up primality tests several magnitudes. It is still a little slow if you generate many numbers. A hundred is OK but with your ideas one probably uses many more. In any case, here goes:
from time import time def fortunate(n): # https://en.wikipedia.org/wiki/Fortunate_number pprod = 2 lastp = 2 seq = [] while len(seq) < n: m = 2 while not is_prime(pprod + m): m +=1 seq.append(m) lastp = next_prime(lastp) pprod *= lastp 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 for finding the next prime ---- #### start = time() print(fortunate(100)) print(time()-start)And the output: It still isn't that fast, 2.5 sec for 100 numbers. with my method for checking primality it took a couple of hours...So I tried to tweak it to make it faster but with this final version of the function "fortunate" it still takes 2.16 sec: 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
Mar-15-2021, 03:31 PM
Serafim.... your OCD is showing! lol!
It's busy for me with job and garden, so I'm going to discard all my 3d work and proceed 2d in this project. Plus, since I haven't actually played any games in a long time I'm also playing through Zelda 2: The Adventure of Link. :) While I'm doing that, I could use your help making some sort of limiters for these math functions so I can put check boxes and sliders in my GUI, and the functions (or limiting function that calls them) return usable numbers. 19**12345 can't be used as screen (x,y).
Well, whatever OCD I suffer from, gaming is not one of them .
I think that first of all you need to consider which of the number sequences you want to use. Not all of them have interesting graphical interpretations. Once that's done I will try to, if time permits, establish reasonable limits, though I don't know exactly what you have in mind. Length limits depending on generation time? Or what? By the way, here is another number sequence (this one is simple), the number of elements that can be stacked to form equilateral triangles: def triangular(n): # https://en.wikipedia.org/wiki/Triangular_number if n == 0: return [0] seq=[0]*n for i in range(1, n): seq[i] = (i*i + i) // 2 return seq print(triangular(100))Some of the sequence functions may need tweaking to be usable. I even thought that some sequences that are time consuming to generate could be stored in some database that offer B-tree indices. I'll look into that to see if it may speed up some hard to generate sequences (provided that you intend to use them). In the general case, opening and closing databases is in itself time consuming.
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 |
|