無法找到我的錯誤，涉及畢達哥拉斯三元組和算法設置

Question

我試圖找到答案「鑑於L是電線的長度，有多少L≤1,500,000的值可以完全是一個整數雙面直角三角形？「，Project Euler #75。

我並沒有要求正確的答案，或代碼來找到它。我會解釋我是如何試圖解決這個問題的，只是要求你指出我錯在哪裏。我試圖解決Java和Common Lisp中的問題總是得到相同的錯誤答案。因此，我很確定我的算法中有些東西或者我的基本假設是錯誤的，但是我找不到它。我對潛在錯誤點的猜測是：1）設置差異錯誤2）設置參數限制錯誤。

這裏是我的算法如下：

1. 生成所有畢達哥拉斯三重周邊和收集他們在一組 「A」（列表Common Lisp的，因此時間差）。這個集合將會產生每一個周長，只有一個三角形 解決方案或者不止一個。因爲它是一個集合，每個周邊只會代表一次 。
2. 收集附加設置 「B」中的週期性（重複）周長。這組將包括只有一個三角形解決方案具有超過 的周長。
3. A - B應該給我一個單一的三角形的周長列表 的解決方案。這可能是我錯了的地方。

我用公式發現here來生成三元組，因此是周長。我優選使用式與所述附加係數「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 *（平方公尺 - N^2 +的2mn + M^2 + N^2）< = 1500000

而且發現這一點：

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

下面是在代碼Java和Common Lisp。請注意，雖然Java由於HashSet只需2秒鐘，但Common Tips在我的筆記本上需要1889秒，很可能是因爲檢查新生成的外圍是否已經是集合「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; 
     }  
} 

的Common 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)) 

任何解釋，我錯了可以理解的地方。但請不要給出正確的答案或代碼。

編輯：

我爲了做出的Common Lisp的代碼的稍加改動版本，看看如何收集到的名單（套）看，並希望看到什麼不順心。

我還添加了位來自動設置限制到m個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...)部分，有計劃只列出名單，並mapcar編#'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 

這讓我質疑了我的基本假設。所以這是我的問題。

具體的問題：

1. 是我在這篇文章的正確的頂部描述的算法？ all-peris和dupl-peris（之後 (remove-duplicates...)）給我正確的答案？
2. 這段代碼是否正確地收集了 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)))

是什麼原因導致的length神祕行爲？

由於我對Java和Common Lisp都有同樣的結果，所以我認爲這不是我所做的特定於語言的錯誤。爲什麼 不會有peris.removeAll(duplicatePeris);的大小給我 只有一個三角形的周長數？是否有一些基本的 錯誤，我正在使用該算法或與 集合及其子集的差異？

我希望這有助於「解除」我的問題。

編輯＃2，Java版本的更新：

我試圖用HashMap，與周邊的按鍵和頻率周邊的價值觀寫我的解決方案的Java版本。那就是：

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版本和Common Lisp的版本列表。我目前正在嘗試使用散列表編寫新的Common Lisp版本。

問題：
這是第三個版本，結果相同。顯然，我的邏輯/算法/數學有問題。任何指針在哪裏？

Answer 1

要使用歐拉公式對於這個問題，你必須遵守所有保證每個三會產生恰好一次規則。否則，您將多次生成相同的三元組，並且您將跳過有效長度，因爲它們的計數過高。

該規則包括僅使用(m,n)對是共素，並且其中m和n都不是奇數。

我認爲如果您根據這些規則添加檢查以避免無效對，那麼您的算法將是正確的。至少它會更接近。

對您的Java代碼的額外評論：聲明Long變量很少有用。聲明long並讓自動裝箱按需處理轉換。一般來說，您使用Long類型很奇怪。例如。 Long.valueOf("1")可以替換爲1或1L。同樣，Long.compare(tempKey, limit) <= 0應該是tempKey <= limit。其實long對於這個問題是不必要的。它可以完全用int完成。

Lisp的

跟蹤有多少你已經生成每個長度爲小整數數組的最簡單方法。下面是Common Lisp中的想法：

(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; 
}