I really like PI's idea, but 500 seems better. So, (I think) it would work like this:
0-100 = 1d4
101-200 = 2d4
501-600 = 1d6
601-700 = 2d6
1001-1100 = 1d8
1101-1200 = 2d8
1501-1600 = 1d10
etc...
Up to 2501, where you would get your first d20, capping out at 3000 with the 5d20.
At least, that's the way I understood it (with a minor edit)