题目38：最大的能够通过一个固定数与1,2,3,...相乘得到的1到9pandigital数是多少？

欧拉计划

Pandigital multiples

Take the number 192 and multiply it by each of 1, 2, and 3:

192 × 1 = 192
192 × 2 = 384
192 × 3 = 576
By concatenating each product we get the 1 to 9 pandigital, 192384576. We will call 192384576 the concatenated product of 192 and (1,2,3)

The same can be achieved by starting with 9 and multiplying by 1, 2, 3, 4, and 5, giving the pandigital, 918273645, which is the concatenated product of 9 and (1,2,3,4,5).

What is the largest 1 to 9 pandigital 9-digit number that can be formed as the concatenated product of an integer with (1,2, ... , n) where n > 1?

题目：

将 192 与 1, 2, 3 分别相乘得到：

192 × 1 = 192
192 × 2 = 384
192 × 3 = 576

将这三个乘积连接起来我们得到一个 1 到 9 的 pandigital 数， 192384576。我们称 192384576 是 192 和 (1,2,3) 的连接积。

通过将 9 与 1, 2, 3, 4 和 5 相乘也可以得到 pandigital 数：918273645，这个数是 9 和 (1,2,3,4,5) 的连接积。

用一个整数与 1,2, ... , n（n 大于 1）的连接积构造而成的 1 到 9 pandigital 数中最大的是多少？

迷雾少年

没懂什么意思，，不过感觉不难。。

愤怒的大头菇

list1 = [1,2,3,4,5,6,7,8,9]
list2 = []
for i in range(1,100000):
      str_1 = ''
      for each in list1:
            str_1 += str(i*each)
            if len(str_1)>=9:
                  break
      
      if len(str_1) == 9:
            tmp = True
            for each in list1:
                  if str(each) not in str_1:
                        tmp = False
                        break
            if tmp:
                  list2.append(int(str_1))
                  list2.sort()
print(list2[-1])
                  

932718654

芒果加黄桃

# encoding:utf-8
# 一个整数与1,2,3...N的乘积链接构成1-9的pandigital，寻找最大的数
from time import time
def euler038():
    for i in range(1, 9877):
        tmp = ''
        for t in range(1, 10):
            tmp += str(i * t)
            if len(tmp) > 9:
                break
            if len(tmp) == 9:
                if not '123456789'.strip(tmp):
                    print(i, [k for k in range(1, t + 1)])
                    break
if __name__ == '__main__':
    start = time() 
    euler038()
    print('cost %.6f sec' % (time() - start))

1 [1, 2, 3, 4, 5, 6, 7, 8, 9]
9 [1, 2, 3, 4, 5]
192 [1, 2, 3]
219 [1, 2, 3]
273 [1, 2, 3]
327 [1, 2, 3]
6729 [1, 2]
6792 [1, 2]
6927 [1, 2]
7269 [1, 2]
7293 [1, 2]
7329 [1, 2]
7692 [1, 2]
7923 [1, 2]
7932 [1, 2]
9267 [1, 2]
9273 [1, 2]
9327 [1, 2]
cost 0.020014 sec

渡风

%% Problem38.m
% 最后编辑时间：17-06-15 0:45
% 通过将 9 与 1, 2, 3, 4 和 5 相乘也可以得到 pandigital 数:918273645,这个数是918273645,这个数是 9 和 (1,2,3,4,5) 的连接积。
% 用一个整数与 1,2, ... , n(n 大于 1)的连接积构造而成的 1 到 9 pandigital 数中最大的数是多少？
%分析 ：1位数1 *[1 2 3 4 5 6 7 8 9] 9*[ 1 2 3 4 5]
%      2位数 * 不可能存在这样的数
%      3位数 * [1 2 3] 三位数小于 333
%      4位数 * [1 2]   四位数大于5000

%% Problem38.m
% 最后编辑时间：17-06-15 0:45
% 通过将 9 与 1, 2, 3, 4 和 5 相乘也可以得到 pandigital 数:918273645,这个数是918273645,这个数是 9 和 (1,2,3,4,5) 的连接积。
% 用一个整数与 1,2, ... , n(n 大于 1)的连接积构造而成的 1 到 9 pandigital 数中最大的数是多少？
%分析 ：1位数1 *[1 2 3 4 5 6 7 8 9] 9*[ 1 2 3 4 5]
%      2位数 * 不可能存在这样的数
%      3位数 * [1 2 3] 三位数小于 333
%      4位数 * [1 2]   四位数大于5000
% Problem38所用时间为： 1.43秒
% Problem358的答案为： 932718654
function Output = Problem38()
tic
Output = 0;
% 一位数
for ii = 1:9
    Str = [];
    FirstJudge = 0;
    for jj = 1:9
        Str = [Str,num2str(ii*jj)];
        if length(Str) == 9
            FirstJudge = 1;
            break
        elseif length(Str) > 9
            FirstJudge = 0;
            break
        end
    end
    
    if FirstJudge == 1
        if str2double(Str) > Output
            if strcmp(sort(Str),'123456789') == 1
                
                Output = str2double(Str);
            end
        end
    end
end

%三位数
for kk = 100:333
    Str = [num2str(kk),num2str(kk*2),num2str(kk*3)];
    if str2double(Str) > Output
        if strcmp(sort(Str),'123456789') == 1
            
            Output = str2double(Str);
        end
    end
end

%四位数

for ll = 5001:9999
    Str = [num2str(ll),num2str(ll*2)];
    if str2double(Str) > Output
        if strcmp(sort(Str),'123456789') == 1          
            Output = str2double(Str);
        end
    end
end
                   
        
toc
disp('此代码使用matlab编程')
disp(['Problem38所用时间为： ',num2str(toc),'秒'])
disp(['Problem358的答案为： ',num2str(Output)])

zengtaozt

from time import time
start = time()

def isPandingital(n):
    i =1
    str_1 = ''
    tag = True
    while i<10:
        str_1 = str_1+str(n*i)
        i = i + 1
        if '0' not in str_1:
            if  len(set(str_1))==9 and len(str_1)==9:
                   return True
                   break
    return False

def getPandingital(n):
    i = 1
    str_1 = ''
    tag = True
    while i < 10:
        str_1 = str_1+str(n * i)
        i = i + 1
        if '0' not in str_1:
            if len(set(str_1)) == 9 and len(str_1) == 9:
                return int(str_1)

num = 10000    #n需要大于1,所以需要两个数组合,num不会超过4位数,为保险,可以取num = 100000
while num > 0:
   if  not isPandingital(num):
       num -=1
   else:
       print(num)
       print(getPandingital(num))
       break

print("Program running cost %4f secs!" % (time() - start))

9327
932718654
Program running cost 0.005000 secs!

najin

用的matlab
结果是：
   932718654

时间已过 2.374731 秒。
>>

k往事如烟k

def concatenating(num):
    sum = 0
    numTempList = []
    for i in range(1, 10):
        sum += len(str(num * i))
        numTempList.append(str(num * i))
        if sum == 9:
            break
        elif sum > 9:
            break
    finalNumStr = ""
    for each in numTempList:
        finalNumStr += each
    finalNum = int(finalNumStr)
    return finalNum

def isPandigital(num):
    if len(str(num)) != 9:
        return False
    else:
        numTempList = []
        refNumList = [1, 2, 3, 4, 5, 6, 7, 8, 9]
        for i in range(len(str(num))):
            numTempList.append(int(str(num)[i]))
        if list(set(numTempList)) == refNumList:
            return True
        else:
            return False

numList = []
for num in range(1, 1000000):
    if isPandigital(concatenating(num)):
        numList.append(concatenating(num))

numList.sort()
print(numList[-1])

932718654

王小召

最大值是：932718654
用时:0.4212027 秒

import time

def is_pandigital(num):
    l = [i for i in str(num)]
    l.sort()
    if l == [str(i) for i in range(1, 10)]:
        return True
    else:
        return False

def cal_nums():
    results = []
    for num in range(1, 100000):
        length = 2
        tmp = ""
        for i in range(1, 10):
            tmp += str(num * i)
            if len(str(tmp)) < 9:
                continue
            elif len(str(tmp)) > 9:
                break
            else:
                if is_pandigital(tmp):
                    results.append((tmp, num, length))

    return results

results = cal_nums()
max_result = max(int(each[0]) for each in results)

print("最大值是：{}\n用时:{} 秒".format(max_result, time.process_time()))

debuggerzh

932718654

Process returned 0 (0x0)   execution time : 0.036 s
Press any key to continue.
既然题目已给出918273645这一解，可直接讨论首位为9的情况
一位数的构造只有上述一种
其余情况只有四位数满足题意
由连接积的定义，逆序枚举效率更高

#include<iostream>
using namespace std;

bool pan(int x,int y){
  int digit[10] = {0};

  while(x){
    digit[x % 10] = 1;
    x /= 10;
  }

  while(y){
    digit[y % 10] = 1;
    y /= 10;
  }

  if (digit[0]) return false;

  for (int i = 1;i < 10;i++)
    if (!digit[i]) return false;

  return true;
}

int main(){
  for (int i = 9876;i > 9011;i--){
    int t = 2*i;
    if (pan(i,2*i)) {cout << i << t << endl; break;}
  }
  return 0;
}

a1351468657

#include <stdio.h>
#include <string.h>

int check_num(int);
int check_num(int num)
{
        int i, j, a[10] = { 0 };
        j = num;
        while (j)
        {
                i = j % 10;
                if (i == 0)
                {
                        return 0;
                }
                if (a[i])
                {
                        return 0;
                }
                j /= 10;
                a[i] = 1;
        }
        return 1;
}

main()
{
        char str[20], rts[20];

        int i, j, k, max = 0;

        for (i = 5000; i < 10000; i++)
        {
                j = i * 2;
                sprintf(str, "%d", i);
                sprintf(rts, "%d", j);
                strcat(str, rts);
                k = atoi(str);

                if (check_num(k))
                {
                        max = max > i ? max : i;                        
                }
        }

        printf("%d", max);
}

9327

B1tetheDust

import time as t

start = t.perf_counter()


def is_pandigital(a_num):
    tar = [index for index in range(1, 10)]
    list_num = [int(each) for each in str(a_num)]
    if len(list_num) != 9:
        return False
    elif tar == list(set(list_num)):
        return True


pandigitals = []
for i in range(2, 10):
    multiplier = 10 ** (int(9 // i) - 1)
    while True:
        res = ''
        for j in range(1, i + 1):
            res += str(multiplier * j)
        res = int(res)
        if res > 1e9:
            break
        elif is_pandigital(res):
            pandigitals.append(res)
        multiplier += 1

print(max(pandigitals))
print("It costs %f s" % (t.perf_counter() - start))

932718654
It costs 0.031873 s

mathtimes

$ time ./main
932718654

real        0m0.002s
user        0m0.000s
sys        0m0.002s

fn bits(x: u32) -> u32 {
    let mut x = x;
    let mut ans = 0;
    while x != 0 {
        if x%10 == 0 {
            return 0;
        }
        let y = 1 << (x % 10 - 1);
        if ans & y != 0 {
            return 0;
        }
        ans |= y;
        x /= 10;
    }
    ans
}

fn is_pandigital(x: u32) -> bool {
    let mut tot = 0;
    for i in 1..=9 {
        let b = bits(i*x);
        if b == 0 || tot & b != 0 {
            return false;
        }
        tot |= b;
        if tot == 0b111111111 {
            return true;
        }
    }
    false
}

fn pandigital(x: u32) -> u32 {
    let v = &mut [0;9];
    let mut vi = 0;
    let mut i = 1;
    while vi != 9 {
        let mut y = x*i;
        while y != 0 {
            v[vi] = y / 10u32.pow(y.ilog10());
            vi += 1;
            y %= 10u32.pow(y.ilog10());
        }
        i += 1;
    }
    let mut sum = 0;
    for i in 0..=8 {
        sum += v[8-i] * 10u32.pow(i as u32);
    }
    sum
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_is_pandigital() {
        assert!(is_pandigital(192));
        assert!(is_pandigital(9));
        assert!(is_pandigital(1));
        assert!(!is_pandigital(191));
    }
    #[test]
    fn test_pandigital() {
        assert_eq!(pandigital(9),918273645);
        assert_eq!(pandigital(192),192384576);
    }
}

fn main () {
    // 要使 n > 1, 最多是4位数
    let v:Vec<u32> = (1..1e5 as u32).filter(|&x| is_pandigital(x)).collect();
    let p:Vec<u32> = v.into_iter().map(|x| pandigital(x)).collect();
    println!("{}", p.iter().max().unwrap());
}