#include <iostream>
#include <vector>
using namespace std;
typedef unsigned long long int ulong;

//======================================================================
// This program generates a b-file for the lucky numbers (A000959)
// Run "lucky <elems>" to print elements 1 through <elems>
// It uses a "virtual sieve" and requires O(<elems>) space
// It runs as fast of faster than an explicit sieving algorithm
int main(int argc, char* argv[])
{
    // Obtain number of elements from command line
    unsigned elems = argc <= 1 ? 10000 : atoi(argv[1]);

	// Create a vector for our seive
	vector<ulong> lucky;
	lucky.resize(elems);

    // Set and print the first two elements explicitly
    // Indexing from 0 simplifies the computation
	if (elems >= 1)
	{
		lucky[0] = 1;
		cout << "1 1" << endl;
	}
	if (elems >= 2)
	{
	   lucky[1] = 3;
	   cout << "2 3" << endl;
	}

    // g is the largest index with lucky[g] <= n+1
    unsigned g = 0;

    // Compute the nth lucky number for 2 <= n <= elems
    for (unsigned n = 2; n < elems; n++)
	{
        // Update g to largest index with lucky[g] <= n+1
        if (lucky[g+1] <= n+1) g++;

        // Now we are going to trace the position k of the nth
        // lucky number backwards through the sieving process.
        // k is the nth lucky number, so it is at position n
        // after all the sieves.
        ulong k = n;

        // If lucky[i] > n+1, the sieve on lucky[i] does not alter
        // the position of the nth lucky number, that is, does not
        // alter k. So we need to run backwards through the sieves
        // for which lucky[i] <= n+1. The last such sieve is the
        // sieve for lucky[g], by definition of g.

        // So, we run backwards through the sieves for lucky[g]
        // down to the sieve for lucky[1] = 3.
        for (unsigned i = g; i >= 1; i--)
		{
            // Here k is the position of the nth lucky number
            // after the sieve on lucky[i]. Adjust the position
            // prior to the sieve on lucky[i].
            k = k*lucky[i]/(lucky[i]-1);
        }

        // Here k is the position of the nth lucky number prior to
        // sieve on 3, that is, after the sieve on 2. Adjust the
        // position prior to the sieve on 2.
        k = 2*k;

        // Here k is the position of the nth lucky number prior to
        // the sieve on 2, that is, within the natural numbers
        // (1, 2, 3, ...) indexed from 0. So the nth lucky number is
        lucky[n] = k+1;

        // Adjust n for 1-indexing and print our new value
        cout << n+1 << " " << lucky[n] << endl;
    }

    // And we are done
    return 0;
}