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

欧拉计划

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

另外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()

飘飞的白杨

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 = '')

愤怒的大头菇

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

芒果加黄桃

# 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这个条件可以用....

渡风

%% 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

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

k往事如烟k

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

王小召

符合队列：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

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

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

#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

#找出由互为排列的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

/*
答案：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

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