## A C version, using builting popcount

Works better with `clang -O3`, but also works if you only have `gcc`.

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    unsigned long pairs(unsigned int n, unsigned long s) { 
      unsigned long result = 0;
    
      for(int d=1;d<=n;d++) { 
        unsigned long mx = 1 << d;
        unsigned long mask = mx - 1;
    
        unsigned long diff = (s >> (n - d)) ^ (s & mask);
        if (__builtin_popcountl(diff) <= 1)
          result |= mx;
      } 
      return result;
    
    }
    
    unsigned long f(unsigned long  n) { 
      unsigned long max = 1 << (n - 1);
    #define BLEN (max / 2)
      unsigned char * buf = malloc(BLEN);
      memset(buf, 0, BLEN);
      unsigned long long * bufll = (void *) buf;
    
      for(unsigned long i=0;i<=max;i++) { 
        unsigned int r = pairs(n, i);
        buf[r / 8] |= 1 << (r % 8);
      } 
    
      unsigned long result = 0;
    
      for(unsigned long i=0;i<= max / 2 / sizeof(unsigned long long); i++) { 
        result += __builtin_popcountll(bufll[i]);
      } 
    
      free(buf);
    
      return result;
    }
    
    int main(int argc, char ** argv) { 
      unsigned int n = 1;
    
      while(1) { 
        printf("%d %ld\n", n, f(n));
        n++;
        if(n>24)
          break;
      } 
      return 0;
    }