We have a function \(f\colon\mathbb{Z}\to \mathbb{Z}\) defined recursively as \[ f(n) = \begin{cases} 0 & \text{ if } n < 1\\ 1 & \text{ if } n=1\\ f(n/2) & \text{ if $n$ is even }\\ 2 f((n+1)/2) - f((n-1)/4) & \text{ if } n\equiv 1 \text{ mod } 4\\ 3 f((n-1)/2) - 2 f((n-3)/4) & \text{ if } n\equiv 3 \text{ mod } 4 \end{cases} \] and we want to calculate \(\sum_{n=1}^{3^{27}} f(n)\).
First let us find a recurrence relation for the summation. Let \(S(n) = \sum_i^n f(i)\). Notice that \[ f(4n+3) - f(4n+2) = f(4n+3) - f(2n+1) = 2 f(2n+1) - 2 f(n) \] for \(n\geq 0\) and \[ f(4n+2) - f(4n+1) = - f(2n+1) + f(n) \] for \(n\>0\), and finally \[ f(4n+1) - f(4n) = 2 f(2n+1) - 2 f(n) \] for \(n\>0\). Then we get \[ f(4n+3) + f(4n+2) + f(4n+1) + f(4n) = 6 f(2n+1) - 2 f(n) \] which can be written as \[ f(4n+3) + f(4n+2) + f(4n+1) + f(4n) = 6 f(2n+1) + 6 f(2n) - 8 f(n) \] By induction/recursion we get a recurrence relation for \(S(n)\) as \[ S(4n+3) = 6 S(2n+1) - 8 S(n) -1 \] The last –1 comes as a correction from the fact that one recurrence relation for \(f(n)\) works for \(n\geq 0\) while the other two work for \(n \> 0\).
First, I will code the function \(f\). I used memoization to cut down the computation time which is not shown here.
(defun fn (n)
(cond ((< n 1) 0)
((= n 3) 3)
((= n 2) 1)
((= n 1) 1)
((evenp n) (fn (/ n 2)))
((= (rem n 4) 3) (- (* 3 (fn (/ (1- n) 2))) (* 2 (fn (/ (- n 3) 4)))))
(t (- (* 2 (fn (/ (1+ n) 2))) (fn (/ (1- n) 4))))))And next the summation function. Again I used memoization which isn’t shown here.
(defun S (n)
(cond ((< n 1) 0)
((= n 3) 5)
((= n 2) 2)
((= n 1) 1)
((= (rem n 4) 3) (+ (- 1) (* 6 (S (/ (1- n) 2))) (* (- 8) (S (/ (- n 3) 4)))))
((= (rem n 4) 2) (+ (fn (/ n 2)) (S (1- n))))
((= (rem n 4) 1) (+ (fn n) (fn (/ (1- n) 2)) (S (- n 2))))
(t (+ (fn (/ n 4)) (S (1- n))))))I am not going to show the result, but it took less than a second to calculate \(S(3^{37})\).