## Pentabonacci Numbers

### December 13, 2019

You don’t need a computer program to figure out which members of the sequence are odd: the sequence starts with an even number, then the pattern two odds and four evens continues indefinitely, so the nth member of the sequence is odd when n (mod 6) ∈ {2, 3}. And our Standard Prelude makes it easy to calculate the sequence:

```> (iterate 30 + 0 1 1 2 4)
(0 1 1 2 4 8 16 31 61 120 236 464 912 1793 3525 6930 13624
26784 52656 103519 203513 400096 786568 1546352 3040048
5976577 11749641 23099186 45411804 89277256)```

You can run the program at https://ideone.com/i3yHrt.

Pages: 1 2

### 16 Responses to “Pentabonacci Numbers”

1. Steve said

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.

```
2. Zack said

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!

3. matthew said
```pdiv (a:s) t = a : pdiv (zipWith (-) (s ++ repeat 0) (map (*a) t)) t
take 20 (pdiv  [-1,-1])
take 20 (pdiv [0,1] [-1,-1,-1,-1,-1])
```
4. matthew said

That Haskell is using the generating function from Mathworld and polynomial division to generate the sequence (and the Fibonacci numbers as well).

5. Steve said

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]

```
6. matthew said

@Steve: very nice, but any chance of an explanation what that code is doing?

7. Steve said

@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 list

```

8. matthew said

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]) >>
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])
```
9. matthew said

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.
```
10. Daniel said

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:

```1: [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
2: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181]
3: [0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768, 10609, 19513, 35890]
4: [0, 1, 1, 2, 4, 8, 15, 29, 56, 108, 208, 401, 773, 1490, 2872, 5536, 10671, 20569, 39648, 76424]
5: [0, 1, 1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, 3525, 6930, 13624, 26784, 52656, 103519]
6: [0, 1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 117920]
7: [0, 1, 1, 2, 4, 8, 16, 32, 64, 127, 253, 504, 1004, 2000, 3984, 7936, 15808, 31489, 62725, 124946]
8: [0, 1, 1, 2, 4, 8, 16, 32, 64, 128, 255, 509, 1016, 2028, 4048, 8080, 16128, 32192, 64256, 128257]
9: [0, 1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 511, 1021, 2040, 4076, 8144, 16272, 32512, 64960, 129792]
10: [0, 1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1023, 2045, 4088, 8172, 16336, 32656, 65280, 130496]
```
11. Daniel said

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.

12. Steve said

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 list
```
13. matthew said

Inspired 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 = +*(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)]}')
```
14. Daniel said

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:

```1: [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
2: [0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1]
3: [0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0]
4: [0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0]
5: [0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1]
6: [0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0]
7: [0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0]
8: [0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1]
9: [0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0]
10: [0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0]
```
15. said
```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]]
```