20
$\begingroup$

Let $n\ge2$ be an integer , then $$\int_{0}^1 \prod_{k=2}^n \lfloor kx \rfloor dx=\text{ ?}, $$ where $\lfloor \space \rfloor$ is the "floor-function"

$\endgroup$
5
  • 2
    $\begingroup$ Not a real answer, but a possibility to explore: since the product is a product of step functions, the integral can be rewritten as a sum: $\frac1{n!}\sum_{j=0}^{n!-1} \left(\prod_{k=2}^{n}\lfloor\frac{kj}{n!}\rfloor\right)$ $\endgroup$ Jun 18, 2014 at 5:22
  • 1
    $\begingroup$ Note we can lop off the interval [0,1/2] because it is the 0 function on that interval. $\endgroup$ Jun 21, 2014 at 3:49
  • 1
    $\begingroup$ $\lfloor kx \rfloor \approx kx$ so your integrand is basically $ \int dx \; n! x^{n-1} = (n-1)!$. Is there a reason this approximation is not enough? $$ . $$ The Farey Fractions should be helpful since you need rational nubmers with denominator up to $n$. $\endgroup$
    – cactus314
    Jun 21, 2014 at 12:16
  • 1
    $\begingroup$ Numerically, with $n$ upto $500$, the leading asymptotic behavior of the integral seems to be $$\mathcal{I}_n = \int_0^1 \prod_{k=2}^n\lfloor k x \rfloor dx \sim \frac{(n-1)!}{\alpha n+ O(1)}$$ where $\alpha \sim 0.44$ and the $O(1)$ term may be converging to some number around $0.94$. $\endgroup$ Jun 27, 2014 at 11:15
  • 1
    $\begingroup$ With data for $n$ upto 10000, the improved estimate is $$\mathcal{I}_n \sim \frac{(n-1)!}{\alpha n + \beta + O\left(\frac{0.3}{n}\right)}$$ where $\alpha \approx 0.43964235(2)$ and $\beta \approx 0.9349(3\!\!-\!\!6)$. I'm now pretty sure the leading dependence of the denominator in linear in $n$ but I'm clueless how to estimate $\alpha$ analytically (apart from it should be a number $\approx 0.5$). $\endgroup$ Jun 28, 2014 at 8:27

4 Answers 4

20
+100
$\begingroup$

This is not an answer but a note how to evaluate the integral for larger $n$.

Part I - the formula

For any integer $k$ such that $2 \le k \le n$ and $x \in [0,1)$, we have following decomposition:

$$\lfloor k x \rfloor = \sum_{j=1}^{k-1} \theta\left(x - \frac{j}{k}\right) \quad\text{ where }\quad \theta(x) = \begin{cases}1,& x \ge 0\\0,& x < 0\end{cases} $$ Notice for any $x, y_1, y_2, \ldots, y_m \in \mathbb{R}$, we have $$\prod_{k=1}^m \theta(x - y_k) = \theta\left(x - \max_{1 \le k \le m}\{y_k\} \right)$$

This leads to

$$\begin{align} \int_0^1 \prod_{k=2}^n \lfloor kx\rfloor dx &= \sum_{j_2 = 1}^{1}\sum_{j_3 = 1}^{2}\cdots\sum_{j_n=1}^{n-1} \int_0^1 \prod_{k=2}^n \theta\left(x - \frac{j_k}{k}\right) dx\\ &= \sum_{j_2 = 1}^{1}\sum_{j_3 = 1}^{2}\cdots\sum_{j_n=1}^{n-1} \int_0^1 \theta\left(x - \max_{2\le k \le n}\left\{\frac{j_k}{k}\right\}\right) dx\\ &= \sum_{j_2 = 1}^{1}\sum_{j_3 = 1}^{2}\cdots\sum_{j_n=1}^{n-1} \left(1 - \max_{2 \le k \le n}\left\{\frac{j_k}{k}\right\}\right)\\ &= \sum_{j_2 = 1}^{1}\sum_{j_3 = 1}^{2}\cdots\sum_{j_n=1}^{n-1} \min_{2\le k \le n}\left\{\frac{j_k}{k}\right\} \end{align} $$ There are totally $(n-1)!$ terms in above sum. We will calculate the sum as if it is a problem of taking expectation values.

$$ \int_0^1 \prod_{k=2}^n \lfloor kx\rfloor dx = (n-1)! \;\mathbf{E}(X) = (n-1)!\;\mathbf{E}\left( \min_{2\le k \le n}\left\{X_k\right\}\right)\tag{*1}$$ where $X = \min\limits_{2 \le k \le n} \left\{ X_k \right\}$ and $X_k, k = 2,\ldots, n$ are uniform discrete random variables: $$X_k \in \left\{\; \frac1k, \frac2k, \ldots \frac{k-1}{k} \;\right\} \text{ each with probability } \frac{1}{k-1}. $$

