题目49：找出由互为排列的4位数质数组成的序列

欧拉计划 · 发表于 2015-5-29 22:49:19

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

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

x

Prime permutations

The arithmetic sequence, 1487, 4817, 8147, in which each of the terms increases by 3330, is unusual in two ways: (i) each of the three terms are prime, and, (ii) each of the 4-digit numbers are permutations of one another.

There are no arithmetic sequences made up of three 1-, 2-, or 3-digit primes, exhibiting this property, but there is one other 4-digit increasing sequence.

What 12-digit number do you form by concatenating the three terms in this sequence?

题目：

1487, 4817, 8147 这个序列，每个比前一个递增 3330，而且这个序列有两个特点：1. 序列中的每个数都是质数。 2. 每个四位数都是其他数字的一种排列。

1，2，3 位组成的三个质数的序列中没有具有以上性质的。但是还有另外一个四位的递增序列满足这个性质。

如果将这另外一个序列的三个数连接起来，组成的 12 位数字是多少？

jerryxjr1220 · 发表于 2016-10-6 16:22:39

本帖最后由 jerryxjr1220 于 2016-10-12 16:24 编辑

另外4位数字是：2969 6299 9629
def isPrime(num):
if num == 2:
return True
elif num % 2 == 0:
return False
else:
for i in range(3,int(num**0.5+1),2):
if num % i == 0:
return False
return True
def main():
primes = sorted([x for x in range(1000, 10000) if isPrime(x)])
for a in primes:
b = a + 3330
c = b + 3330
# test 1: are primes
if b in primes and c in primes:
# test 2: are permutations of each other
if set(sorted(list(str(a)))) == set(sorted(list(str(b)))) == set(sorted(list(str(c)))):
print (a, b, c)
main()

复制代码

飘飞的白杨 · 发表于 2016-10-29 21:06:03

from itertools import permutations as per
def isprime(n):
if n <= 1: return False
if n == 2: return True
if n % 2 == 0: return False
for i in range(3,int(n**0.5)+1,2):
if n % i == 0: return False
return True
for i in per([1,2,3,4,5,6,7,8,9],3):
if i[0] > 3: break
n = i[0]*100+i[1]*10+i[2]
if sorted(list(str(n))) == sorted(list(str(n + 333))) == sorted(list(str(n + 666))):
for j in [1,3,7,9]:
if isprime(n*10+j) and isprime(n*10+j+3330) and isprime(n*10+j+6660):
if n*10+j != 1487:
print(n*10+j,n*10+j+3330,n*10+j+6660,sep = '')

复制代码

愤怒的大头菇 · 发表于 2016-11-18 23:20:14

import math
def Prime(x):
if x >1:
if x==2:
return True
if x%2==0:
return False
for i in range(3,int(math.sqrt(x)+1),2):
if x%i==0:
return False
return True
return False
list1=[]
for i in range(1000,10000):
if Prime(i):
list1.append(i)
for i in list1:
j = 1000
while True:
tmp = False
if i+j in list1 and i+2*j in list1:
tmp = True
if tmp:
a=set(str(i))
b=set(str(i+j))
c = set(str(i+2*j))
if a==b and b==c:
print(i,i+j,i+2*j)
break
else:
tmp = False
if not tmp:
j+=10
if i+2*j>list1[-1]:
break

复制代码

运行结果：
1487 4817 8147
2969 6299 9629

芒果加黄桃 · 发表于 2017-1-16 15:15:51

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

# encoding:utf-8
# 1487 4817 8147 都是质数等差数列找另外一组类似的四位数
from time import time
from itertools import permutations
def getPrimes(N):
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
return [k for k, p in enumerate(primes) if p and k > 1000]
def isSeq(s_nums):
l_sums = list(s_nums)
l_sums.sort()
for i in range(0, len(l_sums)):
for j in range(i + 1, len(l_sums)):
for k in range(j + 1, len(l_sums)):
if l_sums[i] - l_sums[j] == l_sums[j] - l_sums[k]:
print(l_sums[i], l_sums[j], l_sums[k])
def euler049(N=10000):
s_primes = set(getPrimes(N))
s_pass = set()
for each in s_primes:
if each in s_pass:
continue
l_tmp = list(str(each))
s_tmp = set()
for tt in permutations(l_tmp, 4):
s = ''
for t in tt:
s += t
s_tmp.add(int(s))
joint_set = s_primes & s_tmp
s_pass = s_pass | joint_set
if len(joint_set) >= 3:
isSeq(joint_set)
if __name__ == '__main__':
start = time()
euler049()
print('cost %.6f sec' % (time() - start))

