//----------------------------------------------------------------------------
// An LFSR-based algorithm to construct a cut-down DB sequence of length L
// based on an algorithm by Golomb.  Uses hard coded primitive polynomials
// for n up to 25.  See https://debruijnsequence.org/db/code/lfsr/poly.c
// for a program to list all primitive polynomials for a given n
// NOTE: This method does not work for L a power of 2


// Programmed by Joe Sawada, 2022
//----------------------------------------------------------------------------
#include<stdio.h>
#include<math.h>
#include<stdlib.h>

int prim[26][26] = {
    { },
    {1,1},
    {1,1,1},
    {1,0,1,1},
    {1,0,0,1,1},
    {1,0,1,0,0,1},
    {1,0,0,0,0,1,1},
    {1,0,0,0,0,0,1,1},
    {1,0,0,0,1,1,1,0,1},
    {1,0,0,0,0,1,0,0,0,1},
    {1,0,0,0,0,0,0,1,0,0,1},
    {1,0,0,0,0,0,0,0,0,1,0,1},
    {1,0,0,0,0,0,1,0,1,0,0,1,1},
    {1,0,0,0,0,0,0,0,0,1,1,0,1,1},
    {1,0,0,0,0,0,0,0,0,1,0,1,0,1,1},
    {1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1},
    {1,0,0,0,0,0,0,0,0,0,0,1,0,1,1,0,1},
    {1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1},
    {1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,1,1},
    {1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,1,1},
    {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1},
    {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1},
    {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1},
    {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1},
    {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,1,1},
    {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1}
};

int n, taps[100], s[100];
long long int total=0, L;

//===========================================
// Find string s[] after L iterations
//===========================================
void LFSR() {
    int i,j,next,a[100];
    
    for (i=1; i<n; i++) a[i] = 0;
    a[n] = 1;
    for (i=1; i<=L; i++) {
        next = 0;
        for (j=1; j<=n; j++) next += taps[j]*a[n-j+1];
        for (j=1; j<n; j++) a[j] = a[j+1];
        a[n] = next%2;
    }
    for (i=1; i<=n; i++) s[i] = a[i];
}
//===================================================================
// Iterate LFSR starting with both 0^{n-1}1 and s[] until a conjugate
// pair is found (they share the same length n-1 suffix).  Once found
// the next L symbols from a[] form a cycle of length L. (Golomb)
//===================================================================
void LFSR2() {
    int i,j,next,next2,a[100],match=0;
        
    for (i=1; i<n; i++) a[i] = 0;
    a[n] = 1;

    while (1) {
        if (match == 0) {
            // Compare
            for (j=2; j<=n; j++) if (a[j] != s[j]) break;
            if (j > n) match = 1;
        }
        
        next = next2 = 0;
        for (j=1; j<=n; j++) next += taps[j]*a[n-j+1];
        for (j=1; j<=n; j++) next2 += taps[j]*s[n-j+1];

        //shift
        for (j=1; j<n; j++) a[j] = a[j+1];
        a[n] = next%2;
        
        for (j=1; j<n; j++) s[j] = s[j+1];
        s[n] = next2%2;
        
        if (match) {
            printf("%d", a[n]); total++;
            if (total == L) break;
        }
    }
}
//===============================================
int main(int argc, char **argv) {
    
    printf("Enter length of cutdown DB sequence: "); scanf("%lld", &L);
    
    n=0;
    while (L > pow(2,n)) n++;
    
    if (pow(2,n) == L) { printf("This method does not work when L is a power of 2\n"); exit(0); }
        
    for (int i=0; i<=n; i++) taps[i] = prim[n][i];
    LFSR();
    LFSR2();
    printf("\n\n");
}