/* Generate b-file for sequence A340287.
   Kevin Ryde, January 2021.

   Usage: gcc -O3 a340287-bfile.c
          ./a.out >b340287.txt

   A prospective term n is tested by examining its digits in each base b.
   Only odd n are tested.  Even n are eliminated by base b=2 because low
   0-bit is != b-1 and always have a 1-bit = b-1 somewhere above.
   Base b=2 says nothing about odd n since low 1-bit = b-1.

   Bases 4 and 8 are checked by bit-twiddling.  This eliminates some n
   quickly.  Bases 3,5,6,7 use an inlined macro.  This is a convenient way
   to skip bases 4 and 8, and also lets the compiler see some divisions by
   constant which it might reduce to multiply by inverse.

   The default WORD type is 64-bits, even on a 32-bit machine, since the
   code is fast enough to exceed 32-bits after a few minutes run even on a
   nowadays modest CPU.  (On a 32-bit machine try "gcc -O9 -fno-pie -static"
   or similar to avoid PLT slowdowns when calling libgcc for 64-bit
   division.  But an actual 64-bit machine will be preferred.)

   N_STOP is 1 which means stop on wraparound to n=1 again.  This is
   effectively an unlimited search since 64-bits is much too big to iterate
   all the way around explicitly.
 */

#include <limits.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

#define N_START  1   /* an odd number */
#define N_STOP   1   /* stop on wrap-around to 1 again */

typedef uint64_t  WORD;          /* must be an unsigned type */
#define WORD_BITLEN  (CHAR_BIT*sizeof(WORD))   /* bit length */

#ifdef __GNUC__
#define LIKELY(cond)    __builtin_expect((cond) != 0, 1)
#define UNLIKELY(cond)  __builtin_expect((cond) != 0, 0)
#else
#define LIKELY(cond)    (cond)
#define UNLIKELY(cond)  (cond)
#endif

/* MASK(2) is bit pairs     .. 01  01  01  00
   MASK(3) is bit triplets  ..001 001 001 000

   Each whole group of w many bits in WORD is 1, except the lowest group of
   w bits is 0s.  A partial group at the high end of the WORD is left as 0s
   (for instance when WORD_BITLEN is not a multiple of 3 bits).
*/
#define MASK(w)  (((~(WORD)0 >>(w+(WORD_BITLEN%w))) /((1<<w)-1)) <<w)

#define TRY_B(b)                                                        \
  do {                                                                  \
    WORD bad = b-1;                                                     \
    WORD r = n % b;   /* least significant digit in base b */           \
    WORD q = n / b;   /* all digits above it */                         \
    if (UNLIKELY( r==bad )) {                                           \
      continue;  /* ignore this b */                                    \
    }                                                                   \
    if (UNLIKELY( q < bad )) {                                          \
      /* high part <= b-2, no digit b-1 in this b or any bigger b, */   \
      /* found term */                                                  \
      return 1;                                                         \
    }                                                                   \
    do {                                                                \
      r = q % b;   /* digit in base b */                                \
      q = q / b;                                                        \
      if (UNLIKELY( r==bad )) {                                         \
        return 0;                                                       \
      }                                                                 \
    } while (LIKELY(q!=0));                                             \
  } while(0)

/* Return 1 if n is a term of A340287, or return 0 if not. */
static inline int
is_A340287 (WORD n)
{
  WORD b;
  {
    /* Bases b=4 or b=8.
       "and3" has 111 triple become a 1-bit, eg. 111 -> xx1, or anything
       else such as 101 -> xx0.
       "notlow3" is all 1-bits when low digit not 111, so that any higher
       111 will mean bad.
    */
    WORD and2 = n & (n>>1);
    WORD and3 = and2 & (n>>2);
    WORD notlow2 = (and2 & 1) - 1;
    WORD notlow3 = (and3 & 1) - 1;
    if (LIKELY(  ( and2 & notlow2 & MASK(2) )
               | ( and3 & notlow3 & MASK(3) ) )) {
      return 0;
    }
  }

  TRY_B(3);   /* other than b=4,b=8 */
  TRY_B(5);
  TRY_B(6);
  TRY_B(7);
  for (b = 9; ; b++) {
    TRY_B(b);
  }
}

int
main (void)
{
  unsigned count = 0;
  WORD n = N_START;
  setbuf(stdout,0);
  do {
    if (UNLIKELY( is_A340287(n) )) {
      count++;
      printf("%u %Lu\n", count, (unsigned long long) n);
    }
  } while ((n+=2) != N_STOP);
  return 0;
}