题目43：找出所有具有异常子串整除性的pandigital数之和

欧拉计划

Sub-string divisibility

The number, 1406357289, is a 0 to 9 pandigital number because it is made up of each of the digits 0 to 9 in some order, but it also has a rather interesting sub-string divisibility property.

Let be the digit, be the digit, and so on. In this way, we note the following:



Find the sum of all 0 to 9 pandigital numbers with this property.

题目：

1406357289 是一个 pandigital 数，因为它包含了 0 到 9 之间每个数字且只包含了一次。此外它还有一个有趣的子串整除性质。

令 表示其第一位数字， 表示第二位，以此类推。这样我们可以得到：



求所有具有如上性质的 0 到 9 pandigital 数的和。

迷雾少年

跑了10几分钟  
3个数。。。
1406357289
1430952867
1460357289
还没跑完，等下补充

#include <iostream>
#include <algorithm>
#include <string>
#include <strstream>
using namespace  std;
void unsigned_to_hex(unsigned int value, std::string& hex_string)
{
        std::strstream buffer;
        buffer.setf(std::ios::showbase);
        buffer  << value;   
        buffer >> hex_string;
}


//这个数是不是pandight数字
bool isnumpandig(unsigned int n)        
{
        
        
        string str;
        unsigned_to_hex(n,str);
        sort(str.begin(),str.end());
        int i = str.size();

        for (int n=0;n<i-1;n++)
        {
                if(str[n]==str[n+1])
                        return false;
        }
        return true;
}
//获取一个int类型的位数
int get(unsigned int n)
{
        if(n==0) return 1;
        int m = 0;
        while (n)
        {
                n/=10;
                m++;
        }
        return m;
}
//获取一个数的第几位
//从左边开始第几个
unsigned int  getnum(unsigned int n,int m)
{
        int k = get(n)-m+1; //就是右边的k个
        int z = 1;
        while (n)
        {
                if(z==k)
                        return n%10;
                n/=10;

                z++;

        }
}
 int cal(unsigned int num,int a,int b,int c)
{
        string str;
    unsigned_to_hex(num,str);
        int len =str.size();

        
        return (getnum(num,a)*100)+(getnum(num,b)*10)+(getnum(num,c));
}
int main(void)
{
        //从0123456789开始
        //std::cout<<cal(2802399493,2,3,4);
        //2802399493
        for (unsigned int n=1023456789;n<=9876543210;n+=1)
        {
                //满足几个性质 
                if(isnumpandig(n))
                {
                        //好尴尬
                        if(cal(n,2,3,4)%2==0)
                                if(cal(n,3,4,5)%3==0)
                                        if(cal(n,4,5,6)%5==0)
                                                if(cal(n,5,6,7)%7==0)
                                                        if(cal(n,6,7,8)%11==0)
                                                                if(cal(n,7,8,9)%13==0)
                                                                        if(cal(n,8,9,10)%17==0)
                                                                                std::cout<<n<<endl;

                        
                }
        }
        return 0;
}

迷雾少年

1406357289
1430952867
1460357289
4106357289
4130952867
4160357289

拈花小仙

迷雾少年 发表于 2016-8-30 18:01
跑了10几分钟  
3个数。。。
1406357289

能答出欧拉计划这些题的人不多呀` 支持迷雾大神~

迷雾少年

拈花小仙 发表于 2016-8-30 21:21
能答出欧拉计划这些题的人不多呀` 支持迷雾大神~

觉得无聊，就试着做做了

拈花小仙

迷雾少年 发表于 2016-8-30 21:34
觉得无聊，就试着做做了

迷雾大神在无聊次，我们就又多一份参考文献啦~
你编程技术高，能不能写篇日常关于编程过程中的小技巧整理、和心得体会呢。

迷雾少年

拈花小仙 发表于 2016-8-30 21:44
迷雾大神在无聊次，我们就又多一份参考文献啦~
你编程技术高，能不能写篇日常关于编程过程中 ...

会的，谢谢小仙支持

jerryxjr1220

迷雾少年 发表于 2016-8-30 19:04
1406357289
1430952867
1460357289

答案应该是对的，但是我换了一种算法，不要穷举所有数，不然效率太低。
我是生成pandigital，然后依次判断，27.3秒搞定。

['4130952867', '1430952867', '4160357289', '4106357289', '1460357289', '1406357289']
[Finished in 27.3s]