复制代码

2969 6299 9629
1487 4817 8147
cost 0.022000 sec

完成后学习了其他几位老大的程序，发现原来还有差值3330这个条件可以用....

渡风 · 发表于 2017-6-14 11:18:40

%% Problem49.m
%最后编辑时间：2017-06-14 11:13 版本1.0
%找出三个四位数的质数，能够形成等差数列,且差值为3330，并且能够互为排列。
%这要的质数组有两组。找出第二组
%使用传统的三重循环

% 此代码使用matlab编程
% Problem49所用时间为10.2873秒
% Problem49的答案为[1487 4817 8147;2969 6299 9629]

%% Problem49.m
%最后编辑时间：2017-06-14 11:13 版本1.0
%找出三个四位数的质数，能够形成等差数列,且差值为3330，并且能够互为排列。
%这要的质数组有两组。找出第二组
%使用传统的三重循环
% 此代码使用matlab编程
% Problem49所用时间为10.2873秒
% Problem49的答案为[1487 4817 8147;2969 6299 9629]
function Output = Problem49()
tic
%先刷出大于1000 小于10000 的素数组
Limit = 10000;
Judge = ones(1,Limit-1);
Judge(1) = 0;
for ii = 1:Limit-1
if Judge(ii) == 1
for jj = 2*ii : ii : Limit-1
Judge(jj) = 0;
end
end
end
PossiFactor = find(Judge == 1);
All = PossiFactor(PossiFactor > 1000);
Num = length(All);
Output = P49(Num,All);
toc
disp('此代码使用matlab编程')
disp(['Problem49所用时间为',num2str(toc),'秒'])
disp(['Problem49的答案为',mat2str(Output)])
end
% 此程序为了解决欧拉计划的第十九题
% 破除三重循环，使用return
function Output = P49(Num,All)
Output = zeros(2,3);
Time = 0;
for ii = 1 : Num-2
for jj = ii+1 : Num -1
for kk = jj+1 : Num
if All(jj) - 3330 == All(ii) && All(kk) - 3330 == All(jj)
if strcmp(sort(num2str(All(ii))),sort(num2str(All(kk)))) == 1 && ... %比较三个数是否为相互的排列数
strcmp(sort(num2str(All(ii))),sort(num2str(All(jj)))) == 1
Time = Time + 1;
Output(Time,:) = [All(ii),All(jj),All(kk)];
if Time == 2
return
end
end
end
end
end
end
end

复制代码

najin · 发表于 2017-9-30 09:29:36

用的matlab
结果是:
296962999629
时间已过 0.028753 秒。
>>

k往事如烟k · 发表于 2019-3-30 02:13:56

