A275692 Numbers k such that every rotation of the binary digits of k is less than k.

0, 1, 2, 4, 6, 8, 12, 14, 16, 20, 24, 26, 28, 30, 32, 40, 48, 50, 52, 56, 58, 60, 62, 64, 72, 80, 84, 96, 98, 100, 104, 106, 108, 112, 114, 116, 118, 120, 122, 124, 126, 128, 144, 160, 164, 168, 192, 194, 196, 200, 202, 208, 210, 212, 216, 218, 224, 226, 228

Offset: 1

Author

Robert Israel, Aug 05 2016

Keywords

• nonn

Comments

0, and terms of A065609 that are not in A121016.

Number of terms with d binary digits is A001037(d).

Take the binary representation of a(n), reverse it, add 1 to each digit. The result is the decimal representation of A102659(n).

From Gus Wiseman, Apr 19 2020: (Start)

Also numbers k such that the k-th composition in standard order (row k of A066099) is a Lyndon word. For example, the sequence of all Lyndon words begins:

0: () 52: (1,2,3) 118: (1,1,2,1,2)

1: (1) 56: (1,1,4) 120: (1,1,1,4)

2: (2) 58: (1,1,2,2) 122: (1,1,1,2,2)

4: (3) 60: (1,1,1,3) 124: (1,1,1,1,3)

6: (1,2) 62: (1,1,1,1,2) 126: (1,1,1,1,1,2)

8: (4) 64: (7) 128: (8)

12: (1,3) 72: (3,4) 144: (3,5)

14: (1,1,2) 80: (2,5) 160: (2,6)

16: (5) 84: (2,2,3) 164: (2,3,3)

20: (2,3) 96: (1,6) 168: (2,2,4)

24: (1,4) 98: (1,4,2) 192: (1,7)

26: (1,2,2) 100: (1,3,3) 194: (1,5,2)

28: (1,1,3) 104: (1,2,4) 196: (1,4,3)

30: (1,1,1,2) 106: (1,2,2,2) 200: (1,3,4)

32: (6) 108: (1,2,1,3) 202: (1,3,2,2)

40: (2,4) 112: (1,1,5) 208: (1,2,5)

48: (1,5) 114: (1,1,3,2) 210: (1,2,3,2)

50: (1,3,2) 116: (1,1,2,3) 212: (1,2,2,3)

(End)

Examples

			6 is in the sequence because its binary representation 110 is greater than all the rotations 011 and 101.
10 is not in the sequence because its binary representation 1010 is unchanged under rotation by 2 places.
From _Gus Wiseman_, Oct 31 2019: (Start)
The sequence of terms together with their binary expansions and binary indices begins:
    1:       1 ~ {1}
    2:      10 ~ {2}
    4:     100 ~ {3}
    6:     110 ~ {2,3}
    8:    1000 ~ {4}
   12:    1100 ~ {3,4}
   14:    1110 ~ {2,3,4}
   16:   10000 ~ {5}
   20:   10100 ~ {3,5}
   24:   11000 ~ {4,5}
   26:   11010 ~ {2,4,5}
   28:   11100 ~ {3,4,5}
   30:   11110 ~ {2,3,4,5}
   32:  100000 ~ {6}
   40:  101000 ~ {4,6}
   48:  110000 ~ {5,6}
   50:  110010 ~ {2,5,6}
   52:  110100 ~ {3,5,6}
   56:  111000 ~ {4,5,6}
   58:  111010 ~ {2,4,5,6}
(End)
		

Links

• Robert Israel, Table of n, a(n) for n = 1..9868

Crossrefs

A similar concept is A328596.

Numbers whose binary expansion is aperiodic are A328594.

Numbers whose reversed binary expansion is a necklace are A328595.

Binary necklaces are A000031.

Binary Lyndon words are A001037.

Lyndon compositions are A059966.

Length of Lyndon factorization of binary expansion is A211100.

Length of co-Lyndon factorization of binary expansion is A329312.

Length of Lyndon factorization of reversed binary expansion is A329313.

Length of co-Lyndon factorization of reversed binary expansion is A329326.

Cf. A000031, A000740, A008965, A027375, A102659, A121016.

All of the following pertain to compositions in standard order (A066099):

- Length is A000120.

- Necklaces are A065609.

- Sum is A070939.

- Rotational symmetries are counted by A138904.

- Strict compositions are A233564.

- Constant compositions are A272919.

- Lyndon compositions are A275692 (this sequence).

- Co-Lyndon compositions are A326774.

- Rotational period is A333632.

- Co-necklaces are A333764.

- Co-Lyndon factorizations are counted by A333765.

- Lyndon factorizations are counted by A333940.

- Reversed necklaces are A333943.

Cf. A034691, A060223, A124767, A269134, A292884.

Programs

Maple

filter:= proc(n) local L, k;
  L:= convert(convert(n,binary),string);
  for k from 1 to length(L)-1 do
    if lexorder(L,StringTools:-Rotate(L,k)) then return false fi;
  od;
  true
end proc:
select(filter, [$0..1000]);

Mathematica

filterQ[n_] := Module[{bits, rr}, bits = IntegerDigits[n, 2]; rr = NestList[RotateRight, bits, Length[bits]-1] // Rest; AllTrue[rr, FromDigits[#, 2] < n&]];
Select[Range[0, 1000], filterQ] (* Jean-François Alcover, Apr 29 2019 *)

Python

def ok(n):
    b = bin(n)[2:]
    return all(b[i:] + b[:i] < b for i in range(1, len(b)))
print([k for k in range(230) if ok(k)]) # Michael S. Branicky, May 26 2022