Having seen the answers, my hint above is incorrect. You do need to generate these numbers, but the way to generate them is quite clever. Even with the right way, you need to ensure that your algorithm is efficient.

I feel like this my solution is a bit of a cheat. I had a pretty efficient algorithm for generating them but it wasn't fast enough, so I assumed that this was the way to solve it.

Ok. I get it. Generating green numbers is expensive - To do it in less than O(nlogn) would require a lot of effort (if it's even possible). However, given that n will always be <=3000, there might be a better way to do it.

How high does the Haskell solution check? I can get it to generate the 10000th number with my algorithm in about 12.5s but it always fails with a timeout on the server. I'm really struggling to see where I can get any more performance improvement.