题目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 数中最大的是多少？

迷雾少年

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

愤怒的大头菇

1. list1 = [1,2,3,4,5,6,7,8,9]
   
2. list2 = []
   
3. for i in range(1,100000):
   
4.       str_1 = ''
   
5.       for each in list1:
   
6.             str_1 += str(i*each)
   
7.             if len(str_1)>=9:
   
8.                   break
   
9.       
   
10.       if len(str_1) == 9:
    
11.             tmp = True
    
12.             for each in list1:
    
13.                   if str(each) not in str_1:
    
14.                         tmp = False
    
15.                         break
    
16.             if tmp:
    
17.                   list2.append(int(str_1))
    
18.                   list2.sort()
    
19. print(list2[-1])
    
20.                   

复制代码

932718654

芒果加黄桃

1. # encoding:utf-8
   
2. # 一个整数与1,2,3...N的乘积链接构成1-9的pandigital，寻找最大的数
   
3. from time import time
   
4. def euler038():
   
5.     for i in range(1, 9877):
   
6.         tmp = ''
   
7.         for t in range(1, 10):
   
8.             tmp += str(i * t)
   
9.             if len(tmp) > 9:
   
10.                 break
    
11.             if len(tmp) == 9:
    
12.                 if not '123456789'.strip(tmp):
    
13.                     print(i, [k for k in range(1, t + 1)])
    
14.                     break
    
15. if __name__ == '__main__':
    
16.     start = time()
    
17.     euler038()
    
18.     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

1. %% Problem38.m
   
2. % 最后编辑时间：17-06-15 0:45
   
3. % 通过将 9 与 1, 2, 3, 4 和 5 相乘也可以得到 pandigital 数:918273645,这个数是918273645,这个数是 9 和 (1,2,3,4,5) 的连接积。
   
4. % 用一个整数与 1,2, ... , n(n 大于 1)的连接积构造而成的 1 到 9 pandigital 数中最大的数是多少？
   
5. %分析 ：1位数1 *[1 2 3 4 5 6 7 8 9] 9*[ 1 2 3 4 5]
   
6. %      2位数 * 不可能存在这样的数
   
7. %      3位数 * [1 2 3] 三位数小于 333
   
8. %      4位数 * [1 2]   四位数大于5000
   
9. % Problem38所用时间为： 1.43秒
   
10. % Problem358的答案为： 932718654
    
11. function Output = Problem38()
    
12. tic
    
13. Output = 0;
    
14. % 一位数
    
15. for ii = 1:9
    
16.     Str = [];
    
17.     FirstJudge = 0;
    
18.     for jj = 1:9
    
19.         Str = [Str,num2str(ii*jj)];
    
20.         if length(Str) == 9
    
21.             FirstJudge = 1;
    
22.             break
    
23.         elseif length(Str) > 9
    
24.             FirstJudge = 0;
    
25.             break
    
26.         end
    
27.     end
    
28.    
    
29.     if FirstJudge == 1
    
30.         if str2double(Str) > Output
    
31.             if strcmp(sort(Str),'123456789') == 1
    
32.                
    
33.                 Output = str2double(Str);
    
34.             end
    
35.         end
    
36.     end
    
37. end
    
38. 
    
39. %三位数
    
40. for kk = 100:333
    
41.     Str = [num2str(kk),num2str(kk*2),num2str(kk*3)];
    
42.     if str2double(Str) > Output
    
43.         if strcmp(sort(Str),'123456789') == 1
    
44.             
    
45.             Output = str2double(Str);
    
46.         end
    
47.     end
    
48. end
    
49. 
    
50. %四位数
    
51. 
    
52. for ll = 5001:9999
    
53.     Str = [num2str(ll),num2str(ll*2)];
    
54.     if str2double(Str) > Output
    
55.         if strcmp(sort(Str),'123456789') == 1         
    
56.             Output = str2double(Str);
    
57.         end
    
58.     end
    
59. end
    
60.                   
    
61.         
    
62. toc
    
63. disp('此代码使用matlab编程')
    
64. disp(['Problem38所用时间为： ',num2str(toc),'秒'])
    
65. disp(['Problem358的答案为： ',num2str(Output)])

复制代码

zengtaozt

1. from time import time
   
2. start = time()
   
3. 
   
4. def isPandingital(n):
   
5.     i =1
   
6.     str_1 = ''
   
7.     tag = True
   
8.     while i<10:
   
9.         str_1 = str_1+str(n*i)
   
10.         i = i + 1
    
11.         if '0' not in str_1:
    
12.             if  len(set(str_1))==9 and len(str_1)==9:
    
13.                    return True
    
14.                    break
    
15.     return False
    
16. 
    
17. def getPandingital(n):
    
18.     i = 1
    
19.     str_1 = ''
    
20.     tag = True
    
21.     while i < 10:
    
22.         str_1 = str_1+str(n * i)
    
23.         i = i + 1
    
24.         if '0' not in str_1:
    
25.             if len(set(str_1)) == 9 and len(str_1) == 9:
    
26.                 return int(str_1)
    
27. 
    
28. num = 10000    #n需要大于1,所以需要两个数组合,num不会超过4位数,为保险,可以取num = 100000
    
29. while num > 0:
    
30.    if  not isPandingital(num):
    
31.        num -=1
    
32.    else:
    
33.        print(num)
    
34.        print(getPandingital(num))
    
35.        break
    
36. 
    
37. print("Program running cost %4f secs!" % (time() - start))

复制代码

9327
932718654
Program running cost 0.005000 secs!

najin

用的matlab
结果是：
   932718654

时间已过 2.374731 秒。
>>

k往事如烟k

1. def concatenating(num):
   
2.     sum = 0
   
3.     numTempList = []
   
4.     for i in range(1, 10):
   
5.         sum += len(str(num * i))
   
6.         numTempList.append(str(num * i))
   
7.         if sum == 9:
   
8.             break
   
9.         elif sum > 9:
   
10.             break
    
11.     finalNumStr = ""
    
12.     for each in numTempList:
    
13.         finalNumStr += each
    
14.     finalNum = int(finalNumStr)
    
15.     return finalNum
    
16. 
    
17. def isPandigital(num):
    
18.     if len(str(num)) != 9:
    
19.         return False
    
20.     else:
    
21.         numTempList = []
    
22.         refNumList = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    
23.         for i in range(len(str(num))):
    
24.             numTempList.append(int(str(num)[i]))
    
25.         if list(set(numTempList)) == refNumList:
    
26.             return True
    
27.         else:
    
28.             return False
    
29. 
    
30. numList = []
    
31. for num in range(1, 1000000):
    
32.     if isPandigital(concatenating(num)):
    
33.         numList.append(concatenating(num))
    
34. 
    
35. numList.sort()
    
36. print(numList[-1])

复制代码

932718654

王小召

最大值是：932718654
用时:0.4212027 秒

1. import time
   
2. 
   
3. def is_pandigital(num):
   
4.     l = [i for i in str(num)]
   
5.     l.sort()
   
6.     if l == [str(i) for i in range(1, 10)]:
   
7.         return True
   
8.     else:
   
9.         return False
   
10. 
    
11. def cal_nums():
    
12.     results = []
    
13.     for num in range(1, 100000):
    
14.         length = 2
    
15.         tmp = ""
    
16.         for i in range(1, 10):
    
17.             tmp += str(num * i)
    
18.             if len(str(tmp)) < 9:
    
19.                 continue
    
20.             elif len(str(tmp)) > 9:
    
21.                 break
    
22.             else:
    
23.                 if is_pandigital(tmp):
    
24.                     results.append((tmp, num, length))
    
25. 
    
26.     return results
    
27. 
    
28. results = cal_nums()
    
29. max_result = max(int(each[0]) for each in results)
    
30. 
    
31. 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的情况
一位数的构造只有上述一种
其余情况只有四位数满足题意
由连接积的定义，逆序枚举效率更高

1. #include<iostream>
   
2. using namespace std;
   
3. 
   
4. bool pan(int x,int y){
   
5.   int digit[10] = {0};
   
6. 
   
7.   while(x){
   
8.     digit[x % 10] = 1;
   
9.     x /= 10;
   
10.   }
    
11. 
    
12.   while(y){
    
13.     digit[y % 10] = 1;
    
14.     y /= 10;
    
15.   }
    
16. 
    
17.   if (digit[0]) return false;
    
18. 
    
19.   for (int i = 1;i < 10;i++)
    
20.     if (!digit[i]) return false;
    
21. 
    
22.   return true;
    
23. }
    
24. 
    
25. int main(){
    
26.   for (int i = 9876;i > 9011;i--){
    
27.     int t = 2*i;
    
28.     if (pan(i,2*i)) {cout << i << t << endl; break;}
    
29.   }
    
30.   return 0;
    
31. }
    

复制代码

a1351468657

1. #include <stdio.h>
   
2. #include <string.h>
   
3. 
   
4. int check_num(int);
   
5. int check_num(int num)
   
6. {
   
7.         int i, j, a[10] = { 0 };
   
8.         j = num;
   
9.         while (j)
   
10.         {
    
11.                 i = j % 10;
    
12.                 if (i == 0)
    
13.                 {
    
14.                         return 0;
    
15.                 }
    
16.                 if (a[i])
    
17.                 {
    
18.                         return 0;
    
19.                 }
    
20.                 j /= 10;
    
21.                 a[i] = 1;
    
22.         }
    
23.         return 1;
    
24. }
    
25. 
    
26. main()
    
27. {
    
28.         char str[20], rts[20];
    
29. 
    
30.         int i, j, k, max = 0;
    
31. 
    
32.         for (i = 5000; i < 10000; i++)
    
33.         {
    
34.                 j = i * 2;
    
35.                 sprintf(str, "%d", i);
    
36.                 sprintf(rts, "%d", j);
    
37.                 strcat(str, rts);
    
38.                 k = atoi(str);
    
39. 
    
40.                 if (check_num(k))
    
41.                 {
    
42.                         max = max > i ? max : i;                       
    
43.                 }
    
44.         }
    
45. 
    
46.         printf("%d", max);
    
47. }

复制代码

9327

B1tetheDust

1. import time as t
   
2. 
   
3. start = t.perf_counter()
   
4. 
   
5. 
   
6. def is_pandigital(a_num):
   
7.     tar = [index for index in range(1, 10)]
   
8.     list_num = [int(each) for each in str(a_num)]
   
9.     if len(list_num) != 9:
   
10.         return False
    
11.     elif tar == list(set(list_num)):
    
12.         return True
    
13. 
    
14. 
    
15. pandigitals = []
    
16. for i in range(2, 10):
    
17.     multiplier = 10 ** (int(9 // i) - 1)
    
18.     while True:
    
19.         res = ''
    
20.         for j in range(1, i + 1):
    
21.             res += str(multiplier * j)
    
22.         res = int(res)
    
23.         if res > 1e9:
    
24.             break
    
25.         elif is_pandigital(res):
    
26.             pandigitals.append(res)
    
27.         multiplier += 1
    
28. 
    
29. print(max(pandigitals))
    
30. print("It costs %f s" % (t.perf_counter() - start))
    

复制代码

932718654
It costs 0.031873 s

mathtimes

1. $ time ./main
   
2. 932718654
   
3. 
   
4. real        0m0.002s
   
5. user        0m0.000s
   
6. sys        0m0.002s

复制代码

1. fn bits(x: u32) -> u32 {
   
2.     let mut x = x;
   
3.     let mut ans = 0;
   
4.     while x != 0 {
   
5.         if x%10 == 0 {
   
6.             return 0;
   
7.         }
   
8.         let y = 1 << (x % 10 - 1);
   
9.         if ans & y != 0 {
   
10.             return 0;
    
11.         }
    
12.         ans |= y;
    
13.         x /= 10;
    
14.     }
    
15.     ans
    
16. }
    
17. 
    
18. fn is_pandigital(x: u32) -> bool {
    
19.     let mut tot = 0;
    
20.     for i in 1..=9 {
    
21.         let b = bits(i*x);
    
22.         if b == 0 || tot & b != 0 {
    
23.             return false;
    
24.         }
    
25.         tot |= b;
    
26.         if tot == 0b111111111 {
    
27.             return true;
    
28.         }
    
29.     }
    
30.     false
    
31. }
    
32. 
    
33. fn pandigital(x: u32) -> u32 {
    
34.     let v = &mut [0;9];
    
35.     let mut vi = 0;
    
36.     let mut i = 1;
    
37.     while vi != 9 {
    
38.         let mut y = x*i;
    
39.         while y != 0 {
    
40.             v[vi] = y / 10u32.pow(y.ilog10());
    
41.             vi += 1;
    
42.             y %= 10u32.pow(y.ilog10());
    
43.         }
    
44.         i += 1;
    
45.     }
    
46.     let mut sum = 0;
    
47.     for i in 0..=8 {
    
48.         sum += v[8-i] * 10u32.pow(i as u32);
    
49.     }
    
50.     sum
    
51. }
    
52. 
    
53. #[cfg(test)]
    
54. mod tests {
    
55.     use super::*;
    
56.     #[test]
    
57.     fn test_is_pandigital() {
    
58.         assert!(is_pandigital(192));
    
59.         assert!(is_pandigital(9));
    
60.         assert!(is_pandigital(1));
    
61.         assert!(!is_pandigital(191));
    
62.     }
    
63.     #[test]
    
64.     fn test_pandigital() {
    
65.         assert_eq!(pandigital(9),918273645);
    
66.         assert_eq!(pandigital(192),192384576);
    
67.     }
    
68. }
    
69. 
    
70. fn main () {
    
71.     // 要使 n > 1, 最多是4位数
    
72.     let v:Vec<u32> = (1..1e5 as u32).filter(|&x| is_pandigital(x)).collect();
    
73.     let p:Vec<u32> = v.into_iter().map(|x| pandigital(x)).collect();
    
74.     println!("{}", p.iter().max().unwrap());
    
75. }

复制代码