def getPan(n):
        if n == 2:
                return ['210','120','102','201','021','012']
        if n>2:
                pan = getPan(n-1)
                length = len(pan[0])
                pannew = []
                for each in pan:
                        pannew.append(str(n)+str(each))
                        pannew.append(str(each)+str(n))
                        for j in range(1,length):
                                pannew.append(str(each)[:j]+str(n)+str(each)[j:])
                return pannew

def judge(plist):
        prime = [2,3,5,7,11,13,17]
        returnlist = []
        for each in plist:
                if each[0] == '0':
                        pass
                else:
                        flag = 1
                        for j in range(1,8):
                                if each[j] == '0':
                                        if int(each[j+1:j+3]) % prime[j-1] != 0:
                                                flag = 0
                                                break
                                else:
                                        if int(each[j:j+3]) % prime[j-1] != 0:
                                                flag = 0
                                                break
                        if flag == 1:
                                returnlist.append(each)
        return returnlist

plist = getPan(9)
plist = judge(plist)
print (plist)

飘飞的白杨

from itertools import permutations as per
x = lambda l: (l[1]*100+l[2]*10+l[3]) % 2 == 0 and (l[2]*100+l[3]*10+l[4]) % 3 == 0 and (l[3]*100+l[4]*10+l[5]) % 5 == 0 and (l[4]*100+l[5]*10+l[6]) % 7 == 0 and (l[5]*100+l[6]*10+l[7]) % 11 == 0 and (l[6]*100+l[7]*10+l[8]) % 13 == 0 and (l[7]*100+l[8]*10+l[9]) % 17 == 0
for i in per([0, 1, 2, 3, 4, 5, 6, 7, 8, 9]):
    if i[0] == 0:
        continue
    if x(i):
        print(i)

(1, 4, 0, 6, 3, 5, 7, 2, 8, 9)
(1, 4, 3, 0, 9, 5, 2, 8, 6, 7)
(1, 4, 6, 0, 3, 5, 7, 2, 8, 9)
(4, 1, 0, 6, 3, 5, 7, 2, 8, 9)
(4, 1, 3, 0, 9, 5, 2, 8, 6, 7)
(4, 1, 6, 0, 3, 5, 7, 2, 8, 9)
请按任意键继续. . .

芒果加黄桃

# encoding:utf-8
# 查找三角形单词个数
from time import time
from itertools import permutations
def euler043():
    l_temp = [v for v in permutations([0, 1, 2, 3, 4, 5, 6, 7, 8, 9], 10)]
    l_primes = [2, 3, 5, 7, 11, 13, 17]
    l_pans = []
    l_result = []
    for each in l_temp:
        if each[0] == 0:
            continue
        if each[3] % 2 != 0:
            continue
        if each[5] not in (0, 5):
            continue
        s = ''
        for i in list(each):
            s += str(i)
        l_pans.append(s)
    for each in l_pans:
        flag = True
        for j in range(0, 7):
            if not int(each[j + 1:j + 4]) % l_primes[j] == 0:
                flag = False
                break
        if flag:
            l_result.append(int(each))
    print(l_result)
      
if __name__ == '__main__':
    start = time() 
    euler043()
    print('cost %.6f sec' % (time() - start))

[1406357289, 1430952867, 1460357289, 4106357289, 4130952867, 4160357289]
cost 3.463459 sec

渡风

此代码使用matlab编程
Problem43所用时间为491.9989秒
Problem43的答案为16695334890
算是优化到尽头了，还是跑了8分钟。。matlab的确有劣势

%% Problem43.m
%最后编辑时间：2017-06-12 23:13 版本1.0
%找出满足0—9的pandigital数的个数
% Problem43所用时间为491.9989秒
% Problem43的答案为16695334890
function Output = Problem43()
tic
Output = 0;
All = perms('0123456789');
[M,~] = size(All);

Prime  = [2 3 5 7 11 13 17];
for ii = 1:M
    Num = All(ii,:);
    disp(Num)
    Cut = zeros(1,7);
    Judge = 1;
    for jj = 1:7
        Cut(jj) = str2double(Num(jj+1:jj+3));
        if mod(Cut(jj),Prime(jj)) ~= 0
            Judge = 0;
            break
        end
    end
    
    if Judge == 1
        Output = Output + str2double(Num);
    end
            
