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

欧拉计划 · 发表于 2015-5-16 22:29:13

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

本帖最后由永恒的蓝色梦想于 2020-6-3 19:27 编辑

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 数的和。

迷雾少年 · 发表于 2016-8-30 18:01:00

跑了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;
}

复制代码

迷雾少年 · 发表于 2016-8-30 19:04:32

1406357289
1430952867
1460357289
4106357289
4130952867
4160357289

拈花小仙 · 发表于 2016-8-30 21:21:28

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

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

迷雾少年 · 发表于 2016-8-30 21:34:21

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

觉得无聊，就试着做做了

拈花小仙 · 发表于 2016-8-30 21:44:56

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

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

迷雾少年 · 发表于 2016-8-30 21:57:57

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

会的，谢谢小仙支持

jerryxjr1220 · 发表于 2016-10-5 22:22:38

迷雾少年发表于 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)

复制代码

飘飞的白杨 · 发表于 2016-10-8 12:09:38

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)
请按任意键继续. . .

复制代码

芒果加黄桃 · 发表于 2017-1-15 22:52:25

本帖最后由芒果加黄桃于 2017-1-15 22:53 编辑

# 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

渡风 · 发表于 2017-6-13 00:14:25

此代码使用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-8-17 18:35:21

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

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

cq_xuke · 发表于 2017-8-17 18:45:13

本帖最后由 cq_xuke 于 2017-8-17 18:50 编辑

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 · 发表于 2017-8-19 19:12:56

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 · 发表于 2017-9-30 09:31:42

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

时间已过 0.127576 秒。
>>

hk1057 · 发表于 2018-7-30 13:31:28

'''
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 · 发表于 2019-3-29 16:35:56

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]

王小召 · 发表于 2019-6-14 15:31:16

结果是：['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 · 发表于 2020-8-17 17:15:50

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 · 发表于 2020-10-13 12:36:36

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)

复制代码

账号		自动登录	找回密码
密码			立即注册

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

马上注册，结交更多好友，享用更多功能^_^

浏览过的版块