There are $1 + 2 + \cdots + n-1 = \frac{n(n-1)}{2}$ combinations of $\frac{j}{k}$. Some of these fractions share same numerical value. For simplicity of presentation, we will treat fractions with same numerical value as distinct numbers separated by an infinitesimal amount.

Let us sort them into ascending order. We will collect those with value $\le \frac12$ and label them as

$$\frac{1}{n} = \frac{p_1}{q_1} \le \frac{p_2}{q_2} \le \cdots \le \frac{p_\ell}{q_\ell} = \frac{1}{2}.$$

We can then evaluate $\mathbf{E}(x)$ by systematically break it down into conditional expectation values. More precisely, let $R_k$ and $S_k, k = 1, \ldots, \ell$ be the events:

$$R_k = \mathbf{Event}\left( X = \frac{p_k}{q_k} \right)\quad\text{ and }\quad S_k = \mathbf{Event}\left( X \ge \frac{p_k}{q_k}\right)$$

We have $$ \begin{align} \mathbf{E}(X) = \mathbf{E}(X \mid S_1) &= \mathbf{P}(R_1 \mid S_1) \frac{p_1}{q_1} + \mathbf{P}( S_2 \mid S_1 )\mathbf{E}( X \mid S_2 )\\ &= \frac{1}{q_1 - p_1} \frac{p_1}{q_1} + \left(1 - \frac{1}{q_1-p_1}\right)\mathbf{E}(X \mid S_2)\\ \mathbf{E}(X \mid S_2) &= \mathbf{P}(R_2 \mid S_2) \frac{p_2}{q_2} + \mathbf{P}( S_3 \mid S_2 )\mathbf{E}( X \mid S_3 )\\ &= \frac{1}{q_2 - p_2} \frac{p_2}{q_2} + \left(1 - \frac{1}{q_2-p_2}\right)\mathbf{E}(X \mid S_3)\\ &\;\vdots\\ \mathbf{E}(X \mid S_k) &= \mathbf{P}(R_k \mid S_k) \frac{p_k}{q_k} + \mathbf{P}( S_{k+1} \mid S_k )\mathbf{E}( X \mid S_{k+1} )\\ &= \frac{1}{q_k - p_k} \frac{p_k}{q_k} + \left(1 - \frac{1}{q_k-p_k}\right)\mathbf{E}(X \mid S_{k+1})\\ &\;\vdots\\ \mathbf{E}( X \mid S_\ell ) &= \frac12 \end{align} $$

Combine these, we convert $\mathbf{E}(X)$ and hence the original integral into a sum: $$ \bbox[8pt,border:1px solid blue]{ \mathbf{E}(X) = \sum_{k=1}^\ell \frac{1}{q_k-p_k}\frac{p_k}{q_k} \prod_{j=1}^{k-1}\left(1 - \frac{1}{q_j-p_j}\right) } \tag{*2}$$

Part II - the algorithm/implementation

There are many ways to evaluate the sum in $(*2)$. All takes $O(\ell\log\ell) = O(n^2\log n)$ steps to prepare the sorted list of fractions $\frac{p_k}{q_k}$ and take another $O(n^2)$ steps to compute the sum. To reduce round off error, it will be better to evaluate the sum in reverse order of $k$. More precisely, set $a_{\ell+1} = 0$ and recursively compute $a_\ell, a_{\ell-1}, \ldots, a_1$ by the recurrence relation:

$$a_k = \left(1-\frac{1}{q_k-p_k}\right) a_{k+1} + \frac{1}{q_k-p_k}\frac{p_k}{q_k}.\tag{*3} $$ At the end, $a_1$ will be the sum we need.

For small to medium $n \sim 5\times 10^3$, we can simply compute the $\ell$ fractions $\frac{p_k}{q_k}$, use $O(n^2)$ storage to store them and everything work. On an ordinary PC, this storage consumption becomes the first bottle neck for $n \sim O(10^4)$.

If one look back at the recurrence relation/procedure $(*3)$, one really don't need to know all $\frac{p_k}{q_k}$ all the time. Instead, what one need is the largest fraction $\frac{p}{q}$ among what is left to process. At any moment, there are at most $n$ candidates for the largest remaining fraction.

We can use the data structure heap to hold the $\le n$ potential candidates for the largest remain fraction. This reduces the storage requirement from $O(n^2)$ to $O(n)$ and allow us to extend the computation to $n \sim 5 \times 10^4$.

In case anyone is interested, following is a piece of pseudo code computing the sum in $(*2)$.

