十進制小數中最長的循環週期 - 錯誤還是誤解？

這是相當'數學-y'，但我在這裏發佈，因爲它是一個歐拉項目問題，&我有工作代碼，可能有錯誤。十進制小數中最長的循環週期 - 錯誤還是誤解？

Determing longest repeating cycle in a decimal expansion問題使用對數解決了這個問題，但我很想用簡單的蠻力解決問題。更準確地說，我有興趣瞭解爲什麼我的算法和代碼沒有返回正確的解決方案。

的算法是簡單的：

複製「長除法」，
在每個步驟記錄中的除數，而其餘
當重複除數/餘數元組，推斷出該小數代表將重複。

這裏是私人領域，如要求

private int numerator; 
private int recurrence; 
private int result; 
private int resultRecurrence; 
private List<dynamic> digits;

這裏是代碼：

private void Go() 
{ 
    foreach (var i in primes) 
    { 
     digits = new List<dynamic>(); 
     numerator = 1; 
     recurrence = 0; 

     while (numerator != 0) 
     { 
      numerator *= 10; 

      // quotient 
      var q = numerator/i; 

      // remainder 
      var r = numerator % i; 
      digits.Add(new { Divisor = q, Remainder = r }); 

      // if we've found a repetition then break out 
      var m = digits.Where(p => p.Divisor == q && p.Remainder == r).ToList(); 
      if (m.Count > 1) 
      { 
       recurrence = digits.LastIndexOf(m[0]) - digits.IndexOf(m[0]); 
       break; 
      } 
      numerator = r; 
     } 

     if (recurrence > resultRecurrence) 
     { 
      resultRecurrence = recurrence; 
      result = i; 
     } 
}}

當測試整數< 10和20 <我得到正確的結果;我也正確地確定了i的價值。然而，我得到的十進制表示是不正確的 - 我計算i-1而正確的結果是少得多（類似i-250）。

所以想必我有一個編程錯誤 - 我找不到 - 或者一個邏輯錯誤。

我很困惑，因爲它對我來說就像是一個multiplicative group over p，其中會有p-1個元素。我確定我錯過了一些東西，任何人都可以提供建議嗎？

編輯

我不會包括我的素數的代碼 - 這是不相關的，我解釋我上面正確識別的i值（從內存是983），但我有問題獲得resultRecurrence的正確值。

來源

2011-09-05 Kirk Broadhurst

你能告訴我們你編寫代碼的語言嗎？我認爲這是JavaScript，然後意識到它不可能。 –

@Phil - 添加c＃標籤 - 這不是一個特定於c＃的問題，但我想標籤屬於。 –

你可以發佈整個代碼，其中變量'primes'，'digits'，'numerator'，'recurrence'，'resultRecurrence'和'result'被聲明嗎？如果這些是方法的參數，請向我們展示方法簽名以及如何調用它。 –

我感到困惑，因爲它感覺像是一個對我來說是一個乘法羣體，其中會有p-1個元素。我確定我錯過了一些東西，任何人都可以提供建議嗎？

關閉。

對於除2和5中的所有素數（它劃分10），餘數的序列是由從1開始，並通過

remainder = (10 * remainder) % prime

轉化形成從而ķ第餘數是10 ^ķ（mod prime）並且餘數集合形成非零餘數modulo [1]的一個子羣。重複週期的長度是該子組的順序，也稱爲10模的主階。

組非零餘數的順序模主要是prime-1，並且有由費馬定理：

設G是爲了g有限羣，H是G子組。然後H的訂單h分爲g。

如此循環的長度總是的prime-1一個除數，並且有時是prime-1，例如爲[1]對於複合編號7或19

n互質10中，這將是該組餘數的模n是互質n。

來源

2011-11-28 21:42:32

首先，你不需要除數，你只需要餘數。其次，我將函數分成多個獨立部分，而不是將所有內容都放在一個大的方法中：循環長度的長分解/找到與其餘部分（=找到最長循環）無關。

您的break在Where加上Count是不直觀的。爲什麼不只是使用while循環，條件是(! digits.Contains(r))？（這需要在循環開始之前將0作爲其餘部分放入digits列表中。）

這給我們留下了一個更簡潔的代碼，應該可以直接調試。

來源

2011-09-05 13:08:59

我最初是通過查看數字而不是餘數來開始的;然後我決定我需要看餘數，但保留數字。你是對的 - 沒有必要保持算法中的數字計算或存儲。 –

recurrence = digits.LastIndexOf(m[0]) - digits.IndexOf(m[0]);

肯定的resultRecurrence值總是將是i-1？由於1/n這個形式的一小部分開始，當正在進行的劃分（i的第數字）給出與第一個試用部門（1，因此i-1）相同的商數餘數時開始重複。

（作爲一個附註，我可以向你介紹Math.DivRem）。

來源

2011-09-05 13:09:14 AakashM

我做出了同樣的假設，但正如你在我的問題中看到的那樣，**不是正確的答案（根據歐拉項目，我傾向於相信） –

感謝'Math.DivRem' –

假設是錯誤的：有些數字的週期不是在小數點後面開始的。如果你把「i - 1」作爲答案，這將假設循環從第一個十進制數字開始。 –

十進制小數中最長的循環週期 - 錯誤還是誤解？

回答

相關問題