The derivative of (b/r)(n+2^r) = (b (2^r (r ln(2) - 1) - n))/r^2. A minimum occurs when the derivative == 0, which occurs when 2^r (r ln(2) - 1) - n = 0. For n == 2^20 (about 1 million), r ~= 16.606232 results in O() ~= 2212837. Some example values and O():

 r   O
18   2330169
17   2220514
16   2228224
15   2306867
12   2807125

So r = 16 would be the best actual number based on the formula. However since L1 cache is typically 32 KB, smaller values of r are best. On my system (Intel 2600K 3.4 ghz), for n = 2^20, then 4 fields of 8, 8, 8, 8 (r = 8) is fastest. This changes at around n = 2^24 to 3 fields of 10, 11, 11 being slightly faster.

The derivative of (b/r)(n+2^r) = (b (2^r (r ln(2) - 1) - n))/r^2. A minimum occurs when the derivative == 0, which occurs when 2^r (r ln(2) - 1) - n = 0. For n == 2^20 (about 1 million), r ~= 16.606232 results in O() ~= 2212837. Some example values and O():

 r   O
18   2330169
17   2220514
16   2228224
15   2306867
12   2807125

So r = 16 would be the best actual number based on the formula. However since L1 cache is typically 32 KB, the optimal values for r are less. On my system (Intel 2600K 3.4 ghz), for n = 2^20, then 4 fields of 8, 8, 8, 8 (r = 8) is fastest. At around n = 2^24 3 fields of 10, 11, 11 (r = 10.67) is fastest. At around n = 2^26, 2 fields of 16, 16 (r = 16) is fastest. There's not a lot of difference though, less than 10%.