Solve formulas containing the floor function

dodo

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

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

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

Kummer

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

[tex]a=a_0+2\cdot a_1+2^2\cdot a_2+\cdots+2^k\cdot a_k[/tex]

Then

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

for n > i.

HallsofIvy

And that has what to do with the original question?

CRGreathouse

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

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

[tex]\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) }[/tex]

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.