题目36：求出100万以下所有十进制和二进制表示都是回文的数字之和

欧拉计划

Double-base palindromes

The decimal number, (binary), is palindromic in both bases.

Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2.

(Please note that the palindromic number, in either base, may not include leading zeros.)

题目：

十进制数字 (二进制),可以看出在十进制和二进制下都是回文（从左向右读和从右向左读都一样）。

求 100 万以下所有在十进制和二进制下都是回文的数字之和。

（注意在两种进制下的数字都不包括最前面的 0）

迷雾少年

0:(2)  (10)0
1:(2)1  (10)1
3:(2)11  (10)3
5:(2)101  (10)5
7:(2)111  (10)7
9:(2)1001  (10)9
33:(2)100001  (10)33
99:(2)1100011  (10)99
313:(2)100111001  (10)313
585:(2)1001001001  (10)585
717:(2)1011001101  (10)717
7447:(2)1110100010111  (10)7447
9009:(2)10001100110001  (10)9009
15351:(2)11101111110111  (10)15351
32223:(2)111110111011111  (10)32223
39993:(2)1001110000111001  (10)39993
53235:(2)1100111111110011  (10)53235
53835:(2)1101001001001011  (10)53835
73737:(2)10010000000001001  (10)73737
585585:(2)10001110111101110001  (10)585585

1. #include <iostream>
   
2. #include <string>
   
3. using namespace std;
   
4. string calc(int n)
   
5. {
   
6.         string result;
   
7.         /* 转为二进制 不断取余*/
   
8.         while (n)
   
9.         {
   
10.                 result+=(char)((n%2)+'0');
    
11.                 n/=2;
    
12.         }
    
13.         reverse(result.begin(),result.end());
    
14.         return result;
    
15. 
    
16. }
    
17. /* 是否为回文数字 */
    
18. bool is(string n)
    
19. {
    
20.         char *buf = (char*)n.data();
    
21.        
    
22.         int len = strlen(buf);
    
23.         char *p1,*p2;
    
24.         p1 = buf;
    
25.         p2 = buf + len - 1;
    
26.         while (p1<p2 && *p1 == *p2 )
    
27.         {
    
28.                 p1++;
    
29.                 p2--;
    
30.         }
    
31.    return p1>=p2;
    
32. }
    
33. int main(void)
    
34. {
    
35. 
    
36.         for (int i=0;i<1000000;i++)
    
37.         {
    
38.                 char buf[12];
    
39.                 itoa(i,buf,10);
    
40.                 string str(buf);
    
41.                 if(is(calc(i)) && is(str))
    
42.                 {
    
43.                         std::cout<<i<<":"<<"(2)"<<calc(i)<<"  (10)"<<i<<endl;
    
44.                 }
    
45.         }
    
46.         return 0;
    
47. }

复制代码

愤怒的大头菇

1. def Rec(number):
   
2.       temp = list(number)
   
3.       temp.reverse()
   
4.       tmp = list(number)
   
5.       if temp == tmp:
   
6.             return True
   
7.       return False
   
8.       
   
9. 
   
10. 
    
11. list1=[]
    
12. for i in range(1,1000000):
    
13.       n = str(i)
    
14.       if Rec(n):
    
15.             temp = bin(i)
    
16.             if Rec(str(temp[2:])):
    
17.                   list1.append(i)
    
18. 
    
19. print(sum(list1))

复制代码

结果：872187

芒果加黄桃

1. # encoding:utf-8
   
2. # 寻找100万以下的十进制和二进制都是回文数的数之和
   
3. from time import time
   
4. 
   
5. def euler036(N=1000000):
   
6.     print(sum([i for i in range(1, N + 1) if str(i) == str(i)[::-1] and str(bin(i))[2:] == str(bin(i))[2:][::-1]]))
   
7. if __name__ == '__main__':
   
8.     start = time()
   
9.     euler036(1000000)
   
