1
2 #include "bits/bit-necklace.h"
3 #include "bits/bitrotate.h"
4 #include "bits/bitcount.h"
5
6 #include "fxtio.h"
7 #include "fxttypes.h" // ulong
8
9 #include "bits/bitsperlong.h"
10 #include "jjassert.h"
11
12 #include "nextarg.h" // NXARG()
13
14 #include "bits/print-bin.h"
15 //#include "bits/bitcount.h"
16
17
18 //% OEIS sequence A226893:
19 //% Number of binary Lyndon words of length n having a conjugate at Hamming distance 2.
20
21 // Cf. bits/bit-necklace-demo.cc
22
23
24 //#define TIMING // uncomment to disable printing
25
26 int
main(int argc,char ** argv)27 main(int argc, char **argv)
28 {
29 ulong n = 8;
30 NXARG(n, "Number of bits 0<n<=BITS_PER_LONG");
31 jjassert( n>0 );
32 jjassert( n<=BITS_PER_LONG );
33
34 bit_necklace N(n);
35
36 ulong ct = 0; // count necklaces (prime strings)
37
38 do
39 {
40 if ( N.is_lyndon_word() )
41 {
42 const ulong w = N.data();
43 ulong wr=0;
44 bool q = false;
45 for (ulong r=1; r<n; ++r)
46 {
47 wr = bit_rotate_right(w, r, n);
48 if ( 2 == bit_count( w ^ wr ) )
49 {
50 q = true;
51 break;
52 }
53 }
54
55 if ( q )
56 {
57 ++ct;
58
59 #ifndef TIMING
60 cout << setw(4) << ct << ": ";
61 print_bin(" ", w, n);
62 print_bin(" ", wr, n);
63 print_bin(" ", w^wr, n);
64 // cout << " " << setw(2) << N.period();
65 cout << endl;
66 #endif // TIMING
67
68 }
69 }
70 }
71 while ( N.next() );
72
73 cout << " ct=" << ct << endl;
74
75
76 return 0;
77 }
78 // -------------------------
79
80
81 /// Emacs:
82 /// Local Variables:
83 /// MyRelDir: "demo/seq"
84 /// makefile-dir: "../../"
85 /// make-target: "1demo DSRC=demo/seq/A226893-demo.cc"
86 /// make-target2: "1demo DSRC=demo/seq/A226893-demo.cc DEMOFLAGS=-DTIMING"
87 /// End:
88
89