/*

Computing terms of http://oeis.org/A262896 
Antti Karttunen modified this from a similar program by Max Alekseyev which computed terms of A259934/A259935.

A259934 Infinite sequence starting with a(0)=0 such that A049820(a(k)) = a(k-1) for all k>=1. 
A259935 Infinite sequence of positive integers such that a(n) = A000005(a(1)+a(2)+...+a(n)) for all n>=1. 

A262896 If n is in A262892, a(n) = A259934(n), otherwise the largest term in A045765 from which one can
 reach A259934(n) by iterating A049820, without visiting any other (larger) term of A259934. 

Should begin as (offset 0): 8, 2, 79, 12, 18, 40, 30, 140, 42, 52, 54, 66, 68, 123, 98, 90, 94, 116, ...

Most of code is from the original source by Max Alekseyev, I just added the array nodes and some
additional code manipulating it (added into decr_and_update_nodes). I also changed the output part
a little, so that it creates a standard b-file for OEIS.
Also, I tried to find safe limits and cut-points for this particular sequence, via auxiliary sequences
https://oeis.org/A262508 and A263081.

 - AK, October 12, 2015.

*/

#include <iostream>
#include <cstdint>

using namespace std;


// #define BOUND1 124340 // = A263081(1..38), or, for larger values:
#define BOUND1 24684000 // = A263081(39..68).

#define BOUND_WITH_MARGIN_FOR_TAU BOUND1 + 8192 // = + A002183(101), should be enough as A002182(101) = 3212537328000.

// #define OUTPUT_INDEX_BOUND 9786 // = A262508(37).
#define OUTPUT_INDEX_BOUND 1310010 // = A262508(67).

// Note that A262510(37) = 123257 and 24678461 = A262509(67) = A262510(68).


typedef int16_t mycount_t;

mycount_t *tau, *count;
long *nodes; // Added by AK.

void decr_and_update_nodes(mycount_t* count,long n,long t,long *nodes)
{
    long mc = n;
loop:
    if(mc > nodes[t]) { nodes[t] = mc; } // Maintain the info about the largest leaf-node of node t.

    if( --count[t] == 0 )
     {
       long k = t - tau[t];
       if( k>0 )
        {
          n = t;
          t = k;
          goto loop; // Hand-optimized tail-recursion. (AK)
        }
       else { if(mc > nodes[k]) nodes[k] = mc; } // Just for updating nodes[0].
     }
}


int main()
{

    tau = new mycount_t[BOUND_WITH_MARGIN_FOR_TAU+1]();
    count = new mycount_t[BOUND1+1]();
    nodes = new long[BOUND1+1]();

    // compute tau values
    // Same as https://oeis.org/A000005
    clog << "Cooking tau... "; clog.flush();
    for(long d=1;d<=BOUND_WITH_MARGIN_FOR_TAU;++d)
     {
       for(long i=d;i<=BOUND_WITH_MARGIN_FOR_TAU;i+=d) tau[i]++;
     }
    clog << "done. tau(1)=" << tau[1] << " tau(2)=" << tau[2] << " tau(3)=" << tau[3] << endl; clog.flush();


    // Initially same as https://oeis.org/A060990 Number of solutions to x - d(x) = n.
    clog << "Compute counts... "; clog.flush();
    for(long n=1;n<=BOUND_WITH_MARGIN_FOR_TAU;++n)
     {
       long k = n - tau[n];
       if( k<=BOUND1 ) count[k]++;
     }
    clog << "done. count(0)=" << count[0] << " count[1]=" << count[1] << " count(2)=" << count[2] << " count(3)=" << count[3] << endl;
    clog.flush();

    clog << "Decrease counts and update max-leaf information "; clog.flush();
    for(long n=0;n<=BOUND1;++n)
     {
       // If count for n is initially zero, then it is one of the leaves, https://oeis.org/A045765
       // (decr_and_update_nodes marks zeros also to other nodes):
       if(0 == count[n]) decr_and_update_nodes(count,n,n-tau[n],nodes);
     }
    clog << "done." << endl; clog.flush();

     {
       cout << "0 " << nodes[0] << endl;
       long p = 0;
       long i = 1;
       for(long n=2;i<=OUTPUT_INDEX_BOUND;++n)
        {
          if(!count[n]) continue;
          if( p != n-tau[n] ) break;
          cout << i << " " << (nodes[n] ? nodes[n] : n) << endl;
          i++;
          p = n;

        }
     }


    delete[] tau;
    delete[] count;
    delete[] nodes;

    return 0;
}