10.     print('cost %.6f sec' % (time() - start))

复制代码

872187
cost 0.666491 sec

渡风

此代码使用matlab编程
Problem36所用时间为： 0.21198秒
Problem36的答案为： 872187

1. %% Problem36.m
   
2. % 最后编辑时间：17-06-14 22:10
   
3. % 找出100w以下的数使得，其二进制数和十进制数都为回文数，求其和
   
4. % Problem36所用时间为： 0.21198秒
   
5. % Problem36的答案为： 872187
   
6. function Output = Problem36()
   
7. tic
   
8. Output = 0;
   
9. %个位数
   
10. for aa = 1:9
    
11.     if fliplr(num2str(dec2bin(aa))) == num2str(dec2bin(aa))
    
12.         Output = Output + aa;
    
13.     end
    
14. end
    
15. %十位数
    
16. for aa = 1:9
    
17.     if fliplr(num2str(dec2bin(aa*10 + aa))) == num2str(dec2bin(aa*10 + aa))
    
18.         Output = Output + aa*10 + aa;
    
19.     end
    
20. end
    
21. 
    
22. %百位数
    
23. for aa = 1:9
    
24.     for bb = 0:9
    
25.        if fliplr(num2str(dec2bin(aa*100 + bb*10 + aa))) == num2str(dec2bin(aa*100 + bb*10 + aa))
    
26.           Output = Output + aa*100 + bb*10 + aa;
    
27.        end  
    
28.     end
    
29. end
    
30. 
    
31. %千位数
    
32. for aa = 1:9
    
33.     for bb = 0:9
    
34.        if fliplr(num2str(dec2bin(aa*1000 + bb*100 + bb*10 + aa))) == num2str(dec2bin(aa*1000 + bb*100 + bb*10 + aa))
    
35.           Output = Output + aa*1000 + bb*100 + bb*10 + aa;
    
36.        end  
    
37.     end
    
38. end
    
39. 
    
40. %万位数
    
41. for aa = 1:9
    
42.     for bb = 0:9
    
43.         for cc = 0:9
    
44.             if fliplr(num2str(dec2bin(aa*10000 + bb*1000 + cc*100 + bb*10 + aa))) == num2str(dec2bin(aa*10000 + bb*1000 + cc*100 + bb*10 + aa))
    
45.                 Output = Output + aa*10000 + bb*1000 + cc*100 + bb*10 + aa;
    
46.             end
    
47.         end
    
48.     end
    
49. end
    
50. 
    
51. %十万位
    
52. for aa = 1:9
    
53.     for bb = 0:9
    
54.         for cc = 0:9
    
55.             if fliplr(num2str(dec2bin(aa*100000 + bb*10000 + cc*1000 + cc*100 + bb*10 + aa))) == num2str(dec2bin(aa*100000 + bb*10000 + cc*1000 + cc*100 + bb*10 + aa))
    
56.                 Output = Output + aa*100000 + bb*10000 + cc*1000 + cc*100 + bb*10 + aa;
    
57.             end
    
58.         end
    
59.     end
    
60. end
    
61. toc
    
62. disp('此代码使用matlab编程')
    
63. disp(['Problem36所用时间为： ',num2str(toc),'秒'])
    
64. disp(['Problem36的答案为： ',num2str(Output)])

复制代码

Trami

1. import time
   
2. start = time.time()
   
3. 
   
4. c = []
   
5. for i in range(1, 1000000):
   
6.     binary = bin(i)
   
7.     binary = str(binary)
   
8.     i = str(i)
   
9. 
   
10.     if i == i[::-1] and  binary[2:] == binary[::-1].replace('b0', ''):
    
11.         c.append(i)
    
12. print(sum(map(int, c)))
    
13. 
    
14. end = time.time()
    
15. print(end - start)

复制代码

用时0.703022956848

k往事如烟k

1. numList = []
   
2. 
   
