题目26：找出小于1000的数字中令1/d拥有最长循环圈的数字d

欧拉计划

Reciprocal cycles

A unit fraction contains 1 in the numerator. The decimal representation of the unit fractions with denominators 2 to 10 are given:

1/2        =         0.5
1/3        =         0.(3)
1/4        =         0.25
1/5        =         0.2
1/6        =         0.1(6)
1/7        =         0.(142857)
1/8        =         0.125
1/9        =         0.(1)
1/10      =         0.1
Where 0.1(6) means 0.166666..., and has a 1-digit recurring cycle. It can be seen that 1/7 has a 6-digit recurring cycle.

Find the value of d < 1000 for which 1/d contains the longest recurring cycle in its decimal fraction part.

题目：

分子为1的分数称为单分数。分母是 2 到 10 的单分数用十进制表示如下：

1/2        =        0.5
1/3        =        0.(3)
1/4        =        0.25
1/5        =        0.2
1/6        =        0.1(6)
1/7        =        0.(142857)
1/8        =        0.125
1/9        =        0.(1)
1/10      =        0.1

其中 0.1(6) 表示 0.166666...，因此它有一个长度为 1 的循环圈。可以看出 1/7 拥有一个 6 位的循环圈。

找出小于 1000 的数字 d，1/d 的十进制表示含有最长的循环圈。

愤怒的大头菇

1. def func(x):
   
2.       list1 = []
   
3.       temp = 10%x
   
4.       list1.append(temp)
   
5.       while True:
   
6.             if (temp *10)%x == 0:
   
7.                   length = 0
   
8.                   break
   
9.                   
   
10.             elif (temp *10) %x not in list1:
    
11.                   temp = (temp *10) %x
    
12.                   list1.append(temp)
    
13.             elif temp in list1:
    
14.                   length = len(list1[list1.index((temp *10) %x):])
    
15.                   break
    
16.       return length
    
17. first = 0
    
18. list1 = []
    
19. for i in range(2,1001):
    
20.       length = func(i)
    
21.       if first < length:
    
22.             first = length
    
23.             list1.append(i)
    
24.       else:
    
25.             continue
    
26. print(list1[-1])

复制代码

运行结果是983

jerryxjr1220

1. # -*- coding: utf-8 -*-
   
2. """
   
3. Created on Sat Jan  7 08:58:29 2017
   
4. 
   
5. @author: Jerry Xu
   
6. """
   
7. import time
   
8. start = time.time()
   
9. def getprimes(n=1000):
   
10.     primes = [True]*n
    
11.     primes[0],primes[1]=False,False
    
12.     for i,prime in enumerate(primes):
    
13.         if prime:
    
14.             for j in range(i*i,n,i):
    
15.                 primes[j]=False
    
16.     primes[2],primes[5]=False,False
    
17.     return [k for k,trueprime in enumerate(primes) if trueprime]
    
18. def loop(n):
    
19.     tmp = []
    
20.     m = 10
    
21.     while m%n not in tmp:
    
22.         tmp.append(m%n)
    
23.         m *= 10
    
24.     if not tmp[-1]:
    
25.         return 0
    
26.     else:
    
27.         return len(tmp)
    
28. 
    
29. longest, x = 0, 0
    
30. for i in getprimes():
    
31.     if loop(i)>longest:
    
32.         longest = loop(i)
    
33.         x = i
    
34. print (x, longest)
    
35. print ('Time used: %.3f sec' % (time.time()-start))

复制代码

输出：
983 982
Time used: 0.429 sec

渡风

此代码使用matlab编程
Problem26所用时间为0.63431秒
Problem26的答案为983

1. %% Problem26
   
2. % 题目26：找出1000以内的数字d，使得1/d拥有最大的循环圈        
   
3. function Output=Problem26(Input)
   
4. tic
   
5. if nargin==0
   
6. Input=1000;
   
7. end
   
8. Circle_Max=0;%储存最大的循环圈
   
9. Circle=0;%当前数的循环圈
   
10. R=1;
    
11. r=1;
    
12. Flag=0;
    
13. for ii=1:Input
    
14.     R=1;
    
15.     r=1;
    
16.     while (Flag==0)
    
17.         r=mod(r*10,ii);
    
18.         if r==0
    
19.             Circle=0;%1、r=0表示能除尽,没有循环圈；
    
20.             break
    
21.         else
    
22.             inx=find(r==R);
    
23.             if isempty(inx)==0
    
24.                 %2、看r是否出现在R中,如果出现,表示已完成了循环圈,计算循环圈长度即可；
    
25.                 Circle=length(R)-length(inx)+1;
    
26.                 break
    
27.             else
    
28.                 %3、如果r未出现在R中,则把r添加到R,然后继续循环.
    
29.                 Temp=[R,r];
    
30.                 R=Temp;               
    
31.             end
    
32.         end
    
33.     end
    
34.     if Circle>=Circle_Max
    
35.         Circle_Max=Circle;
    
36.         d=ii;
    
37.     end
    
38. end
    
39. Output=d;
    
40. toc
    
41. disp('此代码使用matlab编程')
    
42. disp(['Problem26所用时间为',num2str(toc),'秒'])
    
43. disp(['Problem26的答案为',num2str(Output)])

复制代码

99592938

1. def Recip(x):
   
2.     a=1
   
3.     l=[]
   
4.     while 1:
   
5.         if a<x:
   
6.             l.append(a)
   
7.             a=10*a
   
8.         elif a%x:
   
9.             a=a%x
   
10.         else:
    
11.             return 0
    
12.         if a in l:
    
13.             return(len(l)-l.index(a))
    
14. 
    
15. l_recip=[0]
    
16. for d in range(1,1000):
    
17.     l_recip.append(Recip(d))
    
18. print('数字='+str(l_recip.index(max(l_recip))),'循环圈='+str(max(l_recip)))

复制代码

>>>
数字=983 循环圈=982

99592938

jerryxjr1220 发表于 2017-1-7 09:24
输出：
983 982
Time used: 0.429 sec

你的27行改为:

1.         return len(tmp)-tmp.index(m%n)

复制代码

应该才更准确。
下面是我借鉴了你的循环圈算法，写的：

1. def Recip(x):
   
2.     a=1
   
3.     l=[]
   
4.     while a%x not in l:
   
5.         l.append(a%x)
   
6.         a*=10
   
7.     if not l[-1]:
   
8.         return 0
   
9.     else:
   
10.         return(len(l)-l.index(a%x))
    
11. 
    
12. l_recip=[0]
    
13. for d in range(1,1000):
    
14.     l_recip.append(Recip(d))
    
15. print('数字='+str(l_recip.index(max(l_recip))),'循环圈='+str(max(l_recip)))

复制代码

cwhsmile

99592938 发表于 2017-3-15 17:03
>>>
数字=983 循环圈=982

果然是大神，用了相除统计余数，只要余数有相等的情况就会出现循环。

我是真笨，根本就想不到。。。。。。

永恒的蓝色梦想

1. #include<iostream>
   
2. #include<cstring>
   
3. 
   
4. 
   
5. 
   
6. int main() {
   
7.     using namespace std;
   
8.     ios::sync_with_stdio(false);
   
9. 
   
10.     constexpr unsigned short UPPER_BOUND = 1000;
    
11.     static unsigned short n, max_n, length, max_length, a, appeared[UPPER_BOUND];
    
12. 
    
13. 
    
14.     for (n = 1; n < UPPER_BOUND; n++) {
    
15.         a = 1;
    
16. 
    
17.         for (length = 1;; length++) {
    
18.             a *= 10;
    
19.             a %= n;
    
20. 
    
21.             if (a) {
    
22.                 if (appeared[a]) {
    
23.                     length -= appeared[a];
    
24. 
    
25.                     if (length > max_length) {
    
26.                         max_n = n;
    
27.                         max_length = length;
    
28.                     }
    
29. 
    
30.                     break;
    
31.                 }
    
32. 
    
33.                 appeared[a] = length;
    
34.             }
    
35.             else {
    
36.                 break;
    
37.             }
    
38.         }
    
39. 
    
40.         memset(appeared, 0, n * sizeof(unsigned short));
    
41.     }
    
42. 
    
43. 
    
44.     cout << max_n << endl;
    
45.     return 0;
    
46. }

复制代码

a1351468657

1. #include <stdio.h>
   
2. 
   
3. int check_num(int n) //标记法
   
4. {
   
5.         int i, a[1000] = { 0 }, count = 0;
   
6.         i = 10 % n;
   
7.         if (i)
   
8.         {
   
9.                 while (1)
   
10.                 {
    
11.                         if (a[i])
    
12.                         {
    
13.                                 return count;
    
14.                         }
    
15.                         a[i] = 1;
    
16.                         i *= 10;
    
17.                         i %= n;
    
18.                         count++;
    
19.                 }
    
20.         }
    
21.         else
    
22.         {
    
23.                 return 0;
    
24.         }
    
25. }
    
