outputting serializable sorted integers

I am wanting to generate a serialized list of randomly selected positive integers in sorted order, but the number of integers desired and the range of numbers that it may select from in a given use case could easily each be in the many millions (or sometimes even each in the range of billions, if 64 bit integers are being used), so it isn't really feasible to store the numbers that into an array that can then be accessed randomly by the software.

Therefore, I wanted to generate the numbers via a simple loop that looked something like this:

unsigned current = 0;
while(remaining>0) {
    if (find_next_to_output(current,max,remaining)) {
        // do stuff having output a value        
    }
}

Where remaining is initialized to however many random numbers I intend to output, and max is the upper bound (plus one) on the numbers that may be generated. It can be assumed that remaining will always be initialized to a number less than or equal to max.

The find_next_to_output function would look similar to this:

/**
 * advance through the range of accepted values until all values have been output
 * @param current [in/out] integer to examine.   Advances to the next integer
 *   to consider for output
 * @param max one more than the largest integer to ever output
 * @param remaining [in/out] number of integers left to output.  
 * @return true if the function ouputted an integer, false otherwise
 */
bool find_next_to_output(unsigned &current, unsigned max, unsigned &remaining)
{
    bool result = false;
    if (remaining == 0) {
        return false;
    } if (rnd() * (max - current) < remaining) {
        // code to output 'current' goes here.
        remaining--;
        result = true;
    } 
    int x = ?;  // WHAT GOES HERE?
    current += x;
    return result;
}

Note, the function rnd() used above would return a uniform randomly generated floating point number on the range [0..1).

As the comment highlights, I am unsure how I can calculate a reasonable value for x, such that the number of values of current that get skipped over by the function is reflective of the probability that none of the values that are skipped would be picked (while still leaving a sufficient number remaining that all remaining numbers can still be picked). I know that it needs to be a random number (probably not from a uniform distribution), but I don't know how to calculate a good value for it. At worst, it would simply increment current by one each time, but this should be statistically unlikely when there is a sufficient difference between the number of integers remaining to output and the number of integers remaining in the range.

I do not want to use any third party libraries such as boost, although I am fine with using any random number generators that may be packed in the standard library for C++11.

If any part of my question is unclear, please comment below and I will endeavor to clarify.