def isPrime(num):
if num <= 1:
return False
else:
for i in range(2, int(num**0.5+1)):
if num % i == 0:
return False
else:
return True
def numList(num):
numTemp = []
for i in range(int(len(str(num)))):
numTemp.append(int(str(num)[i]))
numTemp.sort()
return list(set(numTemp))
#大于2的数为质数，其必然为奇数且为某4个数字的3种排列，所以最小为num1=1235
#所以递增的数i必然为偶数，且最大取到(9999-num1)/2
sequenceList = []
for num1 in range(1235, 9996, 2):
for i in range(2, (9999-num1)//2+1, 2):
if isPrime(num1):
num2 = num1 + i
if isPrime(num2):
num3 = num1 + 2*i
if isPrime(num3):
if numList(num1) == numList(num2) and numList(num1) == numList(num3):
sequenceList.append((num1, num2, num3))
#print(sequenceList)
numStr = ""
for each in sequenceList[-1]:
numStr += str(each)
print(int(numStr))

复制代码

296962999629

王小召 · 发表于 2019-6-24 15:59:50

符合队列：1487--4817--8147
符合队列：2969--6299--9629
用时:0.12480079999999999 秒

import itertools
import time
def is_prime(min_range, max_range):
bool_range = [1] * max_range
bool_range[0], bool_range[1] = 0, 0
for i, j in enumerate(bool_range):
if j:
for k in range(i**2, max_range, i):
bool_range[k] = 0
return [x for x, p in enumerate(bool_range) if p and x > min_range]
def cal_result():
t_primes = is_prime(1000, 10000)
s_primes = set(t_primes)
for each_num in t_primes:
tmp_result = []
for each_str in itertools.permutations(str(each_num)):
tmp_num = int(''.join(each_str))
if tmp_num in s_primes:
tmp_result.append(tmp_num)
s_primes.remove(tmp_num)
tmp_result.sort()
if len(tmp_result) >= 3:
for i in range(len(tmp_result) - 2):
for j in range(i + 2, len(tmp_result)):
if (tmp_result[j] + tmp_result[i])/2 in tmp_result:
print("符合队列：{}--{}--{}".format(tmp_result[i], int((tmp_result[j] + tmp_result[i])/2), tmp_result[j]))
if __name__ == "__main__":
cal_result()
print("用时:{} 秒".format(time.process_time()))

复制代码

debuggerzh · 发表于 2020-8-19 18:35:06

148748178147
296962999629

Process returned 0 (0x0) execution time : 0.025 s
Press any key to continue.

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int M = 1e4;
int cnt = 0;
bool prime[M];
int factor[M];
void euler_sieve(){
prime[1] = false;
for (int i = 2;i <= M;i++) prime[i] = true;
for (int i = 2;i <= M;i++){
if (prime[i]) factor[++cnt] = i;
for (int j = 1;j <= cnt && i*factor[j] < M;j++){
prime[i*factor[j]] = false;
if (i % factor[j] == 0) break;
}
}
}
void parse(int a[],int x){
for (int i = 0;i < 4;i++){
a[i] = x % 10;
x /= 10;
}
}
bool judge(int a[][4]){
bool b1 = false,b2 = false;
int t[4];
for (int i = 0;i < 4;i++) t[i] = a[0][3-i];//反序，以下只需一论排列
do{
if (memcmp(t,a[1],sizeof(t) ) == 0) b1 = true;
if (memcmp(t,a[2],sizeof(t) ) == 0) b2 = true;
}while(next_permutation(t,t+4) );
return b1 && b2;
}
int main(){
euler_sieve();
int n[3] = {0};
for (int j = 1000;j+6660 < 10000;j++){
n[0] = j;
for (int i = 1;i < 3;i++) n[i] = n[0] + i*3330;
int a[3][4];
if (!prime[n[0] ] || !prime[n[1] ] || !prime[n[2] ]) continue;
for (int i = 0;i < 3;i++) parse(a[i],n[i]);
if (judge(a)) cout << n[0] << n[1] << n[2] << endl;
}
return 0;
}

复制代码

4444567 · 发表于 2020-10-21 12:17:56

list1 = []#存放1000-10000的所有质数
def prime(n):
if n%2==0:
return False
else:
for i in range(3,int(n**0.5)+1,2):
if n%i==0:
return False
else:
return True
for i in range(1000,10001):
if prime(i):
list1.append(i)
def bj(a,b):
a = list(str(a))
a.sort()
b = list(str(b))
b.sort()
if a == b:
return True
list2 = []
for i in range(len(list1)):
for j in range(1,i):
s = list1[i] - list1[j]
if bj(list1[j],list1[i]):
if (list1[i]+s) in list1:
if bj(list1[i],list1[i]+s):
list2.append((list1[j],list1[i],list1[i]+s))
print(list2)

复制代码

a1351468657 · 发表于 2021-3-25 20:03:49

#include <stdio.h>
#include <math.h>
int check_prime(int);
int check_prime(int num)//判质数
{
int i, j;
j = sqrt(num + 1);
for (i = 2; i <= j; i++)
{
if (num % i == 0)
{
return 0;
}
}
return 1;
}
main()
{
int i, j, k, m, n, p;
for (i = 1489; i < 10000; i += 2)
{
int a[10] = { 0 };
if (check_prime(i))
{
j = i + 3330;
n = i;
for (m = 0; m < 4; m++)//标记法，将i中各个位上的数用数组a标记
{
p = n % 10;
a[p] = 1;
n /= 10;
}
n = j;
for (m = 0; m < 4; m++)//判断加3330后是否是第一个数的排列
{
p = n % 10;
if (a[p] == 0)
{
goto Label;//不是就直接到标签Label处开始下一轮循环
}
n /= 10;
}
if (check_prime(j))
{
k = j + 3330;
n = k;
for (m = 0; m < 4; m++)//判断再加3330后是否是第一个数的排列
{
p = n % 10;
if (a[p] == 0)
{
goto Label;
}
n /= 10;
}
if (check_prime(k))
{
printf("%d %d %d\n", i, j, k);
break;
}
}
}
Label:continue;
}
}

复制代码

2969 6299 9629

ft215378 · 发表于 2021-10-22 21:31:04

#找出由互为排列的4位数质数组成的序列
from time import *
from math import *
from itertools import * #permutations([1,2,3,4], 4)
#验证是否是质数
def is_prime(number):
if number > 1:
      if number == 2:
         return True
      if number % 2 == 0:
         return False
      for a in range(3,int(sqrt(number) + 1),2):
         if number % a == 0:
            return False
      return True
return False

def creat_increase(num):
if is_prime(num):
      a = num
      b = num + 3330
      c = b + 3330
      if is_prime(b) and is_prime(c):
         return [a, b, c]
      else:
         return None
else:
      return None

#判断是否满足排列条件
def contidion(seq):
out_0 = 0
out_1 = 0
out_2 = 0
out_list0 = []
out_list1 = []
out_list2 = []
for i in str(seq[0]):
      out_0 += int(i)
      out_list0.append(i)
out_list0.sort()
for i in str(seq[1]):
      out_1 += int(i)
      out_list1.append(i)
out_list1.sort()
for i in str(seq[2]):
      out_2 += int(i)
      out_list2.append(i)
out_list2.sort()
if out_0 == out_1 == out_2 and\
   out_list0 == out_list1 == out_list2:
      return True

#生成相差3330且3个数都是质数的序列  列表
def creat_list():
num = 1000
total_list = []
while num + 6660 < 9999:
      if creat_increase(num):
         total_list.append(creat_increase(num))
      num += 1
return total_list
s = time()
for each in creat_list():
if contidion(each):
      print(each)
e = time()
print("用时%.4f秒" % (e-s))
#'''

guosl · 发表于 2022-1-8 17:10:42

/*
答案：296962999629
耗时：0.0170646秒
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdlib>
using namespace std;
char cp[10000];//素数表
int main(void)
{
//建立素数表
memset(cp, 1, 9998 * sizeof(char));
for (int i = 2; i <= 100; ++i)
{
if (cp[i] == 0)
continue;
for (int j = i * i; j < 10000; j += i)
cp[j] = 0;
}
char str[12] = "";
for (int i = 1000; i < 10000; ++i)//枚举第一个素数
{
if (cp[i] == 0 || i == 1487)
continue;
char str1[8] = "";
_itoa(i, str1, 10);
sort(str1, str1 + 4);
bool bFind = false;
for (int j = i + 1; j < 10000; ++j)//枚举第二个素数
{
if (cp[j] == 0)
continue;
char str2[8] = "";
_itoa(j, str2, 10);
sort(str2, str2 + 4);
if (strcmp(str1, str2) != 0)//比对各位数字是否是排列
continue;
int nD = j - i;//计算公差
if (j + nD >= 10000)
continue;
if (cp[j + nD] == 1)//找到第三个候选数
{
char str3[8] = "";
_itoa(j + nD, str3, 10);
sort(str3, str3 + 4);
if (strcmp(str1, str3) != 0)//比对各位数字是否是排列
continue;
//找到了
bFind = true;
//拼接数字
_itoa(i, str1, 10);
strcat(str, str1);
_itoa(j, str2, 10);
strcat(str, str2);
_itoa(j + nD, str3, 10);
strcat(str, str3);
break;
}
}
if (bFind)
break;
}
cout << str << endl;
return 0;
}

复制代码

B1tetheDust · 发表于 2022-10-25 01:40:43

import time as t
import math
from itertools import permutations
start = t.perf_counter()
def check_prime(a_num):
is_prime = 1
for i in range(2, int(math.sqrt(a_num) + 1)):
if a_num % i == 0:
is_prime = 0
return is_prime
bool_prime = [True] * 10000
for pre in range(1000):
bool_prime[pre] = False
for num in range(1000, 10000):
if not check_prime(num):
bool_prime[num] = False
for j in range(1000, 10000):
if bool_prime[j]:
j_perm = set(permutations(str(j)))
bool_prime[j] = False
nums = [j]
count = 1
for k in j_perm:
k_str = ''
for m in k:
k_str += str(m)
k_int = int(k_str)
if bool_prime[k_int]:
count += 1
bool_prime[k_int] = False
nums.append(k_int)
nums.sort()
if count >= 3:
for n in nums:
if n + 6660 > 10000:
break
elif n + 3330 in nums and n + 6660 in nums:
print(n, n + 3330, n + 6660)
print("It costs %f s" % (t.perf_counter() - start))

复制代码

1487 4817 8147
2969 6299 9629
It costs 0.042802 s

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