Sum of super exponentiation

Question

$f(x,n)=x^{2^{1}}+x^{2^{2}}+x^{2^{3}}+...+x^{2^{n}}$

Example: $f(2,10)$ mod $1000000007$ = $180974681$

Calculate $\sum_{x=2}^{10^{7}} f(x,10^{18})$ mod $1000000007$.

We know that $a^{b^{c}}$ mod $p$ = $a^{b^{c} \hspace{0.5 mm} mod \hspace{1 mm} (p-1)}$ mod $p$.

So I tried to find the period of the sequence $2^n$ mod $1000000006$.

$\varphi(1000000006)=500000002$ is an integral multiple of this period. But I am stuck here. Any help please?

I verified that the period of the sequence $2^n$ mod $1000000006$ is indeed $500000002$.

Answer 1

Let $q=5000000003$ and $p=2q+1$

As $10^{18}=1999999992*(q-1)+16$, we have

$f(x,10^{18})=1999999992*(x^2+x^4+...+x^{2(q-1)})+(x^{2^{1}}+x^{2^{2}}+...+x^{2^{16}})$

Now we can use the fact that $2$ is a primitive root modulo $q$

$x^2+x^4+...+x^{2(q-1)}=x^2 \frac{x^{2(q-1)}-1}{x^2-1}\equiv -1$ mod $p$.

So we just have to compute $16*10^7$ values.

Answer 2

Hint: $1000000006=2\cdot500000003$. The smallest number $n$ such that $$2^n \equiv 1 \mod k$$

If $\gcd(n,k)=1$, is equal to $\lambda(k)$, the Carmichael function. For prime $p$, we have $\lambda(p)=\varphi(p)$. So

$$2^{500000002} \equiv 1 \mod 500000003$$

And $500000002$ is the smallest such number.

Alternatively, $ 500000002$ has only 4 prime factors, (2, 41, 41, 148721) so you can test all divisiors.

Answer 3

Partial answer: You are looking for (the remainder $\mod p$ of) $$ \sum_{x=2}^{A}f(x,B)=\sum_{x=2}^{A}\sum_{y=1}^Bx^{2^y}=\sum_{y=1}^B\sum_{x=2}^{A}x^{2^y}.$$ Since $p\equiv 3\pmod 4$, squaring is a bijection $\mod p$. We conclude by induction on $y$ that $$\sum_{x=k+1}^{k+p}x^{2^y}\equiv \sum_{x=k+1}^{k+p}x\equiv 0\pmod p. $$ Hence $$ \sum_{x=2}^{A}x^{2^y}\equiv \sum_{x=2}^{A\bmod p}x^{2^y}= \sum_{x=2}^{49}x^{2^y}$$ and you are in fact looking for $$\sum_{x=2}^{49}f(x,B).$$