A366013 -id:A366013 - cp's OEIS frontend

A364607 Denominations of a 4-coin system that returns the fewest coins in change on average.

1, 5, 18, 25

Offset: 1

Thomas Young, Aug 06 2023

In 1995, Thomas Young, along with students Jeff Greenfield, Joe Culbert, and David Raabe, explored the idea of the best 4-coin system for making change for a dollar. They assumed that each value for change (from 1 cent to 99 cents) was equally likely and, using an original Turbo Pascal program, calculated the average number of coins returned for every possible set of 4 coin denominations. Their result was announced via the essay, "Change the Dime not the Dollar."

The average number of coins required to return 1..99 cents is A339333(99,4)/99 = 389/99. - Pontus von Brömssen, Aug 13 2023

Thomas Young, A Turbo Pascal program to find the optimal coin system.
Thomas Young, Change the Dime Not the Dollar.

Cf. A208953, A339333, A366013.

A366360 Irregular triangle read by rows where each row is coin denominations which make amounts 1 to 99 using the smallest total number of coins by the greedy algorithm.

Original entry on oeis.org

1, 1, 10, 1, 11, 1, 5, 22, 1, 5, 23, 1, 3, 11, 37, 1, 3, 11, 38, 1, 3, 7, 16, 40, 1, 3, 7, 16, 41, 1, 3, 7, 18, 44, 1, 3, 7, 18, 45, 1, 3, 8, 20, 44, 1, 3, 8, 20, 45, 1, 2, 5, 11, 25, 62, 1, 2, 5, 11, 25, 63, 1, 2, 5, 13, 29, 64, 1, 2, 5, 13, 29, 65, 1, 2, 5, 8, 17, 27, 63

Offset: 1

Kevin Ryde, Oct 10 2023

The greedy algorithm makes a given amount by as many as possible of the largest coin, then as many as possible of the second largest towards the remainder, and so on.
A row of length d makes amounts 1 to 99 using total A339334(99,d) coins which is the minimum possible for d denominations by the greedy algorithm.
Denominations within a row are in ascending order and rows are ordered by length and then lexicographically.
Each row starts with denomination 1 since 1 is the only way to make amount 1.
This is a finite sequence, ending with a row of all denominations 1 to 99 which makes every amount with a single coin each.
Amounts 1 to 99 are based on making change in a decimal currency with coins for 1 to 99 cents, and with the greedy algorithm being an easy way to make amounts by successively taking the largest possible coin.
Minimizing the total coins minimizes the average number of coins given as change assuming each of 1 to 99 are equally likely.

			Triangle begins:
      k=1   2   3   4   5
  n=1:  1
  n=2:  1, 10
  n=3:  1, 11
  n=4:  1,  5, 22
  n=5:  1,  5, 23
  n=6:  1,  3, 11, 37
  n=7:  1,  3, 11, 38
  n=8:  1,  3,  7, 16, 40
Rows n=6 and n=7 have length d=4 and are the two sets of denominations which, with the greedy algorithm, make amounts 1 to 99 using the minimum total A339334(99,4) = 410 coins.

Kevin Ryde, Table of n, a(n) for rows 1..1000 (row lengths d=1..10 and some of d=11), flattened
Kevin Ryde, C Code
Jeffrey Shallit, What This Country Needs is an 18¢ Piece, The Mathematical Intelligencer, 25-2, pages 20-23, 2003, figure 2 rows to d=7, and also author's copy, 2002.

Cf. A339334.

Cf. A366013 (amounts any way).

C
```
/* See links */
```

cp's OEIS Frontend

A364607 Denominations of a 4-coin system that returns the fewest coins in change on average.

Views

Author

Keywords

Comments

Links

Crossrefs