题目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 的十进制表示含有最长的循环圈。

愤怒的大头菇

def func(x):
      list1 = []
      temp = 10%x
      list1.append(temp)
      while True:
            if (temp *10)%x == 0:
                  length = 0
                  break
                  
            elif (temp *10) %x not in list1:
                  temp = (temp *10) %x
                  list1.append(temp)
            elif temp in list1:
                  length = len(list1[list1.index((temp *10) %x):])
                  break
      return length
first = 0
list1 = []
for i in range(2,1001):
      length = func(i)
      if first < length:
            first = length
            list1.append(i)
      else:
            continue
print(list1[-1])

运行结果是983

jerryxjr1220

# -*- coding: utf-8 -*-
"""
Created on Sat Jan  7 08:58:29 2017

@author: Jerry Xu
"""
import time
start = time.time()
def getprimes(n=1000):
    primes = [True]*n
    primes[0],primes[1]=False,False
    for i,prime in enumerate(primes):
        if prime:
            for j in range(i*i,n,i):
                primes[j]=False
    primes[2],primes[5]=False,False
    return [k for k,trueprime in enumerate(primes) if trueprime]
def loop(n):
    tmp = []
    m = 10
    while m%n not in tmp:
        tmp.append(m%n)
        m *= 10
    if not tmp[-1]:
        return 0
    else:
        return len(tmp)

longest, x = 0, 0
for i in getprimes():
    if loop(i)>longest:
        longest = loop(i)
        x = i
print (x, longest)
print ('Time used: %.3f sec' % (time.time()-start))

输出：
983 982
Time used: 0.429 sec

渡风

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

%% Problem26
% 题目26：找出1000以内的数字d，使得1/d拥有最大的循环圈         
function Output=Problem26(Input)
 tic
if nargin==0
Input=1000;
end
Circle_Max=0;%储存最大的循环圈
Circle=0;%当前数的循环圈
R=1;
r=1;
Flag=0;
for ii=1:Input
    R=1;
    r=1;
    while (Flag==0)
        r=mod(r*10,ii);
        if r==0
            Circle=0;%1、r=0表示能除尽,没有循环圈；
            break
        else
            inx=find(r==R);
            if isempty(inx)==0
                %2、看r是否出现在R中,如果出现,表示已完成了循环圈,计算循环圈长度即可；
                Circle=length(R)-length(inx)+1;
                break
            else
                %3、如果r未出现在R中,则把r添加到R,然后继续循环.
                Temp=[R,r];
                R=Temp;                
            end
        end
    end
    if Circle>=Circle_Max
        Circle_Max=Circle;
        d=ii;
    end
end
Output=d;
toc
disp('此代码使用matlab编程')
disp(['Problem26所用时间为',num2str(toc),'秒'])
disp(['Problem26的答案为',num2str(Output)])

99592938

def Recip(x):
    a=1
    l=[]
    while 1:
        if a<x:
            l.append(a)
            a=10*a
        elif a%x:
            a=a%x
        else:
            return 0
        if a in l:
            return(len(l)-l.index(a))

l_recip=[0]
for d in range(1,1000):
    l_recip.append(Recip(d))
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行改为:

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

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

def Recip(x):
    a=1
    l=[]
    while a%x not in l:
        l.append(a%x)
        a*=10
    if not l[-1]:
        return 0
    else:
        return(len(l)-l.index(a%x))

l_recip=[0]
for d in range(1,1000):
    l_recip.append(Recip(d))
print('数字='+str(l_recip.index(max(l_recip))),'循环圈='+str(max(l_recip)))

cwhsmile

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

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

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

永恒的蓝色梦想

#include<iostream>
#include<cstring>



int main() {
    using namespace std;
    ios::sync_with_stdio(false);

    constexpr unsigned short UPPER_BOUND = 1000;
    static unsigned short n, max_n, length, max_length, a, appeared[UPPER_BOUND];


    for (n = 1; n < UPPER_BOUND; n++) {
        a = 1;

        for (length = 1;; length++) {
            a *= 10;
            a %= n;

            if (a) {
                if (appeared[a]) {
                    length -= appeared[a];

                    if (length > max_length) {
                        max_n = n;
                        max_length = length;
                    }

                    break;
                }

                appeared[a] = length;
            }
            else {
                break;
            }
        }

        memset(appeared, 0, n * sizeof(unsigned short));
    }


    cout << max_n << endl;
    return 0;
}

a1351468657

#include <stdio.h>

int check_num(int n) //标记法
{
        int i, a[1000] = { 0 }, count = 0;
        i = 10 % n;
        if (i)
        {
                while (1)
                {
                        if (a[i])
                        {
                                return count;
                        }
                        a[i] = 1;
                        i *= 10;
                        i %= n;
                        count++;
                }
        }
        else
        {
                return 0;
        }
}
main()
{
        int i, count, max = 0, num;
        for (i = 2; i < 1000; i++)
        {
                count = check_num(i);
                if (max < count)
                {
                        max = count;
                        num = i;
                }

        }
        printf("%d  %d"， num, max);
}

数字是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

/*
答案：983
耗时：0.0230429秒（单核）
      0.00499988秒（八核）
*/
#include <iostream>
#include <algorithm>
#include <vector>
#include <omp.h>
using namespace std;

int getCycleLen(int n)//求出数n的循环节长度
{
  vector<int> vC;
  int r = 1;
  vector<int>::iterator itr;
  while (r > 0)
  {
    r = r % n;
    itr = find(vC.begin(), vC.end(), r);
    if (itr != vC.end())
      break;
    vC.push_back(r);
    r *= 10;
  }
  if (r == 0)
    return 0;
  int k = int(vC.end() - itr);
  return k;
}

int main(void)
{
  volatile int nMaxLen = 0, nVal = 0;
#pragma omp parallel for shared(nMaxLen,nVal) schedule(dynamic)
  for (int i = 1; i < 1000; ++i)
  {
    int k = getCycleLen(i);
    if (k > nMaxLen)
    {
#pragma omp critical
      {
        nMaxLen = k;
        nVal = i;
      }
    }
  }
  cout << nVal << endl;
  return 0;
}

mathtimes

import math
prime = [2,3]
def isprime(n):
        if n<=prime[-1]:
                return n in prime
        else:
                i = prime[-1]+2
                while n>prime[-1]:
                        j = 0
                        while j<math.sqrt(len(prime)):
                                s = True
                                if i%prime[j]==0:
                                        s = False
                                        break
                                j = j+1
                        if s:
                                prime.append(i)
                        i = i+1
                return n in prime
def odd(up,down):
        bits=[]
        sign=[]
        up %= down;
        up *= 10;
        bits.append(up//down)
        up %= down
        while up not in sign:
                sign.append(up)
                up *= 10;
                bits.append(up//down)
                up %= down
        bits.pop()
        return bits
maxv = 0
maxi = 0
for i in range(2,1000):
        if isprime(i):
                if len(odd(1,i))>maxv:
                        maxv = len(odd(1,i))
                        maxi = i
print(maxi,maxv)