Posts: 101
Threads: 0
Joined: Jan 2021
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
Posts: 419
Threads: 34
Joined: May 2019
(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.
Posts: 101
Threads: 0
Joined: Jan 2021
Mar-08-2021, 08:21 PM
(This post was last modified: Mar-08-2021, 08:21 PM by Serafim.)
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...
Posts: 101
Threads: 0
Joined: Jan 2021
Mar-08-2021, 08:55 PM
(This post was last modified: Mar-08-2021, 08:55 PM by Serafim.)
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
Posts: 101
Threads: 0
Joined: Jan 2021
Mar-10-2021, 10:36 AM
(This post was last modified: Mar-10-2021, 10:36 AM by Serafim.
Edit Reason: Corrected an error
)
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.
Posts: 101
Threads: 0
Joined: Jan 2021
Mar-10-2021, 09:19 PM
(This post was last modified: Mar-10-2021, 09:19 PM by Serafim.)
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..
Posts: 419
Threads: 34
Joined: May 2019
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.
Posts: 101
Threads: 0
Joined: Jan 2021
Mar-11-2021, 08:32 AM
(This post was last modified: Mar-11-2021, 08:32 AM by Serafim.)
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
Posts: 101
Threads: 0
Joined: Jan 2021
Mar-12-2021, 09:55 AM
(This post was last modified: Mar-12-2021, 09:55 AM by Serafim.)
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.
Posts: 101
Threads: 0
Joined: Jan 2021
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.
|