function calculate_sum( N ){
    heap = Heap->new( order => '>' );
    for( i = 2; 2 <= N; i++ ){
        heap->insert( Fraction->new( p => floor(i/2), q => i ) );
    }
    sum = 0;
    // heap->extract return the largest element on heap
    while( fraction = heap->extract ){ 
       p = fraction->p;
       q = fraction->q;
       f = 1/(q - p);
       sum = (1 - f)*sum + f*(p/q);
       if( p > 1 ){
           heap->insert( Fraction->new( p => p-1, q => q );
       }
    }
    return sum;
}

Part III - the numerical results

Following are some numerical results.

Instead of $\mathbf{E}(X)$, I find it more convenient to study its reciprocal $\displaystyle\;\eta_n = \frac{1}{\mathbf{E}(X)}\;$. It seems the leading dependence of $\eta_n$ on $n$ is linear.

In following table, $\alpha_n$ is an estimate of the slope of $\eta_n$ vs. $n$. $\beta_n$ is the corresponding constant offset. They are estimation based on the formulas: $$\alpha_n = \frac{\eta_n - \eta_{n-100}}{100}\quad\text{ and }\quad \beta_n = \eta_n - \alpha_n n$$

$$\begin{array}{|r:rrr:r|} \hline n & \eta_n & \alpha_n & \beta_n & \delta_n^{(eye)}\\ \hline 1000 & 440.57849249 & 0.439642912524 & 0.935579966035 & 0.306940385013\\ 2000 & 880.22159103 & 0.439643171269 & 0.935248489314 & 0.306956239421\\ 3000 & 1319.86479184 & 0.439643216555 & 0.935142177807 & 0.306876766506\\ 4000 & 1759.50801827 & 0.439643232266 & 0.935089199737 & 0.306860089425\\ 5000 & 2199.15125496 & 0.439643239853 & 0.935055695099 & 0.307048190306\\ 6000 & 2638.79449669 & 0.439643242826 & 0.935039733871 & 0.306851355739\\ 7000 & 3078.43774142 & 0.439643245039 & 0.935026141386 & 0.307066132100\\ 8000 & 3518.08098802 & 0.439643247922 & 0.935004641647 & 0.307743460185\\ 9000 & 3957.72423577 & 0.439643249057 & 0.934994257881 & 0.308001451641\\ 10000 & 4397.36748444 & 0.439643249954 & 0.934984897053 & 0.308851123061\\ \hline \end{array}$$

As one can see, both $\alpha_n$ and $\beta_n$ seems to converge quickly.

A vanilla linear regression using the data-set $\{\; \eta_{100k} : k = 1,\ldots,100 \;\}$ gives us

$$\eta_n \approx \alpha^{(reg)} n + \beta^{(reg)} = 0.43964319256906 n + 0.93539254734969$$

Compare with above estimation, we find a vanilla/barebone regression give us an estimation for slope $\alpha$ and offset $\beta$ accurate to about 6 and 3 decimal places respectively.

To obtain a better estimate, we vary the parameter $(\alpha,\beta)$ away a little bit from $(\alpha^{(reg)}, \beta^{(reg)})$ by hand. Instead of minimizing any sort of square error, we attempt to pick an $(\alpha, \beta)$ to make following expression

$$\delta_n = n ( \eta_n - \alpha n - \beta )$$ qualitatively as simple as possible. Based on my own subjective judgement, following formula $$\eta_n \approx \alpha^{(eye)} n + \beta^{(eye)} = 0.439643252 n + 0.93493355$$ produces a reasonable flat value of $\delta_n$.

During this process of subjective estimation, I haven't consulted the slope and offset computed in above table. It is interesting to see I get an $\alpha^{(eye)}$ and $\beta^{(eye)}$ which matches the corresponding values in last column of above table. This suggests the values of $\alpha^{(eye)}$ and $\beta^{(eye)}$ are accurate up to $8$ and $4$ decimal places respectively.

The last column in above table shows the values of $\delta_n$ computed using $\alpha^{(eye)}$ and $\beta^{(eye)}$. As one can see, the $3^{th}$ decimal places of $\delta_n$ are sort of random. This indicate for this part of calculation, we are hitting artifacts caused by the round off errors using standard IEEE double precision numbers.

Despite this drag back, one find all these $\delta_n$ are very close to the number $0.31$. Based on this, it is reasonable to conjecture the leading behavior of the integral is given by $$ \bbox[8pt,border:1px solid blue]{ \int_0^1 \prod_{k=2}^n\lfloor k x \rfloor dx \sim \frac{(n-1)!}{\alpha n + \beta + O\left(\frac{0.3}{n}\right)} \quad\text{ with }\quad \begin{cases} \alpha &\approx 0.43964325(2)\\ \\ \beta &\approx 0.9349(3355). \end{cases} } $$

At the end are two figures which hopefully illustrate the situation.

  1. The first figure is a plot of $\eta_n$ vs. $n$.
    As one can see, $\color{blue}{\eta_n}$ lies right on top of the straight line $\color{red}{\eta = \alpha^{(eye)} n + \beta^{(eye)}}$.

  2. The second figure is a plot of $\delta_n$ vs. $n$.

    • At $n \sim 10^3$, $\delta_n$ start to stabilize at a value $\approx 0.307$.
    • At $n \sim 5 \times 10^3$, $\delta_n$ start to pickup artifacts due to round off error.

    Despite these artifacts, $\delta_n$ remains very close to $0.307$ over the whole data range studied.

$\hspace0.6in$ Eta vs N

$\hspace0.4in$ Delta vs N

Part IV - ???

$\endgroup$
2
  • $\begingroup$ @Edwin Wow, thanks for the big bonus. $\endgroup$ Jul 6, 2014 at 18:55
  • 1
    $\begingroup$ You are welcome, you clearly deserve it. I am really impressed by your answer. $\endgroup$
    – user146010
    Jul 7, 2014 at 10:57
0
$\begingroup$

This is not an answer, but too long for a comment. Here is the result of a numerical experiment done with Maple: $$seq(int(mul(floor(k*x), k = 2 .. n), x = 0 .. 1), n = 2 .. 15) $$ outputs $$1/2,5/6, 13/6, 15/2, 166/5, 888/5, 5617/5, 57339/7, 473958/7, 48185388/77,$$ $$ 493082052/77, 10264563168/143, 125213779200/143, 1651372471104/143.$$ Then $$plots:-pointplot([seq([n, evalf(ln(int(mul(floor(k*x), k = 2 .. n), x = 0 .. 1)))],$$ $$ n = 2 .. 15)], color = red, symbolsize = 15) $$ enter image description here In my opinion, the plot is close to a straight line. Therefore, this suggests the asymptotic dependence of the form $A+B\exp(k)$

$\endgroup$
0
$\begingroup$

A partial answer and insight to the nature of the integral.

Let $$I=\int^1_0dx\prod^n_{k=2}\lfloor kx\rfloor $$

Make the substitution $u=1/x$ therefore $dx=-1/u^2du$ and the integral becomes

$$I=\int^\infty_1du\frac1{u^2}\left[\prod^n_{k=2}\lfloor k/u\rfloor\right]$$

Then integrate by parts you will see it evaluates to (integrand obtained by considering derivatives of products).

$$I=n!+\int^\infty_1\frac1u\left[\sum^n_{j=2}\prod^n_{\substack{i=2\\i\ne j}}\lfloor i/u\rfloor\right]du$$

Then by manipulation we get

$$I=n!+\sum_{j=2}^n\int^\infty_1du\frac{1}{u\lfloor j/u\rfloor}\prod^n_{i=2}\lfloor i/u\rfloor$$

Now focus on the other integral. Let

$$I_2=\int^\infty_1du\frac1{u\lfloor j/u\rfloor}\prod^n_{i=2}\lfloor i/u\rfloor$$

Now let $x=1/u$ again then $du=-dx/x^2$ and $$I_2=\int_0^1dx\frac1{x\lfloor jx \rfloor}\prod^n_{i=2}\lfloor ix\rfloor$$ I tried to manipulate this further however that factor will not go away.

So now I am going to look at the asymptotics of the integral. Clearly $I(n)\in\omega(n!)$. The summation term may give us a more precise approximation however. Through inspection it can be seen that $\sum I_2(n)\in O(n!)$. Therefore $I(n)$ can be thought of as $I(n)\in\Theta(n!)$. For approximation low values of $n$ can be though of as $I(n)\approx\frac23(n-2)!$. This can easily be made more accurate.

I would be surprised if a closed form for this integral exists. You should also note that I tried Riemann sums however they end up being messy and difficult to manipulate.

$\endgroup$
0
$\begingroup$

In the following paragraph, the letter k has a different connotation than it does in the question.

Let $F_n$ be the Farey sequence of n. It always has $2k+1$ elements for $n\ge2$ $($which is clearly the case here$)$, and its middle element is always $\dfrac12$, the first and last being $0$ and $1$ respectively. Now, we are interested in the sub-sequence starting at $F_n(k+1)=\dfrac12$ and ending at $F_n(2k+1)=1.~$ $($The number of terms in each Farey sequence can be found here$)$. Now, the product vanishes on $\Big(0,\frac12\Big)$, so the integral can be written as $\displaystyle\sum_{j=1}^kC_j\bigg[F_n(k+j+1)-F_n(k+j)\bigg]$, since the product is a constant on each such sub-interval, whose two extremities are consecutive Farey numbers, the value of each such constant being $C_j=\displaystyle\prod_{i=2}^n\Big\lfloor i\cdot F_n(k+j)\Big\rfloor$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.