re: my comment made to this sequence, here is my attempt to xplain it.
okay, see attached file. sorry to make anything not clear enough, I seem to think at a speed different than I can write !)
I began with small bitstrings of 3, 4 and 5 bits as you can see, and varying # of bit transitions ("1x in file means 1 transition, 2x two transitions, etc)
essentially look at the orange shading, I looked for the "adjustment" required to make things work out for what the maximal decimal value of the bit string could be as a f{# set bits, # bit transitions}
I added cell comments for clarity at C20-C22
So, for xample, treating a N=4 bitstring, can form a matrix of # set bits and # bit transitions
SO, we can have
1110 (3 set bits, 1 transition)
1101 (3 set bits, 2 transition)
1100 (2 set bits, 1 transition)
1010 (2 set bits, 3 transition)
1001 (2 set bits, 2 transition)
etc
I concluded the max value = N-1 left aligned bits + (2^k -2) - adjustment/correction as per my first email [ it's only an "adjustment" from the "incorrect" partial form, it's just part of the formula ...]
where k= (N - #set bits). By left aligned bits, see cells C20-C22. For 2 set bits in a 4 bit string, the upper bound (max) is 1100 obviously or 12. For that case, it has 1 transition, so k=4-2, so 2^k-2=2, as you'll see in those cells C20-C22. This yields A+B=12+2=14, which is the absolute max one can see for N=4 (given the initial restriction that not all bits are set) ie 1110=14, so there is no adjustment. However, for 2 bit transitions, the upper bound is 1101=13, 1 less than 14. For 3 transitions, the upper bound is 1010=10, 4 less than 14. Etc
this generated a sequence 0,1,4,9,20,41,84,169... as the correction ("C"), actually a subtraction.
I then searched OEIS and got the hit to A084639. I then immed tried the 30 bit one and it matched, so formula seems correct (the A+B+C) though it should have read A+B-C in my earlier email I think
SO, the final bound is (N-1 left aligned bits ) + 2^(N -#set bits-1) - A084639(ptr) with ptr=#bit transitions-1
- - -
I think my comments saying how to use WA to generate entries was editted out but one merely follows the pattern as:
for a(32), the input is (note it's 33 bits in each part)
111111111111111111111111111111110 base 2 - 101010101010101010101010101010101 base 2
(one just adds or subtracts a 1 from the front part, and mimics the alternating pattern for the back part )
Comments (0)
You don't have permission to comment on this page.