Sums payable by exactly n banknotes.

[Joshua Zucker]

On Feb 16, 2008 7:59 AM, zak seidov <zakseidov at yahoo.com> wrote:
> Dear Neil, seqfans,
>
> 1) can anyone check/extend these figures?

Sure, see below.

> 2) what about case n => inf?

It sure seems to me like, when n is large, the sequence should
approach 99n (because you can make almost everything from n through
100n).  But I guess it's 99n - a few, because there'll be a few
numbers near n and near 100n that are unmakeable.  Hm, are there
enough unmakeable ones that the limit of a(n)/n is less than 99?  Yes,
because for instance between n and 5n you can only make things by
adding a multiple of 4, right?  No, because you can also add multiples
of 9 instead.  OK, I'm fairly convinced now that it's ~ 99n.

> 3) is this worth submitting?

My general feeling is "if you have to ask, the answer is probably no".

But of course only Neil's opinion really counts here.

--Joshua Zucker

> %N A1 Number of sums payable by exactly n banknotes of
> nominals 1,5,10,20,50,100.

"nominals"?  I think we would say "denominations".

> %S A1 6, 15, 52, 103, 174, 262, 360, 461, 561, 660.

6 21 52 103 174 262 360 461 561 660 759 858 957 1056 1155 1254 1353
1452 1551 1650 1749 1848 1947 2046 2145 2244 2343 2442 2541 2640 2739
2838 2937 3036 3135 3234 3333 3432 3531 3630 3729 3828 3927 4026 4125
4224 4323 4422 4521 4620 4719 4818 4917 5016 5115 5214 5313 5412 5511
5610 5709 5808 5907 6006 6105 6204 6303 6402 6501 6600 6699 6798 6897
6996 7095 7194 7293 7392 7491 7590 7689 7788 7887 7986 8085 8184 8283
8382 8481 8580 8679 8778 8877 8976 9075 9174 9273 9372 9471

Note the correction to the second term, 6 choose 2 = 21.

--Joshua Zucker