← Complete problem index

PROJECT EULER · #0756

Approximating a Sum

Statement only · UnsolvedOriginal problem ↗

Consider a function f(k) defined for all positive integers k>0. Let S be the sum of the first n values of f. That is, S=f(1)+f(2)+f(3)+⋯+f(n)=∑k=1nf(k).

In this problem, we employ randomness to approximate this sum. That is, we choose a random, uniformly distributed, m-tuple of positive integers (X1,X2,X3,⋯,Xm) such that 0=X0<X1<X2<⋯<Xm≤n and calculate a modified sum S∗ as follows. S∗=∑i=1mf(Xi)(Xi−Xi−1)

We now define the error of this approximation to be Δ=S−S∗.

Let E(Δ|f(k),n,m) be the expected value of the error given the function f(k), the number of terms n in the sum and the length of random sample m.

For example, E(Δ|k,100,50)=2525/1326≈1.904223 and E(Δ|φ(k),104,102)≈5842.849907, where φ(k) is Euler's totient function.

Find E(Δ|φ(k),12345678,12345) rounded to six places after the decimal point.

Write-up coming later

The complete problem is available here. An approach, code, and answer will be added later.