add a slow version of 719

1 files changed, 98 insertions, 0 deletions

diff --git a/euler719_slow.c b/euler719_slow.c
new file mode 100644
index 0000000..bacff53
--- /dev/null
+++ b/euler719_slow.c
@@ -0,0 +1,98 @@
+#include <stdio.h>
+#include <stdint.h>
+#include <assert.h>
+
+#define MAXLEN 14
+
+int64_t power10tab[MAXLEN + 1];
+
+void init_pwr10()
+{
+	power10tab[0] = 1;
+	for (size_t i = 1; i <= MAXLEN; i++) {
+		power10tab[i] = power10tab[i - 1] * 10;
+	}
+}
+
+int num_len(int64_t v)
+{
+	// find the length of v
+	int len = MAXLEN;
+	for (size_t i = 0; i < MAXLEN; i++) {
+		if (v < power10tab[i]) {
+			len = i;
+			break;
+		}
+	}
+	assert(len < MAXLEN);
+	return len;
+}
+
+// split a number at digit position {s0,s1,...} and add the numbers
+// v[s0:0], v[s1:s0+1],...,v[len-1:s[last]]
+// split = (1 << s0) | (1 << s1) | ...
+
+int64_t split_num(int64_t v, int len, int split)
+{
+	int64_t sum = 0;
+	int lastsplit = 0;
+	for (int i = 0; i < len; i++) {
+		if (split & 1) {
+			int64_t segment = (v / power10tab[lastsplit])
+				% power10tab[i + 1 - lastsplit];
+			lastsplit = i + 1;
+			sum += segment;
+			// printf("%ld ", segment);
+		}
+		split >>= 1;
+	}
+	// last split is v[len-1:lastsplit]
+	int64_t segment = (v / power10tab[lastsplit])
+		% power10tab[len + 1 - lastsplit];
+	sum += segment;
+	// printf("%ld\n", segment);
+
+	return sum;
+}
+
+int64_t split_test(int64_t v, int split)
+{
+	return split_num(v, num_len(v), split);
+}
+
+int main()
+{
+	init_pwr10();
+	// split 6724 as {6,72,4} => 0b101
+	printf("sum = %ld\n", split_test(6724, 5));
+	// split 8281 as {8,2,81} => 0b110
+	printf("sum = %ld\n", split_test(8281, 6));
+	// split 8281 as {8281}
+	printf("sum = %ld\n", split_test(8281, 0));
+	// split 0
+	printf("sum = %ld\n", split_test(0, 0));
+
+	// split 10^12
+	printf("sum = %ld\n", split_test(1000000LL * 1000000LL, 0));
+
+	int64_t sum_s = 0;
+
+	// calculate T(1000000*1000000)
+	// S-numbers should be able to be splitted to 2 or more numbers, so
+	// an S-number is at least 4*4
+	for (int64_t i = 4; i <= 1000000; i++) {
+		int64_t square = i * i;
+		int L = num_len(square);
+		int maxsp = 1 << L;
+		// we need at least (L+1)/2 digits in the highest split
+		int minsp = 1 << ((L / 2) - 1);
+		for (int sp = minsp; sp < maxsp; sp++) {
+			if (split_num(square, L, sp) == i) {
+				printf("%ld is an S-number.\n", square);
+				sum_s += square;
+				break;
+			}
+		}
+	}
+	printf("The sum of S-numbers is %ld\n", sum_s);
+}