#include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX 100000000LL long long *prod = 0; // [MAX]; #define WANTED 100000000LL long long *a = 0; // [WANTED]; // first index long long *b = 0; // [WANTED]; // last index int u = 1; int r = 0; int mx = -1; int main() { prod = (long long*)malloc(MAX*sizeof(*prod)); a = (long long*)malloc(MAX*sizeof(*a)); b = (long long*)malloc(MAX*sizeof(*b)); memset(prod, 0, sizeof(prod)); memset(a, 0, sizeof(a)); memset(b, 0, sizeof(b)); int v = 1; int k = 0; int m = 0; long long p = -1; long long pp = -1; for (long long n=1; n<=1000000000000000000ll; n++) { for (int o=1;; o++) { int ov = o*v; if (ov>=MAX) { fprintf(stderr, "#the end\n"); return 1; } int old = prod[ov]; if (old+1<=ov) { if (!old && ov<WANTED) { a[ov]=n; } v=o; if (pp==ov) { // giant step - the sequence is 2-periodic for a while if ((ov-old)%2==0) { v = ov/o; } prod[ov] = ov; n += ov-old-1; } else { prod[ov] = old+1; pp = ov; } if (prod[ov]==ov && ov<WANTED) { b[ov] = n; while (b[u]) { int w = b[u]-a[u]+1; if (mx<w) { mx=w; printf ("%d %lld\n", ++r, u); fflush(stdout); } if (++u==WANTED) { return 0; } } } break; } } } return 0; }