You can do better than the greedy algorithm. With coins of value
{1, 6, 20, 75, 175, 474, 756, 785}
you can get N =
3356.
I wrote a search program for this but it isn’t going to finish searching the entire space in reasonable time, so I don’t know whether that’s optimal. Here are all the optimal solutions for up through seven coins:
one coin: {1}, N = 1
two coins: {1, 2} or {1, 3}, N = 4
three coins: {1, 4, 5}, N = 15
four coins: {1, 3, 11, 18}, N = 44
five coins: {1, 4, 9, 31, 51}, N = 126
six coins: {1, 7, 11, 48, 83, 115}, N = 388
seven coins: {1, 7, 18, 62, 104, 244, 259} or {1, 8, 13, 66, 115, 254, 415}, N = 1137
