login
c-squarefree numbers: positive integers which in binary are concatenation of distinct parts of the form 10...0 with nonnegative number of zeros.
155

%I #66 Apr 06 2020 18:22:08

%S 0,1,2,4,5,6,8,9,12,16,17,18,20,24,32,33,34,37,38,40,41,44,48,50,52,

%T 64,65,66,68,69,70,72,80,81,88,96,98,104,128,129,130,132,133,134,137,

%U 140,144,145,152,160,161,176,192,194,196,200,208,256,257,258,260,261

%N c-squarefree numbers: positive integers which in binary are concatenation of distinct parts of the form 10...0 with nonnegative number of zeros.

%C Number of terms in interval [2^(n-1), 2^n) is the number of compositions of n with distinct parts (cf. A032020). For example, if n=6, then interval [2^5, 2^6) contains 11 terms {32,...,52}. This corresponds to 11 compositions with distinct parts of 6: 6, 5+1, 1+5, 4+2, 2+4, 3+2+1, 3+1+2, 2+3+1, 2+1+3, 1+3+2, 1+2+3.

%C From _Gus Wiseman_, Apr 06 2020: (Start)

%C The k-th composition in standard order (row k of A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions. This sequence lists all numbers k such that the k-th composition in standard order is strict. For example, the sequence together with the corresponding strict compositions begins:

%C 0: () 38: (3,1,2) 98: (1,4,2)

%C 1: (1) 40: (2,4) 104: (1,2,4)

%C 2: (2) 41: (2,3,1) 128: (8)

%C 4: (3) 44: (2,1,3) 129: (7,1)

%C 5: (2,1) 48: (1,5) 130: (6,2)

%C 6: (1,2) 50: (1,3,2) 132: (5,3)

%C 8: (4) 52: (1,2,3) 133: (5,2,1)

%C 9: (3,1) 64: (7) 134: (5,1,2)

%C 12: (1,3) 65: (6,1) 137: (4,3,1)

%C 16: (5) 66: (5,2) 140: (4,1,3)

%C 17: (4,1) 68: (4,3) 144: (3,5)

%C 18: (3,2) 69: (4,2,1) 145: (3,4,1)

%C 20: (2,3) 70: (4,1,2) 152: (3,1,4)

%C 24: (1,4) 72: (3,4) 160: (2,6)

%C 32: (6) 80: (2,5) 161: (2,5,1)

%C 33: (5,1) 81: (2,4,1) 176: (2,1,5)

%C 34: (4,2) 88: (2,1,4) 192: (1,7)

%C 37: (3,2,1) 96: (1,6) 194: (1,5,2)

%C (End)

%H <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>

%e 49 in binary has the following parts of the form 10...0 with nonnegative number of zeros: (1),(1000),(1). Two of them are the same. So it is not in the sequence. On the other hand, 50 has distinct parts (1)(100)(10), thus it is a term.

%t bitPatt[n_]:=bitPatt[n]=Split[IntegerDigits[n,2],#1>#2||#2==0&];

%t Select[Range[0,300],bitPatt[#]==DeleteDuplicates[bitPatt[#]]&] (* _Peter J. C. Moses_, Dec 13 2013 *)

%t stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;

%t Select[Range[0,100],UnsameQ@@stc[#]&] (* _Gus Wiseman_, Apr 04 2020 *)

%Y Cf. A032020, A124771, A233249, A233312, A233416, A233420, A233569, A233655.

%Y A subset of A333489 and superset of A333218.

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

%Y - Length is A000120.

%Y - Weighted sum is A029931.

%Y - Partial sums from the right are A048793.

%Y - Sum is A070939.

%Y - Runs are counted by A124767.

%Y - Reversed initial intervals A164894.

%Y - Initial intervals are A246534.

%Y - Constant compositions are A272919.

%Y - Strictly decreasing compositions are A333255.

%Y - Strictly increasing compositions are A333256.

%Y - Anti-runs are counted by A333381.

%Y - Anti-runs are A333489.

%Y Cf. A114994, 225620, A228351, A238279, A242882, A329739, A329744, A333217.

%K nonn,base

%O 1,3

%A _Vladimir Shevelev_, Dec 13 2013

%E More terms from _Peter J. C. Moses_, Dec 13 2013

%E 0 prepended by _Gus Wiseman_, Apr 04 2020