I would have thought it (in general) impossible to store more than 2^15/log2(10000)~2500 integers between 1 and 10000 in 4kB, but I look forward to hearing more.
Yeah, I was thinking about that, too. Something theoretically screams 'No' to me. You have 2^15 bits of storage available, and each number takes log2(10,000) bits, I can't see storing more than the one divided by the other, if each number is equally likely and random.
But! Since we have flexibility in the order in which the integers are stored in the array, could we store a couple "meta integers"? e.g. Could we put our 2,500 integers in the array in such a way that the bits in log2(10,000) locations spell out a 2,501st integer between 1 and 10,000?
I feel like it can't always work: maybe our 2500 integers are just such that there's no way to put them in to spell out the meta integer. OTOH, that's just one scheme I thought of, and perhaps there is a way I'm not thinking of that we can leverage the order in which we put the integers in the array. There might be some free "information" that way that is not being counted by the simple number of bits of storage.
Another thought: Maybe the default ordering of the integers is ascending, and we can break that known ordering in certain places to convey information about the 2501 integer. But then -- what if all the integers given are the same? Sigh.
Yeah, I was thinking about that, too. Something theoretically screams 'No' to me. You have 2^15 bits of storage available, and each number takes log2(10,000) bits, I can't see storing more than the one divided by the other, if each number is equally likely and random.
But! Since we have flexibility in the order in which the integers are stored in the array, could we store a couple "meta integers"? e.g. Could we put our 2,500 integers in the array in such a way that the bits in log2(10,000) locations spell out a 2,501st integer between 1 and 10,000?
I feel like it can't always work: maybe our 2500 integers are just such that there's no way to put them in to spell out the meta integer. OTOH, that's just one scheme I thought of, and perhaps there is a way I'm not thinking of that we can leverage the order in which we put the integers in the array. There might be some free "information" that way that is not being counted by the simple number of bits of storage.
Another thought: Maybe the default ordering of the integers is ascending, and we can break that known ordering in certain places to convey information about the 2501 integer. But then -- what if all the integers given are the same? Sigh.