# Combining sum of floor functions

Consider a simple sum of floor functions: $$S = c\left\lfloor \frac{x}{a}\right\rfloor + d\left\lfloor \frac{x}{b} \right\rfloor$$

Can we combine these two terms into a single function? I am trying to simplify something like this to avoid successive divisions in a computer program.

My question, in general, is: can we combine the following $k$ terms to avoid performing $k$ divisions and multiplications of $x$: $$S(x,k)=\sum_{i=0}^{k}c_i\left\lfloor \frac{x}{a_i}\right\rfloor$$

• Are you assuming anything about $a,b,c,d$ (e.g. that they are positive integers)? Jun 8 '17 at 21:30
• Yes, we can assume that every coefficient is a positive integer Jun 8 '17 at 21:35
• No such combination formula in general. Computation-wise (assuming $x$ is a variable and $a_i$ are constants) you could save the divisions by pre-computing $1/a_i$ to reduce it to multiplications in the loop.
– dxiv
Jun 9 '17 at 5:19
• Is there a way to prove that no such combination formula exists? I.e., can we prove that the summation given above must require k operations to find S(x,k) for a given x? Jun 9 '17 at 20:24
• Are you trying to build the table of $S(x, k)$ ? Jun 10 '17 at 2:07

A simple compute, this might not be a proof :

Assume $\exists a, b \in \Bbb N$ s.t. $\forall x$

$$\left[\frac{x}{2}\right] + \left[\frac{x}{3}\right] = a\left[\frac{x}{b}\right]$$

put x = 2 :

$$a\left[\frac{2}{b}\right] = 1$$

$$\Rightarrow a = 1, b = 2$$

But $\left[\frac{x}{2}\right] + \left[\frac{x}{3}\right] > \left[\frac{x}{2}\right]$ for large enough $x$.

This form might not be able to simplify if the denominators has no limitation.

• Did you mean to conclude $b=2$? Jun 9 '17 at 3:39
• Oh thanks @Matthew Conroy Jun 9 '17 at 4:09
• I'm not sure I follow. Are you attempting to prove that such an a,b exist or are you showing that they do not exist? Jun 9 '17 at 20:29
• @Nisrak, a, b do not exist. Jun 10 '17 at 1:23
• I see. Any ideas to develop a more complete proof? Maybe we can somehow equate this to combining terms of a polynomial, which you obviously can't do? Jun 10 '17 at 2:01