gcd_difference

bruteforce for https://oeis.org/A199768
git clone https://a3nm.net/git/gcd_difference/
Log | Files | Refs

calc.cpp (1175B)

      1 #include<limits.h>
      2 #include "InfInt.h"
      3 #include <cstdio>
      4 #include <deque>
      5 #include <cassert>
      6 #include <numeric>
      7 
      8 using namespace std;
      9 
     10 // http://math.stackexchange.com/q/2099305
     11 
     12 bool ok(deque<InfInt> &v) {
     13   for (unsigned int i = 0; i < v.size(); i++)
     14     for (unsigned int j = i+1; j < v.size(); j++)
     15       if (v[i] % (v[j] - v[i]) > 0)
     16         return false;
     17   return true;
     18 }
     19 
     20 
     21 // http://stackoverflow.com/a/4229930
     22 InfInt gcd(InfInt a, InfInt b)
     23 {
     24     for (;;)
     25     {
     26         if (a == 0) return b;
     27         b %= a;
     28         if (b == 0) return a;
     29         a %= b;
     30     }
     31 }
     32 
     33 // http://stackoverflow.com/a/4229930
     34 InfInt lcm(InfInt a, InfInt b)
     35 {
     36     InfInt temp = gcd(a, b);
     37 
     38     return temp > 0 ? (a / temp * b) : 0;
     39 }
     40 
     41 int main(int argc, char **argv) {
     42   deque<InfInt> v;
     43   v.push_front(1);
     44   assert(argc == 2);
     45   for (int iter = 0; iter < atoi(argv[1]); iter++) {
     46     InfInt mygcd = 1;
     47     for (auto x: v)
     48       mygcd = lcm(mygcd, x);
     49     v.push_front(0);
     50     for (auto &x : v)
     51       x += mygcd;
     52     printf("%ld:", v.size());
     53     for (auto x : v)
     54       cout << " " << x;
     55     printf("\n");
     56     if (!ok(v)) {
     57       printf("PROBLEM\n");
     58       return 1;
     59     }
     60   }
     61   return 0;
     62 }
     63 
     64