You can do better than the greedy algorithm. With coins of value

>! {1, 5, 23, 62, 161, 311, 878, 946}

you can get *N* =

>! 3285.

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 the unique optimal solutions for up through six coins:

>! one coin: {1}, *N* = 1  
>! two coins: {1, 2}, *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