Sum of combinations with repetition

Question

Write the shortest code you can solving the following problem:

Input:

An integer X with 2 <= X and X <= 100

Output:

Total combinations of 2, 3, and 5 (repetition is allowed, order matters) whose sum is equal to X.

Examples:

Input: 8

Output: 6, because the valid combinations are:

3+5
5+3
2+2+2+2
2+3+3
3+2+3
3+3+2

Input: 11

Output: 16, because the valid combinations are

5+3+3
5+2+2+2
3+5+3
3+3+5
3+3+3+2
3+3+2+3
3+2+3+3
3+2+2+2+2
2+5+2+2
2+3+3+3
2+3+2+2+2
2+2+5+2
2+2+3+2+2
2+2+2+5
2+2+2+3+2
2+2+2+2+3

Input: 100

Output: 1127972743581281, because the valid combinations are ... many

Input and output can be of any reasonable form. The lowest byte count in each language wins. Standard code-golf rules apply.

Answer 1

Python 2, 46 45 bytes

thanks to xnor for -1 byte

f=lambda n:n>0and f(n-2)+f(n-3)+f(n-5)or n==0

Try it online!

Answer 2

Oasis, 9 bytes

cd5e++VT1

Try it online!

Explanation

        1    # a(0) = 1
       T     # a(1) = 0, a(2) = 1
      V      # a(3) = 1, a(4) = 1

             # a(n) = 
c    +       # a(n-2) +
 d  +        # a(n-3) +
  5e         # a(n-5)

Answer 3

Pyth, 9 bytes

/sM{y*P30

Try it here!

Pyth, 16 bytes

l{s.pMfqT@P30T./

Try it here

How?

1. Generates the prime factors of 30, namely [2, 3, 5], gets the powerset of it repeated N times, removes duplicate elements, sums each list and counts the occurrences of N in that.

2. For each integer parition p, it checks whether p equals p ∩ primefac(30). It only keeps those that satisfy this condition, and for each remaining partition k, it gets the list of k's permutations, flattens the resulting list by 1 level, deduplicates it and retrieves the length.

Answer 4

Jelly, 11 bytes

5ÆRẋHŒPQḅ1ċ

Try it online!

How it works

5ÆRẋHŒPQḅ1ċ -> Full program. Argument: N, an integer.
5ÆR         -> Pushes all the primes between 2 and 5, inclusively.
   ẋH       -> Repeat this list N / 2 times.
     ŒP     -> Generate the powerset.
       Q    -> Remove duplicate entries.
        ḅ1  -> Convert each from unary (i.e. sum each list)
          ċ -> Count the occurrences of N into this list.

Answer 5

JavaScript (ES6), 32 bytes

Same algorithm as in ovs' Python answer.

f=n=>n>0?f(n-2)+f(n-3)+f(n-5):!n

Test cases

f=n=>n>0?f(n-2)+f(n-3)+f(n-5):!n

console.log(f(8))
console.log(f(11))
console.log(f(13))

Answer 6

Perl, 38 bytes

Includes +1 for p

perl -pE '$_=1x$_;/^(...?|.{5})+$(?{$\++})\1/}{' <<< 11; echo

Interesting enough I have to use \1 to force backtracking. Usually I use ^ but the regex optimizer seems too smart for that and gives too low results. I'll probably have to start giving perl version numbers when using this trick since the optimizer can change at every version. This was tested on perl 5.26.1

This 49 is efficient and can actually handle X=100 (but overflows on X=1991)

perl -pe '$\=$F[@F]=$F[-2]+$F[-3]+$F[-5]for($F[5]=1)..$_}{' <<< 100;echo

Answer 7

C, 41 bytes

G(x){return x>0?G(x-2)+G(x-3)+G(x-5):!x;}

Try it online!

Answer 8

R, 56 49 47 bytes

Recursive approach from ovs's answer. Giuseppe shaved off those final two bytes to make it 47.

f=pryr::f(+`if`(x<5,x!=1,f(x-2)+f(x-3)+f(x-5)))

Try it online!

Answer 9

MATL, 15 bytes

:"5Zq@Z^!XsG=vs

Very inefficient: required memory is exponential.

Try it online!

How it works

:"       % For each k in [1 2 ... n], where n is implicit input
  5Zq    %   Push primes up to 5, that is, [2 3 5]
  @      %   Push k
  Z^     %   Cartesian power. Gives a matrix where each row is a Cartesian k-tuple
  !Xs    %   Sum of each row
  G=     %   Compare with input, element-wise
  vs     %   Concatenate all stack contents vertically and sum
         % Implicit end. Implicit display

Answer 10

05AB1E, 10 bytes

30fIиæÙOI¢

Try it online!

Answer 11

Pari/GP, 36 bytes

f(n)=if(n>0,f(n-2)+f(n-3)+f(n-5),!n)

Try it online!

---

Longer, but more efficient:

Pari/GP, 37 bytes

n->Vec(1/(1-x^2-x^3-x^5)+O(x^n++))[n]

Try it online!

Answer 12

Ruby, 41 bytes

f=->n{n<5?n==1?0:1:[n-5,n-2,n-3].sum(&f)}

Try it online!

This is a recursive solution, the recurcive call being: [n-5,n-2,n-3].sum(&f).

Answer 13

Jelly, 21 bytes

Œṗe€2,3,5$Ạ$ÐfŒ!Q$€ẎL

Try it online!

Surely can be golfed

Answer 14

Pyth, 12 bytes

l{fqQsTy*P30

This is horrendously inefficient and hits the memory limit for inputs above 5.

Try it online

Explanation

l{fqQsTy*P30
         P30   Get the prime factors of 30 [2, 3, 5].
        *   Q  Repeat them (implicit) input times.
       y       Take the power set...
  fqQsT        ... and filter the ones whose sum is the input.
l{             Count unique lists.

Answer 15

Proton, 32 bytes

f=n=>n>0?f(n-2)+f(n-3)+f(n-5):!n

Try it online!

Same approach as ovs' answer.

Answer 16

Wolfram Language (Mathematica), 43 bytes

Tr[Multinomial@@@{2,3,5}~FrobeniusSolve~#]&

Try it online!

Explanation: FrobeniusSolve computes all solutions of the unordered sum 2a + 3b + 5c = n, then Multinomial figures out how many ways we can order those sums.

Or we could just copy everyone else's solution for the same byte count:

f@1=0;f[0|2|3|4]=1;f@n_:=Tr[f/@(n-{2,3,5})]

Answer 17

Haskell, 40 bytes

f 0=1
f n|n<0=0|1>0=f(n-2)+f(n-3)+f(n-5)

Try it online!