gcd_difference

commit 6403a87d3789e14d58a7e9aeffbaadd6bd58f810
parent c2328312eada1d6fc7f266ed23bd60aea55299b0
Author: Antoine Amarilli <a3nm@a3nm.net>
Date:   Sun, 12 Mar 2017 10:44:17 +0100

implement computation

Diffstat:
.gitignore
 | 
1
+
calc.cpp
 | 
56
++++++++++++++++++++++++++++++++++++++++++++++++++++++++

2 files changed, 57 insertions(+), 0 deletions(-)
diff --git a/.gitignore b/.gitignore
@@ -0,0 +1 @@
+a.out
diff --git a/calc.cpp b/calc.cpp
@@ -0,0 +1,56 @@
+#include <cstdio>
+#include <deque>
+#include <cassert>
+#include <numeric>
+
+using namespace std;
+
+// http://math.stackexchange.com/q/2099305
+
+bool ok(deque<long long> &v) {
+  for (unsigned int i = 0; i < v.size(); i++)
+    for (unsigned int j = i+1; j < v.size(); j++)
+      if ((v[j] - v[i]) % v[i])
+        return false;
+  return true;
+}
+
+
+// http://stackoverflow.com/a/4229930
+long long gcd(long long a, long long b)
+{
+    for (;;)
+    {
+        if (a == 0) return b;
+        b %= a;
+        if (b == 0) return a;
+        a %= b;
+    }
+}
+
+// http://stackoverflow.com/a/4229930
+long long lcm(long long a, long long b)
+{
+    long long temp = gcd(a, b);
+
+    return temp ? (a / temp * b) : 0;
+}
+
+int main() {
+  deque<long long> v;
+  v.push_front(1);
+  while (true) {
+    printf("%ld:", v.size());
+    for (auto x : v)
+      printf(" %lld", x);
+    printf("\n");
+  // http://stackoverflow.com/a/4229930
+  long long gcd = std::accumulate(v.begin(), v.end(), 1, lcm);
+  v.push_front(0);
+  for (auto &x : v)
+    x += gcd;
+  }
+  assert(ok(v));
+}
+
+