• If you are citizen of an European Union member nation, you may not use this service unless you are at least 16 years old.

  • You already know Dokkio is an AI-powered assistant to organize & manage your digital files & messages. Very soon, Dokkio will support Outlook as well as One Drive. Check it out today!


OEIS A084639

Page history last edited by Bill McEachen 2 years, 6 months ago

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)
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.