Number of ways to make an amount with coins

Question

This is not a duplicate of Sum of combinations with repetition. This question considers 1+2 to be the same as 2+1. The other question doesn't.

---

OEIS link - A000008

---

Background

If you have 4 types of coins (1, 2, 5 and 10 cents), in how many ways can you make an amount?

There are 4 ways of making 5 cents:

• 1 + 1 + 1 + 1 + 1
• 1 + 1 + 1 + 2
• 1 + 2 + 2
• 5

Note: 1 + 2 + 2 and 2 + 2 + 1 are considered to be the same in this challenge.

Your task

• Take an input. It will be a positive integer. This is the amount (in cents).
• Work out the number of ways to make that number from 1, 2, 5 and 10 cent coins.
• This is a sequence challenge, so any form of output is allowed.
• This is code-golf, so shortest answer in bytes wins.

Answer 1

JavaScript (ES6), 41 bytes

Saved 3 bytes thanks to @ovs

f=(n,k=10)=>n?k*n>0&&f(n,k>>1)+f(n-k,k):1

Try it online!

40 bytes

Suggested by @tsh

Returns true for \$f(0)\$.

f=(n,k=10)=>n>0?k&&f(n,k>>1)+f(n-k,k):!n

Try it online!

Commented

f = (              // f is a recursive function taking:
  n,               //   n = input
  k = 10           //   k = current coin value
) =>               //
n ?                // if n is not equal to 0:
  k * n > 0 &&     //   if k is not equal to 0 and n is positive:
    f(n, k >> 1) + //     do a recursive call where k is updated to the
                   //     next coin value
    f(n - k, k)    //     do a recursive call where k is subtracted from n
:                  // else:
  1                //   increment the number of solutions

Answer 2

Vyxal, 12 8 7 bytes

Ṅ₀$ḊvΠ∑

Try it Online! 6 bytes with s flag

Explained

Ṅ₀$ḊvΠ∑
Ṅ       # Integer partitions of the input
 ₀$Ḋ    # Does each item in each partition divide 10?
    vΠ  # Product of each partition
      ∑ # Sum that

Answer 3

HOPS, 20 bytes

mset(x+x^2+x^5+x^10)

Attempt This Online!

Answer 4

Wolfram Language (Mathematica), 36 bytes