3. for num in range(1000000):
   
4.     decNumList = list(str(num))
   
5.     decNumTempList = list(str(num))
   
6.     binNumList = list(str(bin(num))[2:])
   
7.     binNumTempList = list(str(bin(num))[2:])
   
8.     decNumTempList.reverse()
   
9.     binNumTempList.reverse()
   
10.     if decNumList == decNumTempList:
    
11.         if binNumList == binNumTempList:
    
12.             numList.append(num)
    
13. 
    
14. print(sum(numList))

复制代码

872187

王小召

送分题：872187

1. print(sum(num for num in range(1, 1000000) if str(num) == str(num)[::-1] and str(bin(num)).split('b')[1] == str(bin(num)).split('b')[1][::-1]))

复制代码

永恒的蓝色梦想

C++ 44ms

1. #include<iostream>
   
2. using namespace std;
   
3. 
   
4. 
   
5. int main() {
   
6.     int i, j, res = 0, sum = 0;
   
7. 
   
8.     for (i = 1; i < 1000000; i++) {
   
9.         j = i;
   
10. 
    
11.         while (j) {
    
12.             res = (res << 1) | (j & 1);
    
13.             j >>= 1;
    
14.         }
    
15. 
    
16.         if (res == i) {
    
17.             while (res) {
    
18.                 j = j * 10 + res % 10;
    
19.                 res /= 10;
    
20.             }
    
21. 
    
22.             if (j == i) {
    
23.                 sum += i;
    
24.             }
    
25.         }
    
26.         else {
    
27.             res = 0;
    
28.         }
    
29.     }
    
30. 
    
31.     cout << sum << endl;
    
32.     return 0;
    
33. }

复制代码

debuggerzh

872187

Process returned 0 (0x0)   execution time : 0.321 s
Press any key to continue.
利用vector判断回文串

1. #include<iostream>
   
2. #include<vector>
   
3. using namespace std;
   
4. 
   
5. const int M = 1e6;
   
6. vector<int> decimal;
   
7. vector<int> bin;
   
8. 
   
9. bool judge(int x,int base,vector<int> & v){
   
10.   while(x){
    
11.     v.push_back(x % base);
    
12.     x /= base;
    
13.   }
    
14.   int len = v.size();
    
15.   for (int i = 0;i < v.size()/2;i++)
    
16.     if (v[i] != v[len-1-i]) return false;
    
17. 
    
18.   return true;
    
19. }
    
20. 
    
21. int main(){
    
22.   int ans = 0;
    
23.   for (int i = 1;i < M;i++){
    
24.     decimal.clear();
    
25.     bin.clear();
    
26.     if (judge(i,10,decimal) && judge(i,2,bin))  ans += i;
    
27.   }
    
28.   cout << ans << endl;
    
29.   return 0;
    
30. }
    

复制代码

a1351468657

1. #include <stdio.h>
   
2. #include <string.h>
   
3. #include <math.h>
   
4. 
   
5. void reverse(char str[], char rts[]);
   
6. void Dec2bin(int, char []);
   
7. 
   
8. void reverse(char str[], char rts[])//回文
   
9. {
   
10.         int i, j, k;
    
11.         k = strlen(str);
    
12. 
    
13.         for (i = 0, j = k - 1; i < k; i++, j--)
    
14.         {
    
15.                 rts[i] = str[j];
    
16.         }
    
17.         rts[k] = '\0';
    
18. }
    
19. void Dec2bin(int num, char bin[])//十进制转二进制
    
20. {
    
21.         int i = 0, j, k;
    
22.         j = num;
    
23.         while (j)
    
24.         {
    
25.                 k = j % 2;
    
26.                 bin[i++] = k + '0';
    
27.                 j /= 2;               
    
28.         }
    
29.         bin[i] = '\0';
    
30. 
    
31. }
    
32. main()
    