end
toc

disp('此代码使用matlab编程')
disp(['Problem43所用时间为',num2str(toc),'秒'])
disp(['Problem43的答案为',num2str(Output)])
end

cq_xuke

渡风 发表于 2017-6-13 00:14
此代码使用matlab编程
Problem43所用时间为491.9989秒
Problem43的答案为16695334890

肯定还可以优化的，我用matlab写的代码，耗时是30多秒

cq_xuke

import time
s=time.clock()
from itertools import permutations
from functools import reduce
primes=[2,3,5,7,11,13,17]
count=0
for pandigits in permutations([9,8,7,6,5,4,3,2,1,0]):
    if pandigits[0]==0:
        break
    i=1
    for p in primes:
        pan=reduce(lambda x,y:x*10+y,pandigits[i:i+3])
        i+=1
        if pan % p != 0:
            break
    else:
        count+=reduce(lambda x,y:x*10+y,pandigits)
print(count)
print('Runing time: {0}s'.format(round(time.clock()-s,3)))

16695334890
Runing time: 5.251s

zengtaozt

from time import time
from itertools import permutations
start = time()

def Euler43(i):
    list_1 = ['0','1','2','3','4','5','6','7','8','9']
    list_2 = []
    str_1 = ''
    for each in i:
        if each in list_1:
            list_1.remove(each)
    for each in range(0,len(list_1)):
         s = list_1[each]+"".join(i)
         list_2.append(s[0:3])
    return  list_2

sum = 0
s = permutations('1234567890',3)
for i in s :
      if int(''.join(i[:])) % 17==0:
            for each in Euler43(i):
                if int(each) %13 ==0:
                    for b in Euler43(each[0]+''.join(i)):
                        if int(b)%11==0:
                           for c in Euler43(b[0]+each[0]+"".join(i)):
                               if int(c)%7==0:
                                   for d in Euler43(c[0]+b[0]+each[0]+"".join(i)):
                                        if int(d)%5 ==0:
                                            for e in Euler43(d[0]+c[0]+b[0]+each[0]+"".join(i)):
                                                if int(e)%3 == 0:
                                                    for f in Euler43(e[0]+d[0]+c[0]+b[0]+each[0]+"".join(i)):
                                                        if int(f)%2 ==0:
                                                            for g in Euler43(f[0]+e[0]+d[0]+c[0]+b[0]+each[0]+"".join(i)):
                                                                sum = sum+int(g[0]+f[0]+e[0]+d[0]+c[0]+b[0]+each[0]+"".join(i))
print(sum)
print("Time taken %.6f s" % (time() - start))

16695334890
Time taken 0.002000 s

najin

用的matlab
结果是：
     1     6     6     9     5     3     3     4     8     9     0

时间已过 0.127576 秒。
>>

hk1057

'''
ps:利用生成0~9pandigital 和 生成器相结合可以有效缩减时间

answer:
1406357289
1430952867
1460357289
4106357289
4130952867
4160357289
'''


def produce_9_pandigital():
        list2=[]
        for d0 in range(1,10):
                for d1 in range(10):
                        if d1 != d0:
                                for d2 in range(10):
                                        if d2 not in [d0,d1]:
                                                for d3 in range(10):
                                                        if d3 not in [d0,d1,d2]:
                                                                for d4 in range(10):
                                                                        if d4 not in [d0,d1,d2,d3]:
                                                                                for d5 in range(10):
                                                                                        if d5 not in [d0,d1,d2,d3,d4]:
                                                                                                for d6 in range(10):
                                                                                                        if d6 not in [d0,d1,d2,d3,d4,d5]:
                                                                                                                for d7 in range(10):
                                                                                                                        if d7 not in [d0,d1,d2,d3,d4,d5,d6]:
                                                                                                                                for d8 in range(10):
                                                                                                                                        if d8 not in [d0,d1,d2,d3,d4,d5,d6,d7]:
                                                                                                                                                for d9 in range(10):
                                                                                                                                                        if d9 not in [d0,d1,d2,d3,d4,d5,d6,d7,d8]:
                                                                                                                                                                str_num=str(d0)+str(d1)+str(d2)+str(d3)+str(d4)+str(d5)+str(d6)+str(d7)+str(d8)+str(d9)
                                                                                                                                                                yield int(str_num)


