Problem 927

Prime-ary Tree

A full $k$ -ary tree is a tree with a single root node, such that every node is either a leaf or has exactly $k$ ordered children. The height of a $k$ -ary tree is the number of edges in the longest path from the root to a leaf.

For instance, there is one full $3$ -ary tree of height $0$ , one full $3$ -ary tree of height $1$ , and seven full $3$ -ary trees of height $2$ . These seven are shown below.

For integers $n$ and $k$ with $n \geq 0$ and $k \geq 2$ , define $t_{k} (n)$ to be the number of full $k$ -ary trees of height $n$ or less.

Thus, $t_{3} (0) = 1$ , $t_{3} (1) = 2$ , and $t_{3} (2) = 9$ . Also, $t_{2} (0) = 1$ , $t_{2} (1) = 2$ , and $t_{2} (2) = 5$ .

Define $S_{k}$ to be the set of positive integers $m$ such that $m$ divides $t_{k} (n)$ for some integer $n \geq 0$ . For instance, the above values show that $1$ , $2$ , and $5$ are in $S_{2}$ and $1$ , $2$ , $3$ , and $9$ are in $S_{3}$ .

Let $S = ⋂_{p} S_{p}$ where the intersection is taken over all primes $p$ . Finally, define $R (N)$ to be the sum of all elements of $S$ not exceeding $N$ . You are given that $R (20) = 18$ and $R (1000) = 2089$ .

Find $R (10^{7})$ .

素数多叉树

一个完满 $k$ 叉树是一棵具有单一根结点的树，其中每个结点要么是叶结点，要么恰好有 $k$ 个有序子结点。 $k$ 叉树的高度是从根结点到任一叶结点的最长路径上的边数。

例如，高度为 $0$ 的完满 $3$ 叉树有一棵，高度为 $1$ 的完满 $3$ 叉树有一棵，而高度为 $2$ 的完满 $3$ 叉树有七棵，如下图所示：

对于整数 $n \geq 0$ 和 $k \geq 2$ ，定义 $t_{k} (n)$ 为高度不超过 $n$ 的完满 $k$ 叉树的数量。

因此， $t_{3} (0) = 1$ ， $t_{3} (1) = 2$ ， $t_{3} (2) = 9$ 。同时， $t_{2} (0) = 1$ ， $t_{2} (1) = 2$ ， $t_{2} (2) = 5$ 。

定义 $S_{k}$ 为能整除任意整数 $n \geq 0$ 对应的 $t_{k} (n)$ 的正整数 $m$ 的集合。例如，从上面的例子可知， $1$ 、 $2$ 和 $5$ 属于 $S_{2}$ ，而 $1$ 、 $2$ 、 $3$ 和 $9$ 属于 $S_{3}$ 。

记 $S = ⋂_{p} S_{p}$ ，其中交集取遍所有素数 $p$ 。再定义 $R (N)$ 为 $S$ 中不超过 $N$ 的所有元素之和。已知 $R (20) = 18$ ， $R (1000) = 2089$ 。

求 $R (10^{7})$ 。

译注：原文的Full $k$ -ary Tree直译为“满 $k$ 叉树”；然而，在中文网络中，“满二叉树”的概念其实对应于英文中的Perfect Binary Tree，或“完美二叉树”。为示区别，这里参考网络资料将其翻译为“完满 $k$ 叉树”。