java - 在涉及毕达哥拉斯三元组和集合的算法中找不到我的错误

Question

我试图找到答案“假设L是导线的长度，对于多少L≤1500000的值，可以形成一个整数边直角三角形？”，Project Euler #75。
我不是在要求正确的答案，也不是要找到它的密码我将解释我是如何试图解决这个问题的，请你指出我错在哪里。我试图用java和common lisp解决这个问题，但总是得到相同的错误答案。因此，我很确定我的算法或基本假设中有错误，但我找不到它。我对潜在错误点的猜测是：1）设置差异时出错；2）设置参数限制时出错。
下面是我遵循的算法：
生成所有毕达哥拉斯三倍周长，并将它们集合在一起
“A”（通用Lisp的列表，因此是时差）。这一套会
生成每一个周长，是否只有一个三角形
解决方案或多个。因为这是一套每一个周边都会
只代表一次。
在附加的集合中收集重复的周长
“B”这一套只包括周长超过
一个三角形解。
A-B应该给我一张有单个三角形的周长表
解决方案这可能是我错的地方。
我用我找到的公式生成了三重态，即周长。我更喜欢用附加系数“k”的公式，因为文章说，
尽管产生了所有的原始三元组，欧几里德公式并没有
生成所有三元组例如（9、12、15）不能使用
整数m和n。可以通过插入一个
公式的参数k。
为了在合理的时间内解决这个问题，我需要对嵌套循环中的参数进行合理的限制。我为“k”和“m”设置了限制，您将在后面的完整代码中看到，借助这两个小函数：

(defun m-limit (m)
  (if (> (make-peri m 1 1) 1500000)
      m
      (m-limit (1+ m))))

(defun k-limit (k)
  (if (> (make-peri 2 1 k) 1500000)
      k
      (k-limit (1+ k))))

要设置公式中“n”加上“a”、“b”和“c”的限制，请将其解为“n”（这可能是我犯错误的另一点）。
a=k*（m*m-n*n）
b=2*k*m*n；
c=k*（m*m+n*n）
k*（m^2-n^2+2mn+m^2+n^2）<=1500000
找到这个：

nLimit = 1500000 / (2 * k * m) - m;

下面是java和common lisp中的代码。请注意，虽然Java只需要2秒就可以使用HashSet，而Common-Lips在我的笔记本上只需要1889秒，很可能是因为检查新生成的外围是否已经是set“a”的成员。
Java代码：

package euler75v6;

import java.util.HashSet;

/**
 *
 * @author hoyortsetseg
 */
public class Euler75v6 {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        HashSet<Long> peris = new HashSet<>();
        HashSet<Long> duplicatePeris = new HashSet<>();
        peris = periList(865,125000, duplicatePeris);
        System.out.println("Number of all perimeters: " + peris.size());
        System.out.println("Number of duplicate perimeters: " + duplicatePeris.size());
        System.out.println("Number of all perimeters minus number "
                + "of duplicate perimeters: " + (peris.size() - duplicatePeris.size()));
        peris.removeAll(duplicatePeris);
        System.out.println("Same difference, just to confirm. After 'removeAll': " + peris.size());
    }
    private static Long makePeri (long m, long n, long k){
        //Long a, b, c, res;
        //a = k * (m * m - n * n);
        //b = 2 * k * m * n;
        //c = k * (m * m + n * n);
        return 2 * k * (m * m  + m * n);
    }

    private static HashSet<Long> periList (long x, long z, HashSet<Long> dupList){
            HashSet<Long> res = new HashSet<>();
            Long temp, nLimit;
            Long limit = Long.valueOf("1500000");
            for (long k = 1; k <= z; k++){
                for (long m = 2; m <= x; m++){
                    nLimit = 1500000 / (2 * k * m) - m;
                    for (long n = 1; ((n <= nLimit) && (n < m)); n++){
                        temp = makePeri(m,n,k);
                        if (Long.compare(temp, limit) <= 0){ // Should be redundant but just in case.
                            if (res.contains(temp)){
                                dupList.add(temp);
                            }
                            else {
                                res.add(temp);
                            }
                        }
                    }
                }
            }
            return res;
        }    
}

通用Lisp代码：

(defun make-peri (m n k)
  (* 2 k (+ (* m m) (* m n))))

