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.

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,-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

    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]
    
    
  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
    
    

    Would you mind doing this for your Haskell example?

  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,-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])
    
  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 = [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)]}')
    
  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]]                                                                                                                                                                    
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: