initial commit

1 files changed, 58 insertions, 0 deletions

diff --git a/euler44.c b/euler44.c
new file mode 100644
index 0000000..db032aa
--- /dev/null
+++ b/euler44.c
@@ -0,0 +1,58 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+long long Pn(int n)
+{
+	return (long long)n*(long long)(3*n-1)/2;
+}
+
+#define MAXSIZE (1<<22)
+long long P[MAXSIZE];
+
+int comp(const void *a, const void *b)
+{
+	long long aa = *(long long*)a;
+	long long bb = *(long long*)b;
+	if (aa < bb)
+		return -1;
+	if (aa > bb)
+		return 1;
+	return 0;
+}
+
+int main()
+{
+	int i, j;
+	int range = (1<<15);
+	for (i = 1; i < range; i++)
+		P[i] = Pn(i);
+
+	/* i < 257 is impossible when searching with range=(1<<15) */
+	/* i < 725 is impossible with range=(1<<18) */
+	/* i < 1449 is impossible with range=(1<<20) */
+	for (i = 1; i < range; i++) {
+		long long diff = P[i];
+		for (j = 1; j < range - 1; j++) {
+			long long Pj = P[j];
+			long long Pk = Pj + diff;
+			long long Pjk = Pj + Pk;
+			if (Pk < P[j+1])
+				break;
+			while (Pjk > P[range-1]) {
+				int newrange = range * 2;
+				int r;
+				for (r = range; r < newrange; r++)
+					P[r] = Pn(r);
+				range = newrange;
+			}
+			if (!bsearch(&Pk, P+1, range-1, sizeof(long long), comp))
+				continue;
+			if (!bsearch(&Pjk, P+1, range-1, sizeof(long long), comp))
+				continue;
+			printf("i = %d, D = %lld, j = %d, P[j] = %lld\n", i, diff, j, Pj);
+			/* i = 1912, D = 5482660, j = 1020, P[j] = 1560090 */
+			return 0;
+		}
+		printf("i = %d\n", i);
+	}
+}