(defun peri-list (m n k all-peris dupl-peris)
  (let ((n-limit (- (/ 1500000 (* 2 k m)) m)))
    (cond ((> k 125000) (- (length all-peris)
               (length (remove-duplicates dupl-peris))))
      ((> m 865) (peri-list 2 1 (1+ k) all-peris dupl-peris))
      ((or (>= n m) (> n n-limit))
       (peri-list (1+ m) 1 k all-peris dupl-peris))
      (t (let ((peri (make-peri m n k)))
           (if (> peri 1500000) ;; Redundant with m n k limits but still.
           (peri-list (1+ m) 1 k all-peris dupl-peris)
           (if (member peri all-peris)
               (peri-list m (1+ n) k all-peris (cons peri dupl-peris))
               (peri-list m (1+ n) k (cons peri all-peris)
                  dupl-peris))))))))

(defun result () (peri-list 2 1 1 nil nil))

任何关于我错在哪里的解释都将不胜感激。但请不要给出正确答案或密码。
编辑：
我对常用的lisp代码做了一个稍微修改的版本，以便查看收集的列表（集合）的外观，并希望看到哪里出错了。
我还添加了位来自动设置m n k变量的限制我还去掉了多余的“if”，它检查周长是否超过了极限，正如我所看到的，让m n和k在它们的极限内可以确保周长不超过自己的极限下面是经过这些修改后的代码的外观：

(defun make-peri (m n k)
  (* 2 k (+ (* m m) (* m n))))

