90, 315

1 files changed, 128 insertions, 0 deletions

diff --git a/euler315.c b/euler315.c
new file mode 100644
index 0000000..2d06cf4
--- /dev/null
+++ b/euler315.c
@@ -0,0 +1,128 @@
+#include <stdio.h>
+
+/* The digital root (also repeated digital sum) of a non-negative 
+ * integer is the (single digit) value obtained by an iterative process
+ * of summing digits, on each iteration using the result from the previous
+ * iteration to compute a digit sum. The process continues until a 
+ * single-digit number is reached.
+ */
+
+/* bit 0-2: top, mid, bottom
+ * bit 3-6: top-left, top-right, bottom-left, bottom-right
+ */
+
+enum {
+	TOP = 1,
+	MID = 2,
+	BOTTOM = 4,
+	TL = 8,
+	TR = 16,
+	BL = 32,
+	BR = 64
+};
+
+unsigned char lines[10] = {
+	TOP | BOTTOM | TL | TR | BL | BR,
+	TR | BR,
+	TOP | MID | BOTTOM | TR | BL,
+	TOP | MID | BOTTOM | TR | BR,
+	MID | TL | TR | BR,
+	TOP | MID | BOTTOM | TL | BR,
+	TOP | MID | BOTTOM | TL | BL | BR,
+	TOP | TL | TR | BR,
+	TOP | MID | BOTTOM | TL | TR | BL | BR,
+	TOP | MID | BOTTOM | TL | TR | BR
+};
+
+int popcount(unsigned char x)
+{
+	int count = 0;
+	while (x) {
+		count += (x&1);
+		x >>= 1;
+	}
+	return count;
+}
+
+void get_digits(int x, int a[])
+{
+	int i = 0;
+	do {
+		a[i] = x % 10;
+		x /= 10;
+		i++;
+	} while (x);
+	a[i] = -1;
+}
+
+int clock_sam(int x)
+{
+	int digits[10];
+	int l = 0;
+	while (x >= 10) {
+		get_digits(x, digits);
+		x = 0;
+		for (int i = 0; digits[i] != -1; i++) {
+			l += popcount(lines[digits[i]]) * 2;
+			x += digits[i];
+		}
+	}
+	l += popcount(lines[x]) * 2;
+	return l;
+}
+
+int clock_max(int x)
+{
+	int digits[10],next_digits[10], nx;
+	int l = 0;
+	get_digits(x, digits);
+	nx = 0;
+	for (int i = 0; digits[i] != -1; i++) {
+		l += popcount(lines[digits[i]]);
+		nx += digits[i];
+	}
+	while (x >= 10) {
+		get_digits(nx, next_digits);
+		int i;
+		/* calculate the diff */
+		for (i = 0; next_digits[i] != -1; i++) {
+			l += popcount(lines[digits[i]]^lines[next_digits[i]]);
+		}
+		while (digits[i] != -1) {
+			l += popcount(lines[digits[i]]);
+			i++;
+		}
+		/* get the next */
+		x = nx;
+		nx = 0;
+		for (i = 0; next_digits[i] != -1; i++) {
+			digits[i] = next_digits[i];
+			nx += next_digits[i];
+		}
+		digits[i] = -1;
+	}
+	l += popcount(lines[x]);
+	return l;
+}
+
+int isoddprime(int x)
+{
+	for (int i = 3; i*i <= x; i += 2) {
+		if (x % i == 0)
+			return 0;
+	}
+	return 1;
+}
+
+int main()
+{
+	int sum = 0;
+	const int A = 10*1000*1000;
+	const int B = 20*1000*1000;
+	for (int i = A+1; i < B; i += 2) {
+		if (isoddprime(i)) {
+			sum += clock_sam(i) - clock_max(i);
+		}
+	}
+	printf("%d\n", sum);
+}