Pentabonacci Numbers
December 13, 2019
The sequence of pentabonacci numbers is defined as the sequence beginning 0, 1, 1, 2, 4, and continuing with each subsequent number the sum of the five previous members of the sequence. The sequence grows very quickly; the 20th member of the sequence (counting the 0 that begins the sequence as the first member) is 103519.
Your task is to write a program that calculates the first n members of the pentabonacci sequence and determine the rule that states whether the nth member of the sequence is even or odd. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
Klong version
Program: go::{[s];s::pb(x);.p(($x),": ",($s)," (",:[s!2;"Odd";"Even"],")")} pb::{[l n];l::[0 1 1 2 4];n::x;:[n<6;l@n-1;pb2(n;l)]} pb2::{[l n];n::x;l::y;*|(n-5){x;l::l,+/((#l)-5)_l}:*1} Run: go'1+!40;:ok 1: 0 (Even) 2: 1 (Odd) 3: 1 (Odd) 4: 2 (Even) 5: 4 (Even) 6: 8 (Even) 7: 16 (Even) 8: 31 (Odd) 9: 61 (Odd) 10: 120 (Even) 11: 236 (Even) 12: 464 (Even) 13: 912 (Even) 14: 1793 (Odd) 15: 3525 (Odd) 16: 6930 (Even) 17: 13624 (Even) 18: 26784 (Even) 19: 52656 (Even) 20: 103519 (Odd) 21: 203513 (Odd) 22: 400096 (Even) 23: 786568 (Even) 24: 1546352 (Even) 25: 3040048 (Even) 26: 5976577 (Odd) 27: 11749641 (Odd) 28: 23099186 (Even) 29: 45411804 (Even) 30: 89277256 (Even) 31: 175514464 (Even) 32: 345052351 (Odd) 33: 678355061 (Odd) 34: 1333610936 (Even) 35: 2621810068 (Even) 36: 5154342880 (Even) 37: 10133171296 (Even) 38: 19921290241 (Odd) 39: 39164225421 (Odd) 40: 76994839906 (Even) :ok Rule: 1. The first entry is even. 2. The succeeding entries are grouped in 6 entries: The first 2 are odd, and the next 4 are even.My implementation in Julia: https://pastebin.com/c6CEEJ2e. Note that the BigInt type is preferred as the numbers in the sequence soon grow beyond what Int128 can handle.
Using the map(isodd, p) command, for a large enough array p containing a series of Pentabonacci numbers, it becomes evident that the pattern that these numbers follow is: O,O,E,E,E,E (O = odd, E = even), starting from the 2nd number onwards.
Have a nice weekend!
http://mathworld.wolfram.com/PentanacciNumber.html
That Haskell is using the generating function from Mathworld and polynomial division to generate the sequence (and the Fibonacci numbers as well).
Matthew’s Haskell solution made me want to shorten mine:
Klong version
Code: {[l n];l::[0 1 1 2 4];:[(n::x-5)<1;l@n+4;*|n{x;l::l,+/5#|l}:*1]}'1+!20 Run: [0 1 1 2 4 8 16 31 61 120 236 464 912 1793 3525 6930 13624 26784 52656 103519]@Steve: very nice, but any chance of an explanation what that code is doing?
@matthew – Here you go. Thanks for asking
{[l n];l::[0 1 1 2 4];:[(n::x-5)<1;l@n+4;*|n{x;l::l,+/5#|l}:*1]}'1+!20 { - Start of outermost function [l n] - Instantiate local variables ; - Semicolons separate statements l::[0 1 1 2 4] - Set l equal to array :[ - Start of If / Then / Else construct (n::x-5)<1 - x is the argument submitted to the function. Set n equal to x-5 and see if the difference is less than 5 l@n+4 - True portion of construct (return 1 of 5 numbers of array depending upon the value of n) *|n{x;l::l,+/5#|l}:*1 - False portion of contruct n{x;l::l,+/5#|l}:*1 - This is a for loop that proceeds from 1 to n. The value of the iterator inside the function {} is placed in x x; - Supply x to the function - This lets the system know that the function is a monad (Reading from right to left in the innermost function) l - The list |l - Reverse the list 5# - Get the first 5 elements of the list l, - Add those elements to the list l:: - Give the list the new value of the list } - End of the innermost function *| - Reverse the list and get the 1st element ] - End of the If / Then / Else construct } - End of the outermost function !20 - Generate a list from 0 to 19 1+ - Add 1 to each element of list and the list becomes 1 to 20 {...}'1+!20 - Execute outer function once for each element of listWould you mind doing this for your Haskell example?
Thanks, great explanation. Here’s some light on the Haskell:
-- A sequence such as the Fibonacci numbers [a,b,c,...] can be -- represent by a generating function, f(x) where: -- f(x) = a + bx + cx^2 + ... -- and f might have a finite representation as the division of two -- polynomials, eg. 1/(1-x-x^2) for the Fibonacci numbers. We can -- construct the series by directly performing the polynomial -- division. -- 'Normal' polynomial division, where if the dividend is of a smaller -- degree than the divisor, we just get a remainder polynomial, so we -- use this slightly peculiar procedure that starts from the other end -- of the polynomial and, if the division isn't exact won't terminate, -- but generate the infinite number of terms desired (it's a bit like -- how division works with p-adic numbers, I'm sure there must be a -- name for it). -- A general law about division: -- X/Y = (kY - kY + X)/Y = k + (X - kY)/Y -- and we make the simplifying assumption that the constant -- coefficient of divisor is 1: -- (a + bx + cx^2 + ...) / (1 + Bx + Cx^2 + ...) = -- a + [(a + bx + cx^2 + ...) - (a + aBx + aCx^2)]/(1 + Bx + Cx^2 + ...) = -- a + [(b-aB)x + (c - aC)x^2 + ...]/(1 + Bx + Cx^2 + ...) = -- a + x [(b-aB) + (c - aC)x + ...]/(1 + Bx + Cx^2 + ...) -- and we have got the first value, a, of the output (so in Haskell, -- this can be used to generate a lazy list). -- Represent a polynomial (a+bx+cx^2+..) as [a,b,c..] and now we can -- represent the above calculation as: -- pdiv [a,b,c,..] [1,B,C..] = a : pdiv [b-aB,c-aC,..] [1,B,C..] -- [b-aB,c-aC,..] is just zipWith (-) [b,c,...] (map (a*) [B,C,.]): -- zipWith (-) subtracts elements of one list from elements of another -- and map (a*) multiplies each element of a list by a. -- so now we have: -- pdiv (a:s) (1:t) = a : pdiv (zipWith (-) s (map (*a) t)) (1:t) -- Finally we need to pad out s to the same length as t, which -- we can do by appending an infinite stream of 0's (zipWith -- terminates as soon as one of its arguments does). We should also -- pad t, though that isn't needed for the Fibonacci sequences: pdiv (a:s) (1:t) = a : pdiv (zipWith (-) (s ++ repeat 0) (map (*a) t)) (1:t) main = print(take 20 $ pdiv [1] [1,-1,-1]) >> print(take 20 $ pdiv [1] [1,-1,-1,-1]) >> print(take 20 $ pdiv [1] [1,-1,-1,-1,-1]) >> print(take 20 $ pdiv [1] [1,-1,-1,-1,-1,-1])For some reason, WordPress won’t accept the output for that code as a comment – as you can guess, it’s the Fibonacci, Tribonacci, etc. numbers, of course.
More comments on the code itself:
pdiv -- Define a function called pdiv, with parameters: (a:s) -- Dividend list, first element a, rest is t (1:t) -- Divisor list, first element must be 1, rest is t = -- function result is: a : -- list with a at the beginning pdiv -- and result of recursive call to pdiv for rest of list (zipWith (-) -- first parameter is the elementwise difference of: (s ++ repeat 0) -- list s, padded with 0's as far as needed (map (*a) t)) -- elements of t, multiplied by a (1:t) -- and the original divisor list.Here’s a solution in Python with a function for calculating the mth Fibonacci n-step number. n is 5 for the Pentanacci numbers.
def n_step_fib(n, m): out = [0, 1, 1][:m] while len(out) < m: x = 2 * out[-1] if len(out) > n: x -= out[-(n + 1)] out.append(x) return out for n in range(1, 11): print(f'{n}: {n_step_fib(n, 20)}')Output:
My solution calculates the first m numbers. I mistakenly wrote that wrong in my last post, which suggested the function only returns the mth number alone.
Made a change and an addition to my explanation for the current Klong solution (See entries marked with ***):
{[l n];l::[0 1 1 2 4];:[(n::x-5)<1;l@n+4;*|n{x;l::l,+/5#|l}:*1]}'1+!20 { - Start of outermost function [l n] - Instantiate local variables ; - Semicolons separate statements l::[0 1 1 2 4] - Set l equal to array :[ - Start of If / Then / Else construct (n::x-5)<1 - x is the argument submitted to the function. Set n equal to x-5 and see if the difference is less than 5 l@n+4 - True portion of construct (return 1 of 5 numbers of array depending upon the value of n) *|n{x;l::l,+/5#|l}:*1 - False portion of contruct n{x;l::l,+/5#|l}:*1 - This is a for loop that proceeds from 1 to n. The value of the iterator inside the function {} is placed in x x; - Supply x to the function - This lets the system know that the function is a monad (Reading from right to left in the innermost function) l - The list |l - Reverse the list 5# - Get the first 5 elements of the list *** +/ - Get sum of those 5 elements *** *** l, - Add the sum to the list *** l:: - Give the list the new value of the list } - End of the innermost function *| - Reverse the list and get the 1st element ] - End of the If / Then / Else construct } - End of the outermost function !20 - Generate a list from 0 to 19 1+ - Add 1 to each element of list and the list becomes 1 to 20 {...}'1+!20 - Execute outer function once for each element of listInspired by Daniel’s solution, here’s a variation using Python generators – this one omits the 0 at the start of the sequences:
def n_step_fib(n): s = [1]+[0]*(n-1) a,i = 1,0 while True: assert(a == sum(s)) yield a s[i],a,i = a,2*a-s[i],(i+1)%n for n in range(1, 6): g = n_step_fib(n) print(f'{n}: {[next(g) for _ in range(19)]}')Here’s a Python function for calculating the parity of the mth Fibonacci n-step number, returning 0 for evens and 1 for odds.
def n_step_fib_parity(n, m): return int(m > 0 and (m - 1) % (n + 1) < 2) for n in range(1, 11): print(f'{n}: {[n_step_fib_parity(n, x) for x in range(20)]}')Output:
import numpy as np a = np.matrix([[0,1,0,0,0], [0,0,1,0,0], [0,0,0,1,0], [0,0,0,0,1], [1,1,1,1,1]], dtype=object) print(a**18); # [[3525 5318 6230 6694 6930] # [6930 10455 12248 13160 13624] # [13624 20554 24079 25872 26784] # [26784 40408 47338 50863 52656] # [52656 79440 93064 99994 103519]]