(defun peri-list* (m n k limit all-peris dupl-peris)
  (let* ((n-limit (- (/ limit (* 2 k m)) m))
    (k-upper-limit (1- (k-limit 1 limit)))
    (m-upper-limit (1- (m-limit 2 limit)))
    (dupl-peris* (remove-duplicates dupl-peris))
    (difference* (set-difference all-peris dupl-peris*)))
    (cond ((> k k-upper-limit) (list (sort all-peris #'<)
                     (sort dupl-peris* #'<)
                     (sort difference* #'<)))
                    ;; (length all-peris)
                    ;; (length dupl-peris*)
                    ;; (length difference*)))
      ((> m m-upper-limit) (peri-list* 2 1 (1+ k) limit all-peris dupl-peris))
      ((or (>= n m) (> n n-limit))
       (peri-list* (1+ m) 1 k limit all-peris dupl-peris))
      (t (let ((peri (make-peri m n k)))
           (if (member peri all-peris)
           (peri-list* m (1+ n) k limit all-peris (cons peri dupl-peris))
           (peri-list* m (1+ n) k limit (cons peri all-peris) dupl-peris))))))))
(defun m-limit (m limit)
  (if (> (make-peri m 1 1) limit)
      m
      (m-limit (1+ m) limit)))

(defun k-limit (k limit)
  (if (> (make-peri 2 1 k) limit)
      k
      (k-limit (1+ k) limit)))

首先，我尝试了一个小限制，看看它如何表现。一开始我还没有把 (length...)部分注释掉。我看到一些我不明白的行为：

CL-USER> (peri-list* 2 1 1 150 nil nil)
((12 24 30 36 40 48 56 60 70 72 80 84 90 96 108 112 120 126 132 140 144 150)
 (24 48 60 72 80 84 90 96 108 112 120 132 140 144) (12 30 36 40 56 70 126 150)
 13 9 8)
CL-USER> (- 22 14)
8
CL-USER> (peri-list* 2 1 1 100 nil nil)
((12 24 30 36 40 48 56 60 70 72 80 84 90 96) (24 48 60 72 80 84 90 96)
 (12 30 36 40 56 70) 11 5 6)
CL-USER> (- 14 8)
6

结果， all-peris*和 dupl-peris*的长度与我计算的不匹配。然而，他们的差异确实与计数相符。
之后，我评论了 (length...)部分，让程序只列出列表并 mapcared #'length结果：

CL-USER> (mapcar #'length (peri-list* 2 1 1 100 nil nil))
(14 8 6)

这一次，前两个长度与实际计数相符。然而，差别仍然是一样的，这意味着我仍然得到了错误的答案。

CL-USER> (mapcar #'length (peri-list 2 1 1 nil nil))
(355571 247853)
CL-USER> (- 355571 247853)
107718

这让我质疑我的基本假设。这是我的问题。
具体问题：
我在这篇文章顶部描述的算法正确吗？会的
all-peris和 dupl-peris之间的差异
(remove-duplicates...)）给我正确的答案？
这段代码是否正确地收集了
all-peris和具有多个三角形的周长
dupl-peris？
(let ((peri (make-peri m n k)))
(if (member peri all-peris)
(peri-list* m (1+ n) k limit all-peris (cons peri dupl-peris))
(peri-list* m (1+ n) k limit (cons peri all-peris) dupl-peris)))
是什么导致了这种神秘的行为？
当我使用Java和Common Lisp得到相同的结果时，我
认为这不是我犯的语言错误为什么？
如果你的尺寸是
只有一个三角形的周长是多少？有基本的吗
我在算法上犯的错误或者
集合及其子集？
我希望这有助于“解开”我的问题。
编辑#2，更新Java版本：
我试图使用 length编写我的解决方案的java版本，其中perimeters作为键，perimeters的频率作为值。这里是：

public static void main(String[] args) {
    HashMap<Long, Long> perisMap = new HashMap<>();
    periMap(865, 125000, perisMap);
    System.out.println("Number of all perimeters (1 triangle, many triangles): " + perisMap.size());
    Long uniqueCounter = Long.valueOf("0");
    for (Map.Entry<Long, Long> entry : perisMap.entrySet()){
        Long freq = entry.getValue();
        if (freq == 1){
            uniqueCounter++;
        }
    }
    System.out.println("Number of all perimeters in the map which appear only once: " + uniqueCounter);
}
private static Long makePeri (long m, long n, long k){
    //Long a, b, c, res;
    //a = k * (m * m - n * n);
    //b = 2 * k * m * n;
    //c = k * (m * m + n * n);
    return 2 * k * (m * m  + m * n);
}
private static void periMap (long x, long z, HashMap<Long, Long> myMap){
        Long nLimit;
        Long limit = Long.valueOf("1500000");
        for (long k = 1; k <= z; k++){
            for (long m = 2; m <= x; m++){
                nLimit = limit / (2 * k * m) - m;
                for (long n = 1; ((n <= nLimit) && (n < m)); n++){
                    Long tempKey = makePeri(m,n,k);
                    Long tempVal = myMap.get(tempKey);
                    if (Long.compare(tempKey, limit) <= 0){
                        if (myMap.containsKey(tempKey)){
                            myMap.put(tempKey, tempVal + 1);
                        }
                        else {
                            myMap.put(tempKey, Long.valueOf("1"));
                        }
                    }
                }
            }
        }
    }

这就是我运行它时得到的：

Number of all perimeters (1 triangle, many triangles): 355571
Number of all perimeters in the map which appear only once: 107718

结果与旧的java版本和带有列表的通用lisp版本相同。我正在尝试使用哈希表编写一个新的通用Lisp版本。
问题：
这是第三个版本，结果相同显然，我的逻辑/算法/数学出了问题。有什么线索吗？

Answer 1

要使用Euler公式来解决这个问题，必须遵循所有的规则，这些规则保证每个三元组只生成一次否则，将多次生成相同的三元组，并跳过有效长度，因为它们的计数过高。
规则包括只使用同素的(m,n)对，并且m和n不是同时奇数的。
我认为如果你根据这些规则添加检查以避免无效对，你的算法将是正确的至少会更近一些。
关于Java代码的另一个注释：声明Long变量很少有用。声明long，让自动装箱在需要时进行转换。一般来说，使用Long类型是很奇怪的。例如，Long.valueOf("1")可以替换为1或1L同样地，Long.compare(tempKey, limit) <= 0应该是tempKey <= limit。
事实上，对于这个问题，long是不必要的。这完全可以用int来完成。
口齿不清
跟踪生成的每个长度的最简单方法是使用一个小整数数组以下是常见的口齿不清的想法：

(defun count-triangles (limit)
  (let ((counts (make-array (1+ limit)
                  :element-type 'unsigned-byte
                  :initial-element 0))
        (result 0))
    (loop for m from 2 to (ceiling (sqrt limit)) do
      (loop for n from 1 to (1- m)
        for k1-len = (* 2 m (+ m n)) then (+ k1-len (* 2 m))
        while (<= k1-len limit)
        when (and (oddp (+ m n)) (= (gcd m n) 1))
        do (loop for len = k1-len then (+ len k1-len)
             while (<= len limit)
             do (case (aref counts len)
                  (0 (incf result)
                     (incf (aref counts len)))
                  (1 (decf result)
                     (incf (aref counts len)))))))
    result))

在编译的CLisp中，这大约需要0.5秒下面的Java版本在我的老MacBook上运行的时间是0.014秒。

static int count() {
  byte [] count = new byte[MAX + 1];
  int result = 0;
  for (int m = 2; m < SQRT_MAX; ++m) {
    for (int n = 1; n < m; ++n) {
      if (((m ^ n) & 1) == 0 || gcd(m, n) > 1) continue;
      int base_len = 2 * m * (n + m);
      if (base_len > MAX) break;
      for (int len = base_len ; len <= MAX; len += base_len) { 
        switch (count[len]) {
        case 0:
          ++result;
          count[len] = 1;
          break;
        case 1:
          --result;
          count[len] = 2;
          break;
        default:
          break;
        }
      }
    }
  }
  return result;
}