# How to effectively compute a periodic function?

I'm writing a program to compute a value of periodic function for any arbitrary large argument:

$f(k) = (\sum_{n=1}^{2^k} n)\mod\ (10^9 + 7)$, where $n,k \in \mathbb{N}$

I know that $f(k + P) = f(k)$, which limits the value of $k$ I would have to compute.

What confuses me is that Wolfram Alpha says that it have a period of $\frac {2{i}\pi}{\log(2)}$. Is it even possible to program that period?

-
$f$ is a function of an integer argument and it has an integer period. It sounds like you didn't tell WolframAlpha about the $10^9 + 7$ part. – Qiaochu Yuan May 4 '12 at 18:15
Here is the link goo.gl/1KkQT – Andrew May 4 '12 at 18:17
I don't think WolframAlpha is interpreting "mod" correctly. It is far from infallible. – Qiaochu Yuan May 4 '12 at 18:23
Yes, but it is certainly aware of what "mod" is goo.gl/PGfSS – Andrew May 4 '12 at 18:29
What are you really trying to do? Not (pseudo) random number generation, by any chance? – bgins May 4 '12 at 18:51

Since your function is actually $f(k) = (2^{2k-1} + 2^{k-1})\pmod{10^9+7}$, it suffices to tabulate values of $2^k$.

$10^9+7$ is prime, so by Fermat's theorem, we know that $2^{10^9+6}\equiv 1\pmod{10^9+7}$.

So suppose you want to calculate $f(k)$. Calculating powers is expensive, so we will calculate $z=2^{k-1}\pmod{10^9+7}$ and then $f(k) = z\cdot(2z+1) \pmod{10^9+7}$.

First calculate $k' = k-1\pmod{10^9+6}$. Then calculate $2^{k-1} \equiv 2^{k'}\pmod{10^9+7}$ using the usual fast recursive exponentiation algorithm:

pow2(k):
result = 1
power = 1
while k > 0:
power = (power * 2) mod 1000000007
if k is odd, result = (result * power) mod 1000000007
k = int(k/2)
return result


(In C, use k >>= 1 instead of k=int(k/2), power <<= 1, etc.)

We have $k < 10^9 + 7$, so this will iterate at most about 30 times. If this is too slow, you can cache the results for $0 ≤ k ≤ 10^6$ and then it will iterate at most ten times per call.

Let $z = \mathrm{pow2}(k-1\pmod{10^9+6})$, and then your answer is $(2z+1)\cdot z\pmod{(10^9+6}$.

Wolfram|Alpha appears to have gone temporarily insane.

-