for each in produce_9_pandigital():
                str_i=str(each)
                d_1=1
                d_2=2
                d_3=3
                list1=[2,3,5,7,11,13,17]
                for x in range(7):
                        sum_d1d2d3=int(str_i[d_1])*100 + int(str_i[d_2])*10 + int(str_i[d_3])
                        if sum_d1d2d3 % list1[x] != 0:
                                break
                        d_1+=1
                        d_2+=1
                        d_3+=1
                else:
                        print(each)

k往事如烟k

def perm(n):
    import itertools
    for i in range(n):
        if i == 1:
            listTemp = [0]
        else:
            listTemp = []
            for j in range(i+1):
                listTemp.append(j)
    list1 = list(itertools.permutations(listTemp, len(listTemp)))
    numList = []
    for i in range(len(list1)):
        numStr = ""
        for j in range(len(list1[i])):
            numStr += str(list1[i][j])
        num = int(numStr)
        numList.append(num)
    return numList

TempNumList = perm(10)
allNumList = []
for each in TempNumList:
    if len(str(each)) == 10:
        allNumList.append(each)

def SubNumList(Num):
    SubNumList = []
    for i in range(1, 8):
        SubNumStr = ""
        for j in range(3):
            SubNumStr += str(Num)[i + j]
        SubNumList.append(int(SubNumStr))
    return SubNumList

divisorList = [2, 3, 5, 7, 11, 13, 17]
finalNumList = []
for each1 in allNumList:
    TempList = SubNumList(each1)
    for i in range(len(TempList)):
        if TempList[i] % divisorList[i] != 0:
            break
    else:
        finalNumList.append(each1)

print(finalNumList)

[1406357289, 1430952867, 1460357289, 4106357289, 4130952867, 4160357289]

王小召

结果是：['1406357289', '1430952867', '1460357289', '4106357289', '4130952867', '4160357289']
用时：4.6644299 秒

import itertools
import time

def get_result():
    result = []
    for each in itertools.permutations([str(i) for i in range(10)]):
        target_list = [2, 3, 5, 7, 11, 13, 17]
        mark = 1
        for i in range(7):
            if int(each[1+i] + each[2+i] + each[3+i]) % target_list[i]:
                mark = 0
                break
        if mark:
            result.append("".join(each))
    return result

print("结果是：{}\n用时：{} 秒".format(get_result(), time.process_time()))

debuggerzh

16695334890

Process returned 0 (0x0)   execution time : 0.241 s
Press any key to continue.
进行了一通优化……从0.33提到0.24
枚举全排列

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;

const int p[] = {0,2,3,5,7,11,13,17};//0占位
int a[] = {1,0,2,3,4,5,6,7,8,9};

ll parse(int l,int r){
  ll res = 0;

  for (;l < r;l++){
    res *= 10;
    res += a[l];
  }
  return res;
}

int main(){
  ll ans = 0;

  do{
    bool flag = true;
    if (a[3] & 1) continue;
    if ( (a[2]+a[3]+a[4]) % 3) continue;
    if (a[5] && a[5] != 5)  continue;
    if (a[5] + a[7] != a[6] && a[5] + a[7] != a[6] + 11)  continue;

    for (int i = 1;i <= 7;i++){
      int t = parse(i,i+3);
      if (t % p[i]) {flag = false; break;}
    }
    if (flag) ans += parse(0,10);

  }while(next_permutation(a,a+10));

  cout << ans << endl;
  return 0;
}

4444567

from time import time

def getPan(n):#从大神处copy
        if n == 2:
                return ['210','120','102','201','021','012']
        if n>2:
                pan = getPan(n-1)
                length = len(pan[0])
                pannew = []
                for each in pan:
                        pannew.append(str(n)+str(each))
                        pannew.append(str(each)+str(n))
                        for j in range(1,length):
                                pannew.append(str(each)[:j]+str(n)+str(each)[j:])
                return pannew
t = time()
list1 = getPan(9)
list2 = []
for i in list1:
        if int(i[1:4])%2==0:
                if int(i[2:5])%3==0:
                        if int(i[3:6])%5==0:
                                if int(i[4:7])%7==0:
                                        if int(i[5:8])%11==0:
                                                if int(i[6:9])%13==0:
                                                        if int(i[7:10])%17==0:
                                                                list2.append(int(i))
                
print(list2, '和是：', sum(list2))
print('cos:',time()-t)