846. Magic Bracelets

A bracelet is made by connecting at least three numbered beads in a circle. Each bead can only display $1$$1$, $2$$2$, or any number of the form $p^k$$p^k$ or $2p^k$$2p^k$ for odd prime $p$$p$.

In addition a magic bracelet must satisfy the following two conditions:

• no two beads display the same number

• the product of the numbers of any two adjacent beads is of the form $x^2+1$$x^2+1$.

Define the potency of a magic bracelet to be the sum of numbers on its beads. The example is a magic bracelet with five beads which has a potency of 155.

Let $F(N)$$F(N)$ be the sum of the potency of each magic bracelet which can be formed using positive integers not exceeding $N$$N$, where rotations and reflections of an arrangement are considered equivalent. You are given $F(20)=258$$F(20)=258$ and $F({10}^2)=538768$$F(10^2)=538768$.

Find $F({10}^6)$$F(10^6)$.

846. 魔法数镯

一个数镯由至少三个标有数字的珠子和连接它们的环构成。数镯上的珠子的标号只能是 $1$$1$、$2$$2$、$p^k$$p^k$、$2p^k$$2p^k$ 四种形式之一（其中 $p$$p$ 为任意奇质数，$k$$k$ 为任意正整数）。

进一步，定义魔法数镯为满足以下条件的数镯：

• 数镯上的珠子的标号两两不同。

• 任意两个相邻珠子上的标号之积均可被表示为 $x^2+1$$x^2 + 1$ 的形式（其中 $x$$x$ 为整数）。

对任意魔法数镯，定义其魔法效力为其所有珠子标号之和。上图中的魔法数镯共有 5 个珠子，魔法效力为 155。

记 $F(N)$$F(N)$ 为：满足所有珠子标号均为不超过 $N$$N$ 的正整数的魔法数镯的魔法效力之和，其中，经旋转或翻转后相同的数镯视为相同的数镯。已知：$F(20)=258$$F(20) = 258$、$F({10}^2)=538768$$F(10^2) = 538768$。

求 $F({10}^6)$$F(10^6)$。

点 这个链接 回到源站。

点 这个链接 回到详细版题目目录。