---

Problem 617

---

Mirror Power Sequence

For two integers $n,e>1$, we define a $(n,e)$-MPS (Mirror Power Sequence) to be an infinite sequence of integers $(a_i{)}_i\ge 0$ such that for all $i\ge 0$, $a_{i+1}=min(a_i^e,n-a_i^e)$ and $a_i>1$.
Examples of such sequences are the two (18,2)-MPS sequences made of alternating 2 and 4.

Note that even though such a sequence is uniquely determined by $n,e$ and $a_0$, for most values such a sequence does not exist. For example, no $(n,e)$-MPS exists for $n<6$.

Define $C(n)$ to be the number of $(n,e)$-MPS for some $e$, and $D(N)=\sum _{n=2}^{N}C(n)$.

You are given that $D(10)=2$, $D(100)=21$, $D(1000)=69$, $D({10}^6)=1303$ and D$({10}^{12})=1014800$.

Find $D({10}^{18})$.

---

镜像幂序列

对于两个整数$n,e>1$，我们定义满足如下条件的无穷整数序列$(a_i{)}_i\ge 0$为$(n,e)$-MPS（镜像幂序列）：对于所有$i\ge 0$，都有$a_{i+1}=min(a_i^e,n-a_i^e)$以及 $a_i>1$。
这类序列的例子包括两个由交替的2和4构成的(18,2)-MPS。

注意到，尽管这样的序列总是被$n$，$e$和$a_0$唯一确定，但对于大多数的取值这样的序列并不存在。例如，不存在任何$n<6$的$(n,e)$-MPS。

记$C(n)$为$e$可以任意选择时所有$(n,e)$-MPS的数量，并记$D(N)=\sum _{n=2}^{N}C(n)$。

已知$D(10)=2$，$D(100)=21$，$D(1000)=69$，$D({10}^6)=1303$以及$D({10}^{12})=1014800$。

求$D({10}^{18})$。

---