# Solve formulas containing the floor function

1. Jul 24, 2007

### 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.

2. Jul 24, 2007

### 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.

3. Jul 24, 2007

### dodo

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.)

Last edited: Jul 25, 2007
4. Jul 25, 2007

### 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.

5. Jul 25, 2007

### 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.

Last edited: Jul 25, 2007
6. Jul 25, 2007

### HallsofIvy

Staff Emeritus
And that has what to do with the original question?

7. Jul 26, 2007

### CRGreathouse

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

8. Jul 27, 2007

### 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.

Last edited: Jul 27, 2007
9. Jul 27, 2007

### 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.

10. Jul 27, 2007

### 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.

11. Jul 30, 2007

### 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.

Last edited: Jul 30, 2007