Sum of indices of second least significant bit

k [21 chars]

{+/{(&|0b\:x)1}'!x+1}

Example

{+/{(&|0b\:x)1}'!x+1}[3]
1

{+/{(&|0b\:x)1}'!x+1}[7]
6

{+/{(&|0b\:x)1}'!x+1}[10]
12

{+/{(&|0b\:x)1}'!x+1}[500]
1410

GolfScript (31 chars)

,{)2base-1%.,,\`{=}+,1=}%0+{+}*

This takes input on the stack and leaves output on the stack. Online demo which wraps it in a loop to output the first 12 values.

That implementation does the obvious thing of computing the base-2 representation of the integers in range. A more interesting approach, which sadly I haven't been able to golf as far, is to analyse the sequence. It's a sum of indices: let i2(n) be the index of the second LSB of n. We have i2(2^x) = 0 (given as a special case). What can we say about the values which i2 takes between 2^x and 2^(x+1)?

  • Case 1: 2^x < k < 2^x + 2^(x-1). Then k ^ (2^x + 2^(x-1)) = k - 2^(x-1). If i2(k - 2^(x-1)) < x-1 then i2(k) = i2(k - 2^(x-1)); otherwise i2(k) = x = 1 + i2(k - 2^(x-1)).
  • Case 2: k = 2^x + 2^(x-1). Obviously i2(k) = x since there are two bits set.
  • Case 3: 2^x + 2^(x-1) < k < 2^(x+1) has bit x-1 set and at least one less significant bit set, so i2(k) = i2(k - 2^x).

In other words: the sequence of indices between consecutive powers of two can be found by splicing together three sequences: the previous sequence under the substitution s/x-1/x/; the sequence [x]; and the previous sequence unmodified.

  • []
  • [] + [1] + [] = [1]
  • [2] + [2] + [1] = [2 2 1]
  • [3 3 1] + [3] + [2 2 1] = [3 3 1 3 2 2 1]
  • [4 4 1 4 2 2 1] + [4] + [3 3 1 3 2 2 1] = [4 4 1 4 2 2 1 4 3 3 1 3 2 2 1]
  • etc.

This leads to (40 chars)

([]{,2$<}{..0+0=:x+{.x=+}%\+}/1,*<0+{+}*

(Note for GS aficionados: a rare use for unfold!)


J (and mathematics), way too much (aka. 45 chars), cubic memory and terrible runtime

+/,(*v>(2&^*1+a*2:)+/2^i.)"0]a=.i.v=.".1!:1]1

If I wanted to aim for length, I could of course do it the obvious, straightforward way and get something considerably shorter... however, I found it more interesting to investigate the properties of "index of second least significant set bit".

The J program above is an instance of the formula derived below. The idea is to build a huge table of numbers per bit index, then filter out those below the number we seek, then multiply by the bit index, then sum it all up.


So, I started with the slightly different case "index of the least significant set bit" (LSSB), because it's always best to start simple when looking for patterns... I plotted the index of the LSSB for numbers [0..40]:

          1111111111222222222233333333334
01234567890123456789012345678901234567890
-0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0   =  2k + 1
  1   1   1   1   1   1   1   1   1   1    =  4k + 2
    2       2       2       2       2      =  8k + 4
        3               3               3  = 16k + 8
                4
                                5

(Here, - means N/A.) Well, that's a very obvious pattern. Joining the cases together we get 2^v * (2k + 1) for row v, for integers k (or, 2^v * m for odd m, if you prefer). This is sequence A007814 in OEIS.

Okay, so, back to our real case of the second least significant set bit (2LSSB). Let's do a similar plot for this case and see if there's any pattern here too, and if so, how it relates to the previous pattern.

          1111111111222222222233333333334
01234567890123456789012345678901234567890
--- -   -       -               -
   1   1   1   1   1   1   1   1   1   1
     22      22      22      22      22
         33 3            33 3
                 44 4   4
                                 55 5   5

Well... huh. That looks a bit strange, but there's still some sort of repetition going on. Let's take a look at what numbers get assigned which indices.

0: 0 1 2 4 8 16 32             ...  2^k
1: 3 7 11 15 19 23 27 31 35 39 ...  4k +  2 + {1}           =  2*(2k + 1) + 2^{0}
2: 5 6 13 14 21 22 29 30 37 38 ...  8k +  4 + {1,2}         =  4*(2k + 1) + 2^{0,1}
3: 9 10 12 25 26 28            ... 16k +  8 + {1,2,4}       =  8*(2k + 1) + 2^{0,1,2}
4: 17 18 20 24                 ..? 32k + 16 + {1,2,4,8}     = 16*(2k + 1) + 2^{0,1,2,3}
5: 33 34 36 40                 ..? 64k + 32 + {1,2,4,8,16}  = 32*(2k + 1) + 2^{0,1,2,3,4}

Okay, yeah, definitely a pattern. The general case here is 2^v * (2k + 1) + 2^j, j < v. While we're at it, let's do one more just to see how this all generalises for the n:th least significant set bit.

                                                                                                    111111111111111111111111111111
          111111111122222222223333333333444444444455555555556666666666777777777788888888889999999999000000000011111111112222222222
0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789
 01 012 4       012 4   8      16                               012 4   8      16              32   ...
  012   012 4   8               012 4   8      16              32                                   ...
------- --- -   --- -   -       --- -   -       -               --- -   -       -               -                                       =   2^k + 2^l, l < k                                 0
                                                                                                                                                                                             1
       2       2       2       2       2       2       2       2       2       2       2       2       2       2       2       2        =   8*k +  4 + {3}                                   2
           3 33            3 33            3 33            3 33            3 33            3 33            3 33            3 33         =  16*k +  8 + {3,5,6}                               3
                   4 44  44 4                      4 44  44 4                      4 44  44 4                      4 44  44 4           =  32*k + 16 + {3,5,6,9,10,12}                       4
                                   5 55  55 5    55 5   5                                          5 55  55 5    55 5   5               =  64*k + 32 + {3,5,6,9,10,12,17,18,20,24}           5
                                                                   6 66  66 6    66 6   6        66 6   6       6                       = 128*k + 64 + {3,5,6,9,10,12,17,18,20,24,...}       6

Phew. 40 digits didn't cut it for finding patterns here, so I had to extend it a bit. Sorry about that horizontal scrollbar. Here's the table to the far right again, to spare you from having to scroll back and forth.

   2^k + 2^l, l < k                                 0
                                                    1
   8*k +  4 + {3}                                   2
  16*k +  8 + {3,5,6}                               3
  32*k + 16 + {3,5,6,9,10,12}                       4
  64*k + 32 + {3,5,6,9,10,12,17,18,20,24}           5
 128*k + 64 + {3,5,6,9,10,12,17,18,20,24,...}       6

Huh. That's weird, what are those numbers? They're certainly not powers of two... maybe I should've been able to guess it from the earlier two tables, but instead I went to OEIS and found it's actually the set of sums of two distinct powers of two. So it seems like a qualified guess to generalise this by taking the sum of n distinct powers of two for the index of the n:th least significant set bit. All in all, the final expression looks like so:

Screenshot of expression

Tags:

Code Golf