A258272 - OEIS

%I #31 Jul 24 2022 02:32:42

%S 1,3,8,18,38,88,188,388,588,788,988,1188,1388,1588,1788,1988,2188,

%T 2388,2588,2788,2988,3188,3388,3588,3788,3988,4188,4388,4588,4788,

%U 4988,5188,5388,5588,5788,5988,6188,6388,6588,6788,6988,7188,7388,7588,7788,7988,8188

%N The smallest amount which cannot be made with fewer than n British coins.

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

%C The coins included are those in common circulation in the UK: 1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).

%H Matthew Scroggs, <a href="/A258272/b258272.txt">Table of n, a(n) for n = 1..5005</a>

%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (2,-1).

%F From _Georg Fischer_, Jul 22 2022: (Start)

%F a(n) = 200*n - 1222 for n >= 7.

%F O.g.f.: (1 + x + 3*x^2 + 5*x^3 + 10*x^4 + 30*x^5 + 50*x^6 + 100*x^7)/(x - 1)^2. (End)

%e The smallest value that requires 4 coins is 18p (10p, 5p, 2p and 1p). Therefore a(4)=18.

%t CoefficientList[Series[(1 + x + 3*x^2 + 5*x^3 + 10*x^4 + 30*x^5 + 50*x^6 + 100*x^7)/(x - 1)^2, {x,0,64}], x] (* _Georg Fischer_, Jul 22 2022 *)

%o (Python) #

%o coins = [1,2,5,10,20,50,100,200]

%o need = [0]

%o while True:

%o ....next = len(need)

%o ....n_need = next

%o ....for coin in coins:

%o ........if coin>next:

%o ............break

%o ........n_need = min(n_need,1+need[next-coin])

%o ....need.append(n_need)

%o ....if n_need == len(seq):

%o ........print(next)

%o (PARI) Vec((1 + x + 3*x^2 + 5*x^3 + 10*x^4 + 30*x^5 + 50*x^6 + 100*x^7)/(x - 1)^2 + O(x^50)) \\ _Felix Fröhlich_, Jul 23 2022

%Y Cf. A258274.

%K nonn

%O 1,2

%A _Matthew Scroggs_, May 25 2015

%E More terms from _Felix Fröhlich_, Jul 23 2022