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, Commented Feb 16, 2018 at 17:23
Can someone reword this into a challenge? Because this would be a fun one. — Magic Octopus Urn, Commented Feb 16, 2018 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, Commented Feb 16, 2018 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, Commented Feb 16, 2018 at 19:38

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

10

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, 2018 at 20:31

answered Feb 16, 2018 at 19:51

ovs

60.6k3 gold badges47 silver badges161 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
Commented Feb 16, 2018 at 20:13
\$\begingroup\$ @xnor thanks a lot. I just tried it the other way round \$\endgroup\$
– ovs
Commented Feb 16, 2018 at 20:33

Add a comment |

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

7

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, 2018 at 21:57

answered Feb 16, 2018 at 21:50

Emigna

53k5 gold badges43 silver badges162 bronze badges

Add a comment |

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

3

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.

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Feb 16, 2018 at 19:52

Mr. Xcoder

42.5k9 gold badges81 silver badges214 bronze badges

Add a comment |

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

3

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

edited Feb 16, 2018 at 21:36

answered Feb 16, 2018 at 20:02

Ton Hospel

14.9k1 gold badge22 silver badges45 bronze badges

\$\begingroup\$ I only just now learned that you did this 3 years before my Fibonacci answer. I wonder why you didn't apply this to Fibonacci? Anyway, I've been now extending the idea much further, answering various challenges with regex 🐇-output (output by number of possible matches), and added it as a built-in to RegexMathEngine. \$\endgroup\$
– Deadcode
Commented Aug 5, 2022 at 17:54
\$\begingroup\$ Also, you can do this in 3 fewer bytes, as done in my Fibonacci answer but without -p. And obligatory note: With the $\ and }{ trick you're doing, the program will still try to loop, but it won't reset the value of $\, so it only works properly when given one number followed by EOF. \$\endgroup\$
– Deadcode
Commented Aug 5, 2022 at 18:47

Add a comment |

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, 2018 at 6:19

answered Feb 16, 2018 at 20:00

Mr. Xcoder

42.5k9 gold badges81 silver badges214 bronze badges

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

Add a comment |

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

2

05AB1E, 10 bytes

30fIиæÙOI¢

Try it online!

answered Feb 16, 2018 at 21:42

Mr. Xcoder

42.5k9 gold badges81 silver badges214 bronze badges

Add a comment |

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, 2018 at 0:16

Steadybox

16.5k5 gold badges41 silver badges84 bronze badges

answered Feb 16, 2018 at 23:50

0xrgb

1078 bronze badges

Add a comment |

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

2

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, 2018 at 2:52

Not a tree

3,2061 gold badge12 silver badges23 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, 2018 at 15:31

answered Feb 16, 2018 at 19:48

Arnauld

198k20 gold badges179 silver badges650 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, 2018 at 20:41

answered Feb 17, 2018 at 2:46

rturnbull

3,94916 silver badges27 bronze badges

1

\$\begingroup\$ 48 bytes \$\endgroup\$
– Giuseppe
Commented Feb 19, 2018 at 16:46
\$\begingroup\$ @Giuseppe Very nice improvement! \$\endgroup\$
– rturnbull
Commented Feb 20, 2018 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
Commented Feb 20, 2018 at 17:37

Add a comment |

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

1

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

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Feb 16, 2018 at 19:56

Luis Mendo

105k9 gold badges135 silver badges372 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, 2018 at 23:40

answered Feb 17, 2018 at 7:24

MegaTom

4,2861 gold badge21 silver badges24 bronze badges

Add a comment |

alephalpha · Accepted Answer · 2021-12-14 11:34:44Z

1

Pari/GP, 32 bytes

n->1/(1-x^2-x^3-x^5)%x^(n+1)\x^n

Try it online!

edited Dec 14, 2021 at 11:34

answered Feb 17, 2018 at 2:36

alephalpha

50k7 gold badges68 silver badges182 bronze badges

Add a comment |

naffetS · Accepted Answer · 2022-08-05 17:41:51Z

Vyxal, 9 bytes

⁺¤fẋfṗUṠO

Try it Online!

The header in the link halves the input to make things faster. It will return the same result if you remove it, but it may time out.

⁺¤f could alternatively be 30ǐ (prime factors of 30) or 5~æ (prime numbers up to 5).

⁺¤fẋfṗUṠO
⁺¤f       # Push the digits of 235: [2, 3, 5]
   ẋf     # Repeat the list the input times
     ṗ    # Powerset
      U   # Uniquify
       Ṡ  # Sum each
        O # Count the number of times the input appears in this array

Deadcode · Accepted Answer · 2022-08-05 18:43:05Z

Regex `🐇` (ECMAScript^{^RME} / Perl / PCRE / Raku^{^:P5}), 14 bytes

^(xxx?|x{5})*$

Takes its input in unary, as a string of x characters whose length represents the number. Returns its output as the number of ways the regex can match. (The rabbit emoji indicates this output method.)

Try it on replit.com (RegexMathEngine)
Try it online! - Perl
Try it online! - PCRE1
Try it online! - PCRE2
Try it online! - Raku

Same method as used for Fibonacci function or sequence, directly enumerating the ordered partitions.

^          # tail = input number
(
    xxx?   # tail-=2 or tail-=3
|          # or
    x{5}   # tail-=5
)*         # Loop the above as many times as possible, minimum zero
$          # Assert tail == 0

Regex `🐇` (Raku), 14 bytes

^(xxx?|x**5)*$

Try it online!

Raku's plain regex alternation operator is ||, and | does something special – it chooses the alternative making the longest match. But it'll still try every alternative when backtracking, so this makes no difference in the number of matches.

Perl, 38 bytes _{^{(full program)}}

1x<>~~/^(...?|.{5})*$(??{++$i})/;say$i

Try it online!

Interestingly, I noticed after making this post that Ton Hospel already used the same basic method (and it predates my Perl Fibonacci answer by 3 years), but did it with Perl -p in 37 bytes (which can be reduced to 34 bytes), by exploiting Perl actually using literal { } to create the -p loop. I previously assumed Perl emulated a loop when launched with -p, not that it literally string-concatenated the program into a loop.

Using the $\ trick (setting the print record separator), there's an alternative 38 byte flagless full program:

1x<>~~/^(...?|.{5})*$(??{++$\})/;print

Try it online!

Sadly it's only literally a print record separator and doesn't apply to say.

Raku, 27 bytes^{^SBCS} _{^{(anonymous function)}}

{+m:ex/^(...?|.**5)*$/}o¹x*

Try it online!

Aiden Chow · Accepted Answer · 2022-09-05 23:12:44Z

1

Desmos, 101 bytes

l=mod(floor(nk/n^{[1,2,3]}),n)
f(n)=∑_{k=1}^{n^3}0^{(n-total([2,3,5]l))^2}l.total!/∏_{a=1}^3l![a]

Ugh, no recursion sucks. I literally see all these answers going f(n-2)+f(n-3)+f(n-5), like super golfy, but nope, can't do that in Desmos.

Try It On Desmos!

Try It On Desmos! - Prettified

answered Sep 5, 2022 at 23:12

Aiden Chow

14.2k1 gold badge17 silver badges55 bronze badges

Add a comment |

naffetS · Accepted Answer · 2022-09-05 23:28:48Z

1

Prolog (SWI), 50 bytes

N+O:-N>0,N-2+A,N-3+B,N-5+C,O is A+B+C;N<0,O=0;O=1.

Try it online!

answered Sep 5, 2022 at 23:28

naffetS

12.8k2 gold badges20 silver badges53 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, 2018 at 19:56

hyperneutrino♦

42.6k5 gold badges68 silver badges224 bronze badges

Add a comment |

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

0

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.

answered Feb 16, 2018 at 20:04

user48543

Add a comment |

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, 2018 at 21:45

Mr. Xcoder

42.5k9 gold badges81 silver badges214 bronze badges

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

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, 2018 at 10:53

ovs

60.6k3 gold badges47 silver badges161 bronze badges

Add a comment |

Kevin Cruijssen · Accepted Answer · 2022-09-05 11:06:53Z

05AB1E, 8 bytes

1λèƵ†S₆O

Port of @ovs' Python 2 answer.

Try it online or verify all test cases.

Outputting the infinite sequence would be 6 bytes instead:

λƵ†S₆O

Try it online.

Explanation:

 λ        # Start a recursive environment
  è       # to output the (implicit) input'th value
          # (which is output implicitly in the end)
1         # Starting with a(0)=1, and a(-1)=a(-2)=a(-3)=a(-4)=0
          # And where every next a(n) is calculated as:
   Ƶ†     #  Push compressed integer 235
     S    #  Convert it to a list of digits: [2,3,5]
      ₆   #  Calculate a(n-v) for each value v in this list: [a(n-2),a(n-3),a(n-5)]
       O  #  Sum this list together: a(n-2)+a(n-3)+a(n-5)

λ         # Start a recursive environment
          # to output the infinite sequence
          # (which is output implicitly in the end)
          # (implicitly starting with a(0)=1, and a(-1)=a(-2)=a(-3)=a(-4)=0)
          # And where every next a(n) is calculated as:
 Ƶ†S₆O    #  Same as above

See this 05AB1E tip of mine (section How to compress large integers?) to understand why Ƶ† is 235.

Stack Exchange Network

Sum of combinations with repetition

22 Answers 22

Python 2, 46 45 bytes

Oasis, 9 bytes

Pyth, 9 bytes

Pyth, 16 bytes

How?

Perl, 38 bytes

Jelly, 11 bytes

How it works

05AB1E, 10 bytes

C, 41 bytes

Wolfram Language (Mathematica), 43 bytes

JavaScript (ES6), 32 bytes

Test cases

R, 56 49 47 bytes

MATL, 15 bytes

How it works

Ruby, 41 bytes

Pari/GP, 32 bytes

Vyxal, 9 bytes

Regex `🐇` (ECMAScript^{^RME} / Perl / PCRE / Raku^{^:P5}), 14 bytes

Regex `🐇` (Raku), 14 bytes

Perl, 38 bytes _{^{(full program)}}

Raku, 27 bytes^{^SBCS} _{^{(anonymous function)}}

Desmos, 101 bytes

Prolog (SWI), 50 bytes

Jelly, 21 bytes

Pyth, 12 bytes

Explanation

Proton, 32 bytes

Haskell, 40 bytes

05AB1E, 8 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

22 Answers 22

Python 2, 46 45 bytes

Oasis, 9 bytes

Pyth, 9 bytes

Pyth, 16 bytes

How?

Perl, 38 bytes

Jelly, 11 bytes

How it works

05AB1E, 10 bytes

C, 41 bytes

Wolfram Language (Mathematica), 43 bytes

JavaScript (ES6), 32 bytes

Test cases

R, 56 49 47 bytes

MATL, 15 bytes

How it works

Ruby, 41 bytes

Pari/GP, 32 bytes

Vyxal, 9 bytes

Regex 🐇 (ECMAScriptRME / Perl / PCRE / Raku:P5), 14 bytes

Regex 🐇 (Raku), 14 bytes

Perl, 38 bytes (full program)

Raku, 27 bytesSBCS (anonymous function)

Desmos, 101 bytes

Prolog (SWI), 50 bytes

Jelly, 21 bytes

Pyth, 12 bytes

Explanation

Proton, 32 bytes

Haskell, 40 bytes

05AB1E, 8 bytes

Your Answer

Sign up or log in

Post as a guest

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

Linked

Related

Hot Network Questions

Regex `🐇` (ECMAScript^{^RME} / Perl / PCRE / Raku^{^:P5}), 14 bytes

Regex `🐇` (Raku), 14 bytes

Perl, 38 bytes _{^{(full program)}}

Raku, 27 bytes^{^SBCS} _{^{(anonymous function)}}

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