26. main()
    
27. {
    
28.         int i, count, max = 0, num;
    
29.         for (i = 2; i < 1000; i++)
    
30.         {
    
31.                 count = check_num(i);
    
32.                 if (max < count)
    
33.                 {
    
34.                         max = count;
    
35.                         num = i;
    
36.                 }
    
37. 
    
38.         }
    
39.         printf("%d  %d"， num, max);
    
40. }

复制代码

数字是983， 圈数是982

ft215378

#找出小于 1000 的数字 d，1/d 的十进制表示含有最长的循环圈
#求1/n的循环圈长度
def loop(n):
    result = []
    res = 1
    while True:
        if n <= 10:
            res = (res*10) % n
            if res not in result:
                result.append(res)
            else:
                break
            
        elif 10 < n <= 100:
            res = (res*100) % n
            if res not in result:
                result.append(res)
            else:
                break
        elif 100 <= n <= 1000:
            res = (res*1000) % n
            if res not in result:
                result.append(res)
            else:
                break
               
    return len(result)
d = []
for i in range(1, 1001):
    d.append(loop(i))

print((d.index(max(d))+ 1), max(d))

guosl

1. /*
   
2. 答案：983
   
3. 耗时：0.0230429秒（单核）
   
4.       0.00499988秒（八核）
   
5. */
   
6. #include <iostream>
   
7. #include <algorithm>
   
8. #include <vector>
   
9. #include <omp.h>
   
10. using namespace std;
    
11. 
    
12. int getCycleLen(int n)//求出数n的循环节长度
    
13. {
    
14.   vector<int> vC;
    
15.   int r = 1;
    
16.   vector<int>::iterator itr;
    
17.   while (r > 0)
    
18.   {
    
19.     r = r % n;
    
20.     itr = find(vC.begin(), vC.end(), r);
    
21.     if (itr != vC.end())
    
22.       break;
    
23.     vC.push_back(r);
    
24.     r *= 10;
    
25.   }
    
26.   if (r == 0)
    
27.     return 0;
    
28.   int k = int(vC.end() - itr);
    
29.   return k;
    
30. }
    
31. 
    
32. int main(void)
    
33. {
    
34.   volatile int nMaxLen = 0, nVal = 0;
    
35. #pragma omp parallel for shared(nMaxLen,nVal) schedule(dynamic)
    
36.   for (int i = 1; i < 1000; ++i)
    
37.   {
    
38.     int k = getCycleLen(i);
    
39.     if (k > nMaxLen)
    
40.     {
    
41. #pragma omp critical
    
42.       {
    
43.         nMaxLen = k;
    
44.         nVal = i;
    
45.       }
    
46.     }
    
47.   }
    
48.   cout << nVal << endl;
    
49.   return 0;
    
50. }
    

复制代码

mathtimes

1. import math
   
2. prime = [2,3]
   
3. def isprime(n):
   
4.         if n<=prime[-1]:
   
5.                 return n in prime
   
6.         else:
   
7.                 i = prime[-1]+2
   
8.                 while n>prime[-1]:
   
9.                         j = 0
   
10.                         while j<math.sqrt(len(prime)):
    
11.                                 s = True
    
12.                                 if i%prime[j]==0:
    
13.                                         s = False
    
14.                                         break
    
15.                                 j = j+1
    
16.                         if s:
    
17.                                 prime.append(i)
    
18.                         i = i+1
    
19.                 return n in prime
    
20. def odd(up,down):
    
21.         bits=[]
    
22.         sign=[]
    
23.         up %= down;
    
24.         up *= 10;
    
25.         bits.append(up//down)
    
26.         up %= down
    
27.         while up not in sign:
    
28.                 sign.append(up)
    
29.                 up *= 10;
    
30.                 bits.append(up//down)
    
31.                 up %= down
    
32.         bits.pop()
    
33.         return bits
    
34. maxv = 0
    
35. maxi = 0
    
36. for i in range(2,1000):
    
37.         if isprime(i):
    
38.                 if len(odd(1,i))>maxv:
    
39.                         maxv = len(odd(1,i))
    
40.                         maxi = i
    
41. print(maxi,maxv)

复制代码