← 完整题目索引

PROJECT EULER · #0064

奇数周期平方根

Odd Period Square Roots

仅题目 · 已解决原题 ↗

当写成连分数时,所有平方根都是周期性的,并且可以写成以下形式:

N=a0+1a1+1a2+1a3+…

例如,让我们考虑 23:

23=4+23−4=4+1123−4=4+11+23−37

如果我们继续,我们将得到以下扩展:

23=4+11+13+11+18+…

该过程可概括如下:

a0=4,123−4=23+47=1+23−37a1=1,723−3=7(23+3)14=3+23−32a2=3,223−3=2(23+3)14=1+23−47a3=1,723−4=7(23+4)7=8+23−4a4=8,123−4=23+47=1+23−37a5=1,723−3=7(23+3)14=3+23−32a6=3,223−3=2(23+3)14=1+23−47a7=1,723−4=7(23+4)7=8+23−4

可以看出该序列是重复的。为了简洁起见,我们使用符号 23=[4;(1,3,1,8)] 来表示块 (1,3,1,8) 无限重复。

(无理)平方根的前十个连分数表示是:

2=[1;(2)],句点=1
3=[1;(1,2)],句点=2
5=[2;(4)],句点=1
6=[2;(2,4)],句点=2
7=[2;(1,1,1,4)],句点=4
8=[2;(1,4)],句点=2
10=[3;(6)],句点=1
11=[3;(3,6)],句点=2
12=[3;(2,6)],句点=2
13=[3;(1,1,1,1,6)],句点=5

正好有四个连分数,N≤13,有一个奇数周期。

N≤10000 有多少个连分数有奇数句点?

题解待补充

这道题的题目已收录,解题思路、代码和答案将在后续补充。