Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
$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
show 1 more comment

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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