소수 또는 최하위 반복주기 - 버그 또는 오해?

Question

이것은 꽤 '수학 - 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의 값을 식별합니다. 그러나 나가 얻는 십진법 represetation는 부정확하다 - 나는 정확한 결과가 멀리 더 적은이 (i-250 같이 무언가가 반면) i-1를 산출한다.

아마 내가 프로그래밍 버그 - 찾을 수없는 - 또는 논리 버그가 있습니다.

p-1 요소가있는 multiplicative group over p과 같은 느낌이 들기 때문에 혼란 스럽습니다. 나는 누군가가 제안을 할 수 있는지, 나는 무엇인가 놓치고 있다고 확신한다?

편집

내 소수 코드를 포함하지 않을거야 - 내가 제대로 (가 983이다 메모리에서) i의 값을 식별 위에 내가 설명대로 관련 아니지만 나는 데 resultRecurrence에 대한 올바른 값을 얻는 데 문제가 있습니다.

Answer 1

p-1 요소가있는 p 이상의 곱셈 그룹처럼 느껴지기 때문에 혼란 스럽습니다. 나는 누군가가 제안을 할 수 있는지, 나는 무엇인가 놓치고 있다고 확신한다?

닫기. 도 2 및도 5를 제외한 모든 소수 (이 10 분할) 용

은 나머지의 시퀀스는 이와 K 번째 나머지 10 ^{K는 1에서 시작}

remainder = (10 * remainder) % prime 

로 변환함으로써 형성된다 (mod 프라임)이고 나머지 세트는 modulo prime [1]이 아닌 0이 아닌 나머지 그룹의 하위 그룹을 형성합니다. 되풀이주기의 길이는 해당 하위 그룹의 순서이며, 이는 10 모듈러스 소수 (modulo prime)의 차수라고도합니다.

제로가 아닌 나머지 그룹의 순서는 프라임 prime-1 인 모듈로, 그리고 정리는 페르마가있다 :

하자 순서 g의 유한 그룹이 될 G 및 H는 G의 하위 그룹합니다. 그런 다음 h이 H 인 경우 g으로 나눕니다.

따라서 사이클의 길이는 항상 prime-1의 약수이며, 때로는 prime-1입니다.

[1] 합성 숫자 n이 10 대 1 일 때, 나머지는 n 나머지가 n 인 그룹이됩니다.

Answer 2

첫째로, 약자가 필요 없으며 나머지 만 필요합니다.

둘째로, 나는 하나의 큰 방법으로 모든 것을 가지지 않고 함수를 여러 개의 독립된 부분으로 나눌 것입니다 : 사이클 길이의 긴 나눗셈/발견은 나머지와 독립적입니다 (= 가장 긴 사이클을 찾는 것).

귀하의 break에 Where과 결합하면 Count은 직관적이지 않습니다. 왜 (! digits.Contains(r)) 조건으로 while 루프를 사용하지 않는가? (이렇게하려면 루프 시작 전에 digits 목록에 나머지로 0을 넣어야합니다.)

이렇게하면 디버그하는 것이 훨씬 더 명확한 코드가됩니다.

Answer 3

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

는 확실히 resultRecurrence의 값은 항상i-1을 될 것입니다? 1/n 형식의 일부분의 경우 소수점은 division-in-progress (i 번째 자리)가 첫 번째 시험 분할 (, 따라서 i-1)과 동일한 몫 - 나머지를 제공 할 때 정확하게 반복되기 시작합니다.

(부수적으로, Math.DivRem으로 안내 할 수 있습니다.)