Euler Project, Problem 401 is a number theory question. It asks the reader to calculate the sum \[ \sum_{m=1}^n\sum_{q\|m} q^2 \] modulo \(10^9\) for \(n=10^{15}\). In a previous post, I rewrote the sum in a diffent way as \[ \sum_{q=1}^n q^2\left\lfloor\frac{n}{q}\right\rfloor \] But even with the reduction, the calculation was out of reach under the 1 minute mark of a generic Project Euler problem.
Let me recall the theoretical reduction phase: \[ \Upsilon(n,s) = \sum_{m=1}^n \sum_{q\|m} q^s \] I will define the following auxiliary function \[ \nu(q,n) = \begin{cases} 1 & \text{ if } q\|n\\ 0 & \text{ otherwise} \end{cases} \] Then I can rewrite \(\Upsilon(n,s)\) as follows: \[ \Upsilon(n,s) = \sum_{m=1}^n\sum_{q=1}^m \nu(q,m) q^s \] Now we can switch the summations \[ \Upsilon(n,s) = \sum_{q=1}^n \sum_{m=a}^n \nu(q,m) q^s = \sum_{q=1}^n q^s \left(\sum_{m=a}^n \nu(q,m)\right) \] Notice that, the inner sum terms are \(m=q,q+1,\ldots,n\) but the function we sum is non-zero only if \(m\) is a multiple of \(q\). This means the sum \(\sum_{m=q}^n \nu(q,m) = \left\lfloor\frac{n}{q}\right\rfloor\). Therefore, \[ \Upsilon(n,s) = \sum_{q=1}^n q^s \left\lfloor\frac{n}{q}\right\rfloor \] Take \(m\) such that \(m\|n\) and split the sum as \[ \Upsilon(n,s) = \sum_{q=1}^{m-1} q^s \left\lfloor\frac{n}{q}\right\rfloor + \sum_{q=m}^n q^s\left\lfloor\frac{n}{q}\right\rfloor = \sum_{q=1}^{m-1} q^s \left\lfloor\frac{n}{q}\right\rfloor + \sum_{k=1}^{n/m} k\ \sum_{\lfloor n/q\rfloor = k} q^s \] But this can also be written as \[ \Upsilon(n,s) = \sum_{q=1}^{m-1} q^s \left\lfloor\frac{n}{q}\right\rfloor + \sum_{\lfloor n/q \rfloor=1}^{\lfloor n/(m-1)\rfloor-1} q^s + \sum_{\lfloor n/q \rfloor=2}^{\lfloor n/(m-1)\rfloor-1} q^s + \cdots + \sum_{\lfloor n/q \rfloor=n/m}^{\lfloor n/(m-1)\rfloor-1} q^s \] Now, we observe that \[ \left\lfloor\frac{n}{q}\right\rfloor\geq k \quad\text{ whenever }\quad q\leq \left\lfloor\frac{n}{k}\right\rfloor \] This means \[ \Upsilon(n,s) = \sum_{q=1}^{m-1} q^s \left\lfloor\frac{n}{q}\right\rfloor + \sum_{k=1}^{n/m} \sum_{q=1}^{\lfloor n/k\rfloor} q^s - \frac{n}{m}\sum_{q=1}^{\left\lfloor\frac{n}{\lfloor n/(m-1)\rfloor}\right\rfloor}q^s \] For example when \(n=6\) and \(m=3\) the original summation was \[ \sum_{q=1}^6 q^s \left\lfloor\frac{6}{q}\right\rfloor = 6\cdot 1^s + 3 \cdot 2^s + 2\cdot 3^s + 1\cdot 4^s + 1\cdot 5^s + 1\cdot 6^s \] Our reduction indicates the sum above equals to \[ 6\cdot 1^s + 3\cdot 2^s + (1^s + \cdots + 6^s) + (1^s + 2^s + 3^s) - 2(1^s + 2^s) \] which they are.
I already implemented the first part of the summation for \(s=2\):
(defun upsilon1 (n &optional (m (1- (truncate (sqrt n)))))
(let ((res 0))
(do ((q 1 (1+ q)))
((> q m) res)
(incf res (* q q (truncate n q))))))As for the second part:
(defun upsilon2 (n &optional (m (truncate (sqrt n))))
(labels ((sq (n) (* n (1+ n) (1+ (+ n n)) (/ 6))))
(let* ((a (truncate (/ n m)))
(res (- (* a (sq (truncate (/ n (truncate (/ n (1- m))))))))))
(do* ((k 1 (1+ k)))
((> k a) res)
(incf res (sq (truncate (/ n k))))))))I will not post the answer here. Plus, the lisp implementation I used took about 2 minutes to calculate the result which is twice as long as a generic Euler Project question should take.