loading...

Daily Challenge #102 - Pentabonacci

thepracticaldev profile image dev.to staff ・1 min read

Given the following sequence, what is the number of total values for the odd terms of the sequence, up to the n-th term. The number n will be given as a positive integer.

f(0) = 0
f(1) = 1
f(2) = 1
f(3) = 2
f(4) = 4;
f(n) = f(n-1) + f(n-2) + f(n-3) + f(n-4) + f(n-5);

1 is the only value that will be duplicated in the sequence, it should only be counted once.

Examples:

countPentafib(5) => 1
because the terms up to 5 are: [0, 1, 1, 2, 4, 8], 1 is the only odd and is only counted once.

countPentafib(10) => 3
[1, 1, 31, 61] are each odd and should be counted.

countPentafib(15) => 5
[1, 1, 31, 61, 1793, 3525] are all odd and 1 is only counted once.

Good luck!


This challenge comes from raulbc777 on CodeWars. Thank you to CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!

Want to propose a challenge idea for a future post? Email yo+challenge@dev.to with your suggestions!

Discussion

pic
Editor guide
Collapse
aminnairi profile image
Amin

Haskell

countPentaFibonacci :: Int -> Int
countPentaFibonacci limit 
    | limit < 1 = 0
    | limit == 1 = 1
    | otherwise = length $ filter odd $ map f [2..limit]
    where
        f 0 = 0
        f 1 = 1
        f 2 = 1
        f 3 = 2
        f 4 = 4
        f x = f (x - 1) + f (x - 2) + f (x - 3) + f (x - 4) + f (x - 5)

Online playground

Hosted on Repl.it.

Collapse
citizen428 profile image
Michael Kohl

F#, with a simple sequence expression for generating the Pentonacci numbers.

module DailyChallenge

let pentaFibs =
    let rec pentaFibseq n1 n2 n3 n4 n5 =
        seq {
            let next = n1 + n2 + n3 + n4 + n5
            yield next
            yield! pentaFibseq n2 n3 n4 n5 next
        }
    seq {
        yield 0
        yield 1
        yield 1
        yield 2
        yield 4
        yield! (pentaFibseq 0 1 1 2 4)
    }

let countPentafib n =
    match n with 
    | _ when n <= 0 -> failwith "Invalid input, n needs to be > 0"
    | 1 -> 0
    | 2 -> 1
    | _ ->
        pentaFibs
        |> Seq.take n
        |> Seq.skip 2
        |> Seq.sumBy (fun x -> if x % 2 = 1 then 1 else 0)

Tests:

module DailyChallengeTests

open FsUnit.Xunit
open Xunit
open DailyChallenge

[<Fact>]
let ``countPentafib 5 should be 1``() =
    countPentafib 5 |> should equal 1

[<Fact>]
let ``countPentafib 10 should be 3``() =
    countPentafib 10 |> should equal 3

[<Fact>]
let ``countPentafib 15 should be 5``() =
    countPentafib 15 |> should equal 5

[<Fact>]
let ``countPentafib 1 should be 0``() =
    countPentafib 1 |> should equal 0

[<Fact>]
let ``countPentafib 2 should be 1``() =
    countPentafib 2 |> should equal 1

[<Fact>]
let ``countPentafib -1 should fail``() =
    shouldFail (fun () -> countPentafib -1 |> ignore)
Collapse
colorfusion profile image
Melvin Yeo

In Golang, assuming input is a valid integer.

package main

var fibMap = map[int]int{
    0: 0,
    1: 1,
    2: 1,
    3: 2,
    4: 4,
}

func f(n int) int {
    if n <= 4 {
        return fibMap[n]
    }

    result := f(n-1) + f(n-2) + f(n-3) + f(n-4) + f(n-5)
    fibMap[n] = result
    return result
}

func countPentafib(n int) int {
    odds := make(map[int]bool)
    for i := 0; i < n; i++ {
        result := f(i)
        if result%2 == 1 {
            odds[result] = true
        }
    }

    return len(odds)
}

func main() {
}

Tests

package main

import "testing"

func TestPentaFib(t *testing.T) {
    params := map[int]int{
        5:  1,
        10: 3,
        15: 5,
    }
    for key, value := range params {
        result := countPentafib(key)

        if result != value {
            t.Errorf("Incorrect answer for %d, expected: %d, got: %d", key, value, result)
        }
    }
}
Collapse
erezwanderman profile image
erezwanderman

Javascript:

Pentabonacci = n => n < 2 ? n : Math.floor((n - 1) / 6) + Math.floor((n - 2) / 6) + 1