If you know the maximum integer you can receive, you can do a sort of bucket sort, where the Nth bit in the page represents whether you have revceived number N. So yo can store as many numbers as bits you have available.
http://en.wikipedia.org/wiki/Bloom_filter
I'm feeling a bit lazy to calculate the error rate right now.
4KB of RAM is not the same as an O(1) memory requirement, since we have already restricted the number and range of integers to 10000 (i.e. constants),so there is nothing left to vary. The page size just presents a target ratio for compression, not an asymptotic restriction on memory usage.
Or if you're expecting random data, invent a biased compression algorithm and use that (e.g. one that has shortcuts for storing any multiples of 3). Most of the time it will do nothing and a few times you'll randomly get data it's good at.
Actually on second thought I'm not sure if that works or not. You'll need a header to identify if the compression was used or not. So the compression has to save more on average than this header info costs.
This header problem becomes clearer if you try to chain thousands of special-case compression algorithms that map a single input to one bit and otherwise are unused. Seems to save space at first (at cost of CPU time, and space to store these algorithms), but actually identifying which are used or not will be a problem. Since they all need unique headers, you need just as many header possibilities as there are numbers in the range, so you must as well just use the numbers for the headers, at which case you're actually not doing anything since the header is the data.