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.

Welcome to PPCG! Unfortunately, here we don't answer general programming questions. However, you may be able to get help on Stack Overflow. Just be sure to check their help center out before asking. :) — Erik the Outgolfer, Feb 16 '18 at 17:23
Can someone reword this into a challenge? Because this would be a fun one. — Magic Octopus Urn, Feb 16 '18 at 18:44
@Shaggy Ugghhh... filtering through the challenges with the word sum in them was not a good idea to try to solve that inquiry... — Magic Octopus Urn, Feb 16 '18 at 19:04
I rewrote your question a bit to make it better fit on codegolf. I also changed the result for input 11 from 12 to 16. Of course feel free to fix this if I misunderstood your intention — Ton Hospel, Feb 16 '18 at 19:38

ovs · Accepted Answer · 2018-02-16 20:31:47Z

9

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!

edited Feb 16 '18 at 20:31

answered Feb 16 '18 at 19:51

ovs

33.4k2 gold badges20 silver badges94 bronze badges

\$\begingroup\$ Looks like and/or works and saves a byte: f=lambda n:n>0and f(n-2)+f(n-3)+f(n-5)or n==0. \$\endgroup\$ – xnor Feb 16 '18 at 20:13
\$\begingroup\$ @xnor thanks a lot. I just tried it the other way round \$\endgroup\$ – ovs Feb 16 '18 at 20:33

Add a comment |

Emigna · Accepted Answer · 2018-02-16 21:57:31Z

6

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)

edited Feb 16 '18 at 21:57

answered Feb 16 '18 at 21:50

Emigna

51.3k5 gold badges39 silver badges157 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

Pyth, 9 bytes

/sM{y*P30

Try it here!

Pyth, 16 bytes

l{s.pMfqT@P30T./

Try it here

How?

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

Mr. Xcoder · Accepted Answer · 2018-02-17 06:19:12Z

3

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.

edited Feb 17 '18 at 6:19

answered Feb 16 '18 at 20:00

Mr. Xcoder

40.7k9 gold badges71 silver badges211 bronze badges

\$\begingroup\$ Speed it up by replacing ³ with H (then it will time out at 12 rather than 6) \$\endgroup\$ – Jonathan Allan Feb 16 '18 at 23:03
\$\begingroup\$ @JonathanAllan Done, thanks. \$\endgroup\$ – Mr. Xcoder Feb 17 '18 at 6:19

Add a comment |

Ton Hospel · Accepted Answer · 2018-02-16 21:36:40Z

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

Steadybox · Accepted Answer · 2018-02-17 00:16:24Z

2

C, 41 bytes

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

Try it online!

edited Feb 17 '18 at 0:16

Steadybox

16k5 gold badges34 silver badges83 bronze badges

answered Feb 16 '18 at 23:50

0xrgb

1098 bronze badges

Add a comment |

Arnauld · Accepted Answer · 2018-02-19 15:31:28Z

2

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

edited Feb 19 '18 at 15:31

answered Feb 16 '18 at 19:48

Arnauld

143k13 gold badges147 silver badges523 bronze badges

Add a comment |

rturnbull · Accepted Answer · 2018-02-20 20:41:19Z

2

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!

edited Feb 20 '18 at 20:41

answered Feb 17 '18 at 2:46

rturnbull

3,74912 silver badges26 bronze badges

1

\$\begingroup\$ 48 bytes \$\endgroup\$ – Giuseppe Feb 19 '18 at 16:46
\$\begingroup\$ @Giuseppe Very nice improvement! \$\endgroup\$ – rturnbull Feb 20 '18 at 8:49
1

\$\begingroup\$ ah, you don't need the 0 (I didn't consider that before), as unary + will coerce to numeric as well. \$\endgroup\$ – Giuseppe Feb 20 '18 at 17:37

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

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

Mr. Xcoder · Accepted Answer · 2018-02-16 21:42:12Z

1

05AB1E, 10 bytes

30fIиæÙOI¢

Try it online!

answered Feb 16 '18 at 21:42

Mr. Xcoder

40.7k9 gold badges71 silver badges211 bronze badges

Add a comment |

MegaTom · Accepted Answer · 2018-02-20 23:40:50Z

1

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).

edited Feb 20 '18 at 23:40

answered Feb 17 '18 at 7:24

MegaTom

4,0111 gold badge16 silver badges24 bronze badges

Add a comment |

alephalpha · Accepted Answer · 2018-11-28 09:59:38Z

1

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!

edited Nov 28 '18 at 9:59

answered Feb 17 '18 at 2:36

alephalpha

24.4k5 gold badges38 silver badges101 bronze badges

Add a comment |

HyperNeutrino · Accepted Answer · 2018-02-16 19:56:38Z

0

Jelly, 21 bytes

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

Try it online!

Surely can be golfed

answered Feb 16 '18 at 19:56

HyperNeutrino♦

27.3k4 gold badges48 silver badges169 bronze badges

Add a comment |

user48543user48543 · Accepted Answer · 2018-02-16 20:04:30Z

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.

Mr. Xcoder · Accepted Answer · 2018-02-16 21:45:38Z

0

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.

answered Feb 16 '18 at 21:45

Mr. Xcoder

40.7k9 gold badges71 silver badges211 bronze badges

\$\begingroup\$ JS polyglot :-) \$\endgroup\$ – Arnauld Feb 18 '18 at 11:15

Add a comment |

Not a tree · Accepted Answer · 2018-02-17 02:52:54Z

0

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

answered Feb 17 '18 at 2:52

Not a tree

3,1461 gold badge8 silver badges23 bronze badges

Add a comment |

ovs · Accepted Answer · 2018-02-17 10:53:27Z

0

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!

answered Feb 17 '18 at 10:53

ovs

33.4k2 gold badges20 silver badges94 bronze badges

Add a comment |

Stack Exchange Network

current community

your communities

more stack exchange communities

Sum of combinations with repetition

17 Answers 17

Python 2, 46 45 bytes

Oasis, 9 bytes

Pyth, 9 bytes

Pyth, 16 bytes

How?

Jelly, 11 bytes

How it works

Perl, 38 bytes

C, 41 bytes

JavaScript (ES6), 32 bytes

Test cases

R, 56 49 47 bytes

MATL, 15 bytes

How it works

05AB1E, 10 bytes

Ruby, 41 bytes

Pari/GP, 36 bytes

Pari/GP, 37 bytes

Jelly, 21 bytes

Pyth, 12 bytes

Explanation

Proton, 32 bytes

Wolfram Language (Mathematica), 43 bytes

Haskell, 40 bytes

Your Answer

Not the answer you're looking for? Browse other questions tagged code-golf combinatorics integer-partitions or ask your own question.

Linked

Hot Network Questions

Sum of combinations with repetition

17 Answers 17

Python 2, 46 45 bytes

Oasis, 9 bytes

Pyth, 9 bytes

Pyth, 16 bytes

How?

Jelly, 11 bytes

How it works

Perl, 38 bytes

C, 41 bytes

JavaScript (ES6), 32 bytes

Test cases

R, 56 49 47 bytes

MATL, 15 bytes

How it works

05AB1E, 10 bytes

Ruby, 41 bytes

Pari/GP, 36 bytes

Pari/GP, 37 bytes

Jelly, 21 bytes

Pyth, 12 bytes

Explanation

Proton, 32 bytes

Wolfram Language (Mathematica), 43 bytes

Haskell, 40 bytes

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged code-golf combinatorics integer-partitions or ask your own question.

Linked

Related

Hot Network Questions