---

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\ge0$ such that for all $i\ge0$, $a_{i+1}=\min(a^e_i,n−a^e_i)$ 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}^NC(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\ge0$为$(n,e)$-MPS（镜像幂序列）：对于所有$i\ge0$，都有$a_{i+1}=\min(a^e_i,n−a^e_i)$以及 $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}^NC(n)$。

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

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

---