Length[{1,2,5,10}~FrobeniusSolve~#]&

Try it online!

Answer 5

Regex 🐇 (RME / Perl / PCRE / Raku^:P5), 24 bytes

^x*(xx)*(x{5})*(x{10})*$

Takes its input in unary, as the length of a string of xs. 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! - PCRE
Try it online! - Raku

---

It's also possible to use Arnauld's algorithm, but only for inputs \$≥ 10\$ (because captures are the only kind of variable available, and can only be taken from the input). Even using lookinto, this is pretty long at 42 bytes (and would be longer using variable-length lookbehind):

^(?|(?^1=(x+)\1){0,3}\1|^(?=(x{10}))){2,}$

Try it on replit.com! - RegexMathEngine

^                      # tail = input number
(?|
    (?^1=(x+)\1)       # Assert \1 is set; \1 = floor(\1 / 2);
                       # assert the resulting \1 ≥ 1
                {0,3}  # Iterate the above 0 to 3 times
    \1                 # tail -= \1
|                  # or
    ^(?=(x{10}))       # If on the first iteration, \1 = 10. This can be
                       # matched multiple times in a row, as long as nothing
                       # has been subtracted from tail yet, but that would
                       # result in a non-match when exiting this loop.
){2,}                  # Iterate the above at least 2 times, with no maximum.
                       # This allows the first alternative to get a chance to
                       # match after the second alternative, which is zero-
                       # width, has matched.
$                      # Assert tail == 0

That can be made to work with all inputs by extending it to 49 bytes: ^(?|(?^1=(x+)\1){0,3}\1|^(?=((x{5}|x)\2?)|)){2,}$ - but this defeats the purpose of the 42 byte version in the first place, because if \$10\$ is not the only constant specified, you might as well go with the 24 byte version.

But it is possible to use this algorithm in its pure form (with no constants specified other than \$10\$ and \$\lfloor\log_2{10}\rfloor\$) in such a way that works for all inputs, by capturing \$10\$ in binary (89 bytes):

^(?|(?=(?=(\2))(?=(\3))(\4)()){0,3}(\1\2\2\3{4}\4{8})(?!.*$\5)|^(?=(?=()(x))()(x)|)){2,}$

Attempt This Online! - PCRE2 v10.40+
Try it on replit.com - RegexMathEngine in PCRE mode

^                   # tail = N = input number
(?|                 # Branch reset group - capture group numbering of each
                    # alternative starts at the same number, in this case \1.
    (?=
        # coinValue /= 2, where coinValue is defined as \1 + \2*2 + \3*4 + \4*8
        (?=(\2))    # \1 = \2
        (?=(\3))    # \2 = \3
        (\4)()      # \3 = \4; \4 = 0
    ){0,3}          # maximum number of iterations is floor(log(10) / log(2))
    (               # \5 = coinValue; tail -= \5
        \1
        \2\2
        \3{4}
        \4{8}
    )
    (?!.*$\5)       # Assert \5 != 0
|
    ^               # Only take this alternative on the first iteration (or, as
                    # explained below, also the 2nd iteration, if N==0)
    # coinValue = 10
    (?=             # Atomic lookahead
        # This can only match if tail ≥ 1
        (?=()(x))   # \1 = 0; \2 = 1
           ()(x)    # \3 = 0; \4 = 1
    |           # or...
        # Do nothing, if tail == 0; in this case, the 2nd iteration of the
        # outer loop will also end up taking this alternative, and there will
        # be exactly one way N==0 can result in a match.
    )
){2,}               # An enforced minimum of 2 iterations is necessary, because
                    # the first iteration always has zero width, and would cause
                    # the loop to end otherwise. (In Perl, not even this trick
                    # can force a loop to take more than one zero-width
                    # iteration.)
$                   # Assert that tail == 0

For compatibility with old versions of PCRE2, it is necessary to use a 93 byte version of this:
Try it online! - PCRE2 v10.33

Answer 6

Jelly, 7 bytes

Œṗḍ⁵ẠƇL

A monadic Link that accepts a positive integer and yields a positive integer.

Try it online!

How?

Œṗḍ⁵ẠƇL - Link: integer, Cents        e.g. 4
Œṗ      - integer partitions of Cents      [[1,1,1,1],[1,1,2],[1,3],[2,2],[4]]
   ⁵    - ten                              10
  ḍ     - divides? (vectorises)            [[1,1,1,1],[1,1,1],[1,0],[1,1],[0]]
     Ƈ  - keep those for which:
    Ạ   -   all?                           [[1,1,1,1],[1,1,1],      [1,1]    ]
      L - length                           3

Answer 7

Python, ^{111 106} 65 bytes

f=lambda s,n=4:s==0 or s>=0<n and f(s,n-1)+f(s-(1,2,5,10)[n-1],n)

Try it online!

-5 thanks to Jo King -41 thanks to Kevin Cruijssen

Answer 8

Python 2, 49 bytes

f=lambda n,k=10:k*n>0and f(n-k,k)+f(n,k/2)or n==0

Try it online!

Conveniently, we can iterate through the count value by starting at 10 and floor-dividing by 2 to get 10->5->2->1 and terminating at 0.

Answer 9

Charcoal, 26 bytes

Ｎθ⊞υ⁰Ｆ9410ＦυＦ‹κθ⊞υ⁺κ⊕ιＩ№υθ

Try it online! Link is to verbose version of code. Explanation:

Ｎθ

Input n.

⊞υ⁰

Start with 0 as a possible amount.

Ｆ9410

Loop over the digits 9, 4, 1, and 0, which will later be incremented to represent the coins 10, 5, 2 and 1.

Ｆυ

Loop over each possible amount discovered so far.

Ｆ‹κθ

If this amount is less than n, then...

⊞υ⁺κ⊕ι

... add the current coin to the amount, and record this as a new possible amount. This then allows it to be considered again as a possible amount for the current coin, until the value reaches or exceeds n.

Ｉ№υθ

Count the number of times n was reached.

Example for n=5:

• Start with 0 as an amount.
• Add 10 to that, resulting in a new amount of 10. This amount is now more than 5, so it is ignored.
• Add 5 to the 0 amount, resulting in a new amount of 5. This amount is also ignored for now.
• Add 2 to the 0 amount, resulting in a new amount of 2.
• Add 2 to the 2 amount, resulting in a new amount of 4.
• Add 2 to the 4 amount, resulting in a new amount of 6. This amount is now more than 5, so it is ignored.
• Add 1 to the 0, 2 and 4 amounts, resulting in new amounts of 1, 3 and 5. The 5 amount is ignored for now.
• Add 1 to the 1 and 3 amounts, resulting in new amounts of 2 and 4.
• Add 1 to the 2 and 4 amounts, resulting in new amounts of 3 and 5.
• Add 1 to the 3 amount, resulting in a new amount of 4.
• Add 1 to the 4 amount, resulting in a new amount of 5.
• There are no more coins, so the final count of 5s is 4 as desired.
• The 4 5s correspond to the sums 5, 2+2+1, 2+1+1+1 and 1+1+1+1+1 respectively.

The coins are considered in descending order for efficiency but the algorithm would work with the coins in any order.

Answer 10

05AB1E, 13 10 bytes

ÅœʒTÑsåP}g

Try it online.

A modification of Mr.Xcoder's 05AB1E answer in the related challenge would be 1 byte longer (and way slower):

TÑIиæ€{ÙOI¢

Try it online. (Too slow for TIO for \$n\ge4\$.)

Explanation:

Ŝ           # Get all lists of positive integers that sum to the (implicit) input
  ʒ          # Filter this list of lists by:
             #  (implicitly push the current list)
   TÑ        #  Push the divisors of 10: [1,2,5,10]
     s       #  Swap so the current list is at the top of the stack
      å      #  Check for each value whether it's in list [1,2,5,10]
       P     #  Check if it's truthy for all of them by taking the product
  }g         # After the filter: pop and push the length
             # (which is output implicitly as result)

TÑ           # Push list [1,2,5,10]
  Iи         # Repeat it the input amount of times: [1,2,5,10,1,2,5,10,...]
    æ        # Get the powerset of this list
     €{      # Sort each inner list
       Ù     # Uniquify the list of lists
        O    # Sum each inner list
         I¢  # Count how many times the input occurs in the list
             # (which is output implicitly as result)

Answer 11

Ruby, 46 bytes

f=->n,k=10{n<0||k<1?0:n<1?1:f[n-k,k]+f[n,k/2]}

Try it online!

Shamelessly inspired by Arnauld's Javascript answer.

Answer 12

Desmos, 76 bytes

f(n)=1+∑_{k=1}^{n^4}0^{(n-∑_{j=1}^4[1,2,5,10][j]mod(floor(nk/n^j),n))^2}

Inspired by @fireflame's Desmos answer to How many partitions do I have?

Try It On Desmos!

Try It On Desmos! - Prettified

Answer 13

Prolog (SWI), 66 bytes

N+K+M:-K*N>0,N-K+K+Q,N+K//2+W,M is Q+W;N=:=0,M=1;M=0.
N+M:-N+10+M.

Try it online!

Port of xnor's Python answer.

Answer 14

Scala, 131 bytes

Golfed version. Try it online!

def f(n:Int,p:Seq[Int]=Seq(1,2,5,10)):Int=(n,p)match{case(0,_)=>1;case(_,Nil)=>0;case(_,k::ks)=>if(n<k)0 else f(n-k,k::ks)+f(n,ks)}

Ungolfed version. Try it online!

object Main {
  def a000008(n: Int): Int = {
    val coins = List(1, 2, 5, 10)

    def p(ks: List[Int], m: Int): Int = (ks, m) match {
      case (_, 0)         => 1
      case (Nil, _)       => 0
      case (k :: ksTail, _) if m < k => 0
      case (ksHead :: ksTail, _)     => p(ksHead :: ksTail, m - ksHead) + p(ksTail, m)
    }

    p(coins, n)
  }

  def main(args: Array[String]): Unit = {
    for (n <- 1 to 20) {
      println(s"p($n) = ${a000008(n)}")
    }
  }
}