两个平方和：我的错误在哪里？

Question

我正在尝试计算将自然数写成两个平方和的方法数。我在 definition:

工作

所以，这是我的代码。在我测试它的地方下面，我发现我认为是结果中的错误。

sumOfSquares :: Integer -> Int
sumOfSquares k = 4 * (d1 - d3)
  where
    divs = divisors k
    d1 = congruents d1_test divs
    d3 = congruents d3_test divs
    d1_test n = (n - 1) `mod` 4 == 0
    d3_test n = (n - 3) `mod` 4 == 0

congruents :: (Integer -> Bool) -> [Integer] -> Int
congruents f divs = length $ filter f divs

divisors :: Integer -> [Integer]
divisors k = divisors' 2 k
  where
    divisors' n k' | n*n > k' = [k']
                   | n*n == k' = [n, k']
                   | k' `mod` n == 0 = (n:(k' `div` n):result)
                   | otherwise = result
      where result = divisors' (n+1) k'

当我运行它时，它生成：

*Main Numbers.SumOfSquares> sumOfSquares 10
4

我计算出只有一种方法可以将 10 表示为两个平方和 1^2 + 3^2。请注意，中间结果 (d1 - d3) 等于 1.

我遗漏了一些重要的东西，但不知道是什么。

Answer 1

我认为您误读了公式的语义。 Wikipedia article 表示以下等式：

这里有两个重要的说明：

域是Z，不是N，所以(-1),(-3),0等也是正方形的有效元素；和
我们计算元组的数量，而不是组，所以顺序很重要（并且 (1,2,2) 不等于 (1,2))：如果 (1,3) 是一个解，那么 (3,1) 也是一个解，我们将它们算作两个独立的解。

现在 10 有以下约数：1、2、5、10（您的程序忘记了 1 和 10）。两个与 1 模 4 全等：1 和 5。此外，没有与 3 模 4 全等的除数。所以 d1 = 2 和 d3 = 0。因此有八（4×（2-0）= 8）种可能性：

(1,3): 1²+3²=10
(3,1): 3²+1²=10
(1,-3): 1²+(-3)²=10
(3,-1): 3²+(-1)²=10
(-1,3): (-1)²+3²=10
(-3,1): (-3)²+1²=10
(-1,-3): (-1)²+(-3)²=10
(-3,-1): (-3)²+(-1)²=10

现在我们只需解决您的程序问题即可。您只需要从 1 而不是 2:

开始计数

divisors :: Integer -> [Integer]
divisors k = divisors' <b>1</b>
  where
    divisors' i | i2 > k = <b>[]</b>
                | i2 == k = <b>[i]</b>
                | k `mod` i == 0 = (i:(k `div` i):result)
                | otherwise = result
      where i2 = i*i
            result = divisors' (i+1)

我还稍微简化了程序并解决了其他一些语义错误。现在它至少应该与 r_k(n).

两个平方和：我的错误在哪里？

Sum Of Two Squares: Where's My Error?

algorithm

haskell

number-theory