33. {
    
34.         char str[128], rts[128], bin[128];
    
35.         int i, j, k, len, flag = 1, sum = 0;
    
36. 
    
37.         for (i = 1; i < 1000000; i += 2) //由于要二进制回文后也相等，所以只能是偶数
    
38.         {
    
39.                 sprintf(str, "%d", i);
    
40.                 reverse(str, rts);
    
41.                 k = atoi(rts);
    
42.                 if (k == i)
    
43.                 {
    
44.                         Dec2bin(i, bin);
    
45.                         reverse(bin, rts);
    
46.                         len = strlen(bin);
    
47.                         for (j = 0; j < len; j++)
    
48.                         {
    
49.                                 if (bin[j] != rts[j])
    
50.                                 {
    
51.                                         flag = 0;
    
52.                                         break;
    
53.                                 }
    
54.                         }
    
55.                         if (flag)
    
56.                         {
    
57.                                 sum += i;
    
58.                                 printf("%d ", i);
    
59.                         }
    
60.                         flag = 1;
    
61.                 }       
    
62.         }
    
63.         printf("\n%d\n", sum);
    
64. }

复制代码

答案为：
1 3 5 7 9 33 99 313 585 717 7447 9009 15351 32223 39993 53235 53835 73737 585585

总和为：872187

B1tetheDust

1. import time as t
   
2. 
   
3. start = t.perf_counter()
   
4. palindromic_nums = []
   
5. for num in range(1000000):
   
6.     num_str = str(num)
   
7.     num_bin = str(bin(num)).lstrip('0b')
   
8.     if num_str == num_str[::-1] and num_bin == num_bin[::-1]:
   
9.         palindromic_nums.append(num)
   
10. 
    
11. print(palindromic_nums)
    
12. print(sum(palindromic_nums))
    
13. print("It costs %f s" % (t.perf_counter() - start))

复制代码

mathtimes

结果

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

复制代码

两个判断回文的函数

1. fn palindrome(x: u32) -> bool {
   
2.     let mut x = x;
   
3.     let bits: &mut [u8] = &mut [0; 10];
   
4.     let mut i: usize = 0;
   
5.     while x != 0 {
   
6.         bits[i] = (x % 10) as u8;
   
7.         i += 1;
   
8.         x /= 10;
   
9.     }
   
10.     for j in 0..=i / 2 {
    
11.         if bits[j] != bits[i - 1 - j] {
    
12.             return false;
    
13.         }
    
14.     }
    
15.     true
    
16. }
    
17. 
    
18. fn palindrome2(x: u32) -> bool {
    
19.     let len = u32::BITS - x.leading_zeros();
    
20.     for j in 0..len / 2 {
    
21.         if ((x >> j) ^ (x >> (len - 1 - j))) & 1 != 0 {
    
22.             return false;
    
23.         }
    
24.     }
    
25.     true
    
26. }
    
27. 
    
28. #[cfg(test)]
    
29. mod tests {
    
30.     use super::*;
    
31.     #[test]
    
32.     fn test_palindrome() {
    
33.         assert!(palindrome(123321));
    
34.         assert!(palindrome(12321));
    
35.         assert!(!palindrome(2321));
    
36.         assert!(palindrome(1));
    
37.         assert!(palindrome(585));
    
38.     }
    
39.     #[test]
    
40.     fn test_palindrome2() {
    
41.         assert!(palindrome2(0b101101));
    
42.         assert!(palindrome2(0b101));
    
43.         assert!(!palindrome2(0b1010));
    
44.         assert!(palindrome2(0b1));
    
45.         assert!(palindrome2(585));
    
46.     }
    
47. }

复制代码

主程序

1. fn main() {
   
2.     let mut sum = 0;
   
3.     for i in 1..1e6 as u32 {
   
4.         if palindrome2(i) && palindrome(i) {
   
5.             sum += i;
   
6.         }
   
7.     }
   
8.     println!("{sum}");
   
9. }

复制代码