A396232 The smallest amount which cannot be made with fewer than n Indian coins.

1, 3, 8, 18, 38, 58, 78, 98, 118, 138, 158, 178, 198, 218, 238, 258, 278, 298, 318, 338, 358, 378, 398, 418, 438, 458, 478, 498, 518, 538, 558, 578, 598, 618, 638, 658, 678, 698, 718, 738, 758, 778, 798, 818, 838, 858, 878, 898, 918, 938, 958, 978, 998, 1018

Offset

1,2

Comments

a(n) is the smallest amount (in rupees) that cannot be made with fewer than n coins.

The coins included are those in common circulation in India: Rs. 1, Rs. 2, Rs. 5, Rs. 10 and Rs. 20.

Links

Paolo Xausa, Table of n, a(n) for n = 1..10000

Index entries for linear recurrences with constant coefficients, signature (2,-1).

Formula

From Alois P. Heinz, May 19 2026: (Start)

G.f.: x*(10*x^4+5*x^3+3*x^2+x+1)/(x-1)^2.

a(n) = 20*n - 62 for n>=4. (End)

E.g.f.: 62 + 43*x + 25*x^2/2+ 5*x^3/3 + exp(x)*(20*x - 62). - Stefano Spezia, Jun 18 2026

Example

For n = 3, 8 is the smallest number that requires 3 coins (1 + 2 + 5).

Mathematica

Join[{1, 3, 8}, 20*Range[4, 60] - 62] (* Paolo Xausa, Jun 18 2026 *)

Prog

(Python)
from math import inf
def indianCoins(up_to=2000, coins=(1, 2, 5, 10, 20)):
    coins_needed = [0] + [inf] * up_to
    for c in coins:
        for i in range(c, up_to + 1):
            coins_needed[i] = min(coins_needed[i], coins_needed[i - c] + 1)
    record = 0
    return [n for n, x in enumerate(coins_needed) if x > record and (record := x)]

Crossrefs

Cf. A258272, A258274.

Sequence in context: A000234 A136376 A099845 * A036635 A000713 A261325

Adjacent sequences: A396228 A396230 A396231 * A396233 A396234 A396235

Keyword

nonn,easy,changed

Author

Arjun Maneesh Agarwal, May 19 2026

Status

approved