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

  • Whenever you search in PBworks or on the Web, Dokkio Sidebar (from the makers of PBworks) will run the same search in your Drive, Dropbox, OneDrive, Gmail, Slack, and browsed web pages. Now you can find what you're looking for wherever it lives. Try Dokkio Sidebar for free.


OEIS A084639

Page history last edited by Bill McEachen 1 year, 8 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.