1705 investigation

gistfile1.c

#include <stdio.h>
#include <math.h>

typedef unsigned long long int val_t;

val_t naive_calc(val_t n, val_t min) {
	val_t k;
	for (k = min; k < n; k++)
		if (n / k  == n / (k + 1))
			return k;
	return -1;
}

int my_log2(val_t n) {
	int res = 0;
	while (n >>= 1)
		res++;
	return res;
}

int main() {
	val_t n;
	val_t max = 0;
	int x = 0;
	int min_inc = 0;
	int last_inc = 0;
	for (n = 1; n < 1000000; n++) {
		val_t min = sqrt(n) + 1;
		val_t k = naive_calc(n, min);
		if (k == -1)
			continue;
		if (k > max) {
			max = k;
//			printf("max = %llu starting from %llu (%llu*%llu %llu)\n", max, n, min, min-1, min*(min-1));
			if (!min_inc) {
				int s = sqrt(n);
				printf("max increase without min increase on %d [%llu] (+%d)\n", s, n, s - last_inc);
				last_inc = s;
			}
			min_inc = 0;
		}
		if (n == (min-1) * (min-1)) {
			if (min_inc)
				printf("min increase without max increase on %llu\n", n);
			min_inc = 0;
			min_inc = 1;
//			printf("min = %llu starting from %llu (%llu*%llu %llu)\n", min, n, min-1, min-1, (min-1)*(min-1));
		}

		if (k < min) {
			printf("ERROR on %llu\n", n);
			break;
		}
		
//		printf("%llu:\t%llu\t<%llu>\t%llu (%llu %d)\n", n, min, k, max, max - min, my_log2(n));
		if (max - min > my_log2(n) + x) {
			x = max - min - my_log2(n);
			printf("x = +%d starting from %llu (%llu*%llu %llu)\n", x, n, min, min-1, min*(min-1));
		}
	}
}