Solve formulas containing the floor function

[dodo]

Is there a kosher way of manipulating formulas containing floor truncation, say,

\sum_{i=1}^n \left [ ~ { 333 \over 2^i } ~ \right ] ~=~ ?​

(I mean analytically, not writing a computer program to find out the result.) Thanks.

 

[Kummer]

Is there a kosher way of manipulating formulas containing floor truncation, say,

\sum_{i=1}^n \left [ ~ { 333 \over 2^i } ~ \right ] ~=~ ?​

(I mean analytically, not writing a computer program to find out the result.) Thanks.

I did not spend time on this problem, but I think not. Most problems in mathematics do not have analytic methods to them. Only special cases, or cases which can be brought to special cases. And hence computer computation is the method to use.

 

[dodo]

Thanks for your reply, Kummer.

The problem being that a computer program is not a proof, or at least not for an arbitrary n in the example above. (Actually it was a bad example because the 333 constant limits the useful values of n; let's say it's not a prove for arbitraries n and constant. But you get the idea.)

 

[matticus]

for n >= 9 that sum is 328, but i got that by summing the terms before the argument was less than 1. it seems like there should be a better way to do it. i'll think about it.

 

[CRGreathouse]

Write

a=a_0+2\cdot a_1+2^2\cdot a_2+\cdots+2^k\cdot a_k

Then

f(a, n) = \sum_{i=1}^n \frac{a}{2^i} = \sum_{i=1}^ka_i\cdot\frac12i(i+1)/2

for n > i.

 

[HallsofIvy]

Write

a=a_0+2\cdot a_1+2^2\cdot a_2+\cdots+2^k\cdot a_k

Then

f(a, n) = \sum_{i=1}^n \frac{a}{2^i} = \sum_{i=1}^ka_i\cdot\frac12i(i+1)/2

for n > i.

And that has what to do with the original question?

 

[CRGreathouse]

And that has what to do with the original question?

It's a solution of the original question for n >= 8, with the constant generalized as the poster requested in the third post.

 

[dodo]

There's a confusion here, CR: the square brackets in the first post are meant to mean "floor truncation", which effectively blocks many of the manipulations one is able to do.

So the solution for n>8 is in fact exactly the same as for n=8, for the a=333 case. For arbitrary a, it is not that clear.

 

[CRGreathouse]

There's a confusion here, CR: the square brackets in the first post are meant to mean "floor truncation", which effectively blocks many of the manipulations one is able to do.

So the solution for n>8 is in fact exactly the same as for n=8, for the a=333 case. For arbitrary a, it is not that clear.

Yes, I understand that. I'm truncating by cutting off binary digits -- sneaky, yes? In any case if you know the formula for n = 8 in the a = 33 case, but want the n = 7 case, you can calculate it just by taking the last term off the original sum.

The whole point of this formula is to get some kind of analytical formula (useful if the bits of the number have some special form). Perhaps other forms can be generalized from here -- but this is at least a starting point.

 

[dodo]

As a side note, the reason why I posted this in the Number Theory thread is that, when there is a division involved inside the truncation, I smelled congruency somewhere. The given example becomes

\sum_{i=1}^n \left [ f(i) \over g(i) \right ] = \sum_{i=1}^n { f(i) \over g(i) } - \sum_{i=1}^n { \left ( f(i) ~mod~ g(i) \right ) \over g(i) }

which I'm not sure it's more tractable than the original, since the modulo operation is nearly as blocking as the truncation.

 

[dodo]

Oh, and thanks CR for that binary decomposition trick. Indeed very clever. Though I still can't figure out how you got the compact expression above. The presence of i(i+1)/2 would suggest that some sum of integers is done somewhere, but I still don't get it.

It does have the defect of assuming you know beforehand the a_i, which is tantamount of knowing beforehand the results of the truncations. If you don't know their values, it just adds a lot of new variables. It does say something new about the structure of the expression, which is the good part and might perhaps be useful in some context.