886. Coprime Permutations

A permutation of $\{2,3,\dots ,n\}$$\{2,3,\ldots,n\}$ is a rearrangement of these numbers. A coprime permutation is a rearrangement such that all pairs of adjacent numbers are coprime.

Let $P(n)$$P(n)$ be the number of coprime permutations of $\{2,3,\dots ,n\}$$\{2,3,\ldots,n\}$.

For example, $P(4)=2$$P(4)=2$ as there are two coprime permutations, $(2,3,4)$$(2,3,4)$ and $(4,3,2)$$(4,3,2)$. You are also given $P(10)=576$$P(10)=576$.

Find $P(34)$$P(34)$ and give your answer modulo $83456729$$83\,456\,729$.

886. 互质排列

将 $\{2,3,\dots ,n\}$$\{2,3,\ldots,n\}$ 重新排列得到的数列称为该集合的一个排列。如果该排列满足：任意两个相邻的元素互质，则称该排列是一个 互质排列。

记 $P(n)$$P(n)$ 为 $\{2,3,\dots ,n\}$$\{2,3,\ldots,n\}$ 的互质排列的数量。已知 $P(4)=2$$P(4)=2$，因为只有 $(2,3,4)$$(2,3,4)$、$(4,3,2)$$(4,3,2)$ 这两个互质排列。你还知道 $P(10)=576$$P(10)=576$。

求 $P(34)$$P(34)$ 模 $83456729$$83\,456\,729$ 的值。

点 这个链接 回到源站。

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