Python Forum
[PyGame] Fibonacci graphics ideas?
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
[PyGame] Fibonacci graphics ideas?
#11
I played a little with your gen_fib, letting start to always be 1 and to generate any of the generalized fib sequences (shortened the name to gen_ib, but ...)
def gen_ib(length, n):
    '''Function to generate the n-th number sequence
       generalization of the Fibonacci number sequence.
       n == 2 => Fibonacci number sequence
       n == 3 => "Tribonacci" number sequence
       n == 4 => "Tetranacci" number sequence
       and so on ...'''
    if n < 2:
        return []
    buffer = [0]*(n-1)+[1]
    if length <= n:
        return buffer[:length]
    b = 0
    for j in range(length-n):
        buffer.append(sum(buffer[b:]))
        b += 1
    return(buffer)
Then I tested it with
for i in range(2,10):
    print(gen_ib(20+i, i))
and it works fine.
Output:
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946] [0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768, 10609, 19513, 35890, 66012, 121415] [0, 0, 0, 1, 1, 2, 4, 8, 15, 29, 56, 108, 208, 401, 773, 1490, 2872, 5536, 10671, 20569, 39648, 76424, 147312, 283953] [0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, 3525, 6930, 13624, 26784, 52656, 103519, 203513, 400096] [0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 117920, 233904, 463968] [0, 0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 64, 127, 253, 504, 1004, 2000, 3984, 7936, 15808, 31489, 62725, 124946, 248888, 495776] [0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 64, 128, 255, 509, 1016, 2028, 4048, 8080, 16128, 32192, 64256, 128257, 256005, 510994] [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 511, 1021, 2040, 4076, 8144, 16272, 32512, 64960, 129792, 259328, 518145]
Use it, modify it to your taste or just skip it if it is not useful in your line of ideas. I'm just playing around a little when taking a rest from my own work.
michael1789 likes this post
Reply
#12
(Mar-06-2021, 12:44 PM)Serafim Wrote: Use it, modify it to your taste or just skip it if it is not useful in your line of ideas. I'm just playing around a little when taking a rest from my own work.

Good work. I'm just playing around too. I think the path here will end with a Fractal() class that's __init__ method grabs from a bunch of functions (ie, gen_fib, yours, etc) to construct the algorithm for building that fractal.

Today I'm working on using pygame.Vector2.rotate() to try and curve each segment of points in way that keeps them on screen. I want them to spiral around the origin of the fractal, or have it grow towards the mouse pointer. Then add branching.

After that I think I need to convert to pygame.Vector3 and learn how to plot 3d points in 2d.
Reply
#13
Hi again!

Some time spent on the internet departing from the wikipedia page on number sequences gave these number sequence functions. Mostly number sequences with some graphical interpretation.
from itertools import groupby
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]*(n-1)+[start]
    b = 0
    for j in range(length):
        seq.append(sum(seq[b:]))
        b += 1
    return seq[0:length+1]

def lucas(n):
    # https://en.wikipedia.org/wiki/Lucas_number
    seq = [2, 1]
    while len(seq) < n:
        seq.append(seq[-1]+seq[-2])
    return seq[:n]


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 = []
    for i in range(n):
        seq.append(partitions_count(i))
    return seq

def catalan(n):
    # https://en.wikipedia.org/wiki/Catalan_number
    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(n):
    # https://en.wikipedia.org/wiki/Lazy_caterer%27s_sequence
    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(n):
    # https://en.wikipedia.org/wiki/Pronic_number
    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
All tested and working! More will come...
Reply
#14
Forgot to say that the generalization on fibonacci, "fibn", has a new, simplified form. I no longer look for special cases. Instead I slice the resulting sequence. Shorter code but probably not as time efficient (I imagine).
Also, the "look_and_find" function generate a sequence of string representations of integers, must be converted to integers. Forgot to do it...
michael1789 likes this post
Reply
#15
A couple of more sequences:
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/Abundant_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
I'm going to skip "untouchable numbers" for now as I don't find a good algorithm. The only implementation so far is not in Python and it is also prohibitively slow for numbers above 5. Maybe later, I do have a couple of ideas ...

Interestingly, I found an algorithm on GeeksForGeeks but it is incorrect.
Reply
#16
I don't know if pratical numbers are interesting but if they are this implementation is a bit slow (a couple of seconds for a list with 100 practical numbers), maybe it can be speeded up a bit.
from itertools import combinations

def practical(n):
    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
by the way, "is_practical" is taken from stackoverflow..
Reply
#17
Good Work! I'm still working on visualization. I think I'm going to trash what I have and find an existing 3d module. Panda3d or something. I want to grow 3d trees and crystals fractally. Have a UI to grow and show the shapes. UI I can do, sliders and buttons, etc, it's plotting and rotating and projecting 3d points in 2d I haven't done, but I'll let panda do it for now lol.
Reply
#18
I'll continue to, during breaks, look at integer sequences. If there are other kinds of series and sequences that are interesting, let me know. I have also done a lot of numerical programming, if things like that pop up. What is new to me is to do it in Python. GUI and stuff like that is not my main focus. In Python I have used tkinter, ttk and PySimpleGUI. That's all, and these are not suited for the things you try to do. If time permits I'll take a look at Pandas, but I probably won't have time.

By the way, here is another sequence function:
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
Reply
#19
I thought that it would be more efficient to use numpy arrays and tried with "fibn":
def fibn(start, length, n):
    if n < 2:
        return []
    seq = np.zeros(length, dtype='uint64')
    seq[n-1] = start
    if length < n:
        return seq
    for i in range(length-n):
        seq[i+n] = sum(seq[i:i+n])
    return seq
but max-value for 64 bit unsigned integers is 2**64 = 18446744073709551616, so after fib(93) = 12200160415121876738 things get strange with cancellations et.c. so I changed dtype to "object".
def fibn(start, length, n):
    if n < 2:
        return []
    seq = np.zeros(length, dtype=object)
    seq[n-1] = start
    if length < n:
        return seq
    for i in range(length-n):
        seq[i+n] = sum(seq[i:i+n])
    return seq
Then it works with arbitrarily large numbers but I am concerned about efficiency. In any case, it must be faster than using standard lists as numpy arrays are consecutive cells in memory so I'll change all my implementations and then make some kind of time and space check to see which is to prefer in each case.
A time check shows that the numpy implementation on the average takes 3 times longer than the standard list version. 0.0002846717834472656 sec for the standard and 0.0009121894836425781 sec for the numpy version when generating the first 1000 fibonacci numbers and for 100000 fib numbers 0.36421632766723633 sec for standard list and 0.44461560249328613 s for numpy version = 1.22 times longer for numpy.
Reply
#20
After reading a lot on the subject I decided to abandon the conversion to numpy as "dtype=object" is absolutely necessary for manipulating very large numbers (larger than 2**64) and using numpy arrays with dtype=object means that the array in itself is in contiguous blocks of memory, but the content are pointers to the integers so they have to be looked up in the same manner as in python lists. This article explains the details of standard lists in Python.
In any case, I didn't get better performance except in special cases with specific array lengths, so I won't go on with numpy. It is excellent in many cases but I seem to have found a case where it isn't.
Reply


Forum Jump:

User Panel Messages

Announcements
Announcement #1 8/1/2020
Announcement #2 8/2/2020
Announcement #3 8/6/2020