题目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

#include <iostream>
#include <string>
using namespace std;
string calc(int n)
{
        string result;
        /* 转为二进制 不断取余*/
        while (n)
        {
                result+=(char)((n%2)+'0');
                n/=2;
        }
        reverse(result.begin(),result.end());
        return result;

}
/* 是否为回文数字 */
bool is(string n)
{
        char *buf = (char*)n.data();
        
        int len = strlen(buf);
        char *p1,*p2;
        p1 = buf;
        p2 = buf + len - 1;
        while (p1<p2 && *p1 == *p2 )
        {
                p1++;
                p2--;
        }
   return p1>=p2;
}
int main(void)
{

        for (int i=0;i<1000000;i++)
        {
                char buf[12];
                itoa(i,buf,10);
                string str(buf);
                if(is(calc(i)) && is(str))
                {
                        std::cout<<i<<":"<<"(2)"<<calc(i)<<"  (10)"<<i<<endl;
                }
        }
        return 0;
}

愤怒的大头菇

def Rec(number):
      temp = list(number)
      temp.reverse()
      tmp = list(number)
      if temp == tmp:
            return True
      return False 
      


list1=[]
for i in range(1,1000000):
      n = str(i)
      if Rec(n):
            temp = bin(i)
            if Rec(str(temp[2:])):
                  list1.append(i)

print(sum(list1))

结果：872187

芒果加黄桃

# encoding:utf-8
# 寻找100万以下的十进制和二进制都是回文数的数之和
from time import time

def euler036(N=1000000):
    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]]))
if __name__ == '__main__':
    start = time() 
    euler036(1000000)
    print('cost %.6f sec' % (time() - start))

872187
cost 0.666491 sec

渡风

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

%% Problem36.m
% 最后编辑时间：17-06-14 22:10
% 找出100w以下的数使得，其二进制数和十进制数都为回文数，求其和
% Problem36所用时间为： 0.21198秒
% Problem36的答案为： 872187
function Output = Problem36()
tic
Output = 0;
%个位数
for aa = 1:9
    if fliplr(num2str(dec2bin(aa))) == num2str(dec2bin(aa))
        Output = Output + aa;
    end
end
%十位数
for aa = 1:9
    if fliplr(num2str(dec2bin(aa*10 + aa))) == num2str(dec2bin(aa*10 + aa))
        Output = Output + aa*10 + aa;
    end
end

%百位数
for aa = 1:9
    for bb = 0:9
       if fliplr(num2str(dec2bin(aa*100 + bb*10 + aa))) == num2str(dec2bin(aa*100 + bb*10 + aa))
          Output = Output + aa*100 + bb*10 + aa;
       end  
    end
end

%千位数
for aa = 1:9
    for bb = 0:9
       if fliplr(num2str(dec2bin(aa*1000 + bb*100 + bb*10 + aa))) == num2str(dec2bin(aa*1000 + bb*100 + bb*10 + aa))
          Output = Output + aa*1000 + bb*100 + bb*10 + aa;
       end  
    end
end

%万位数
for aa = 1:9
    for bb = 0:9
        for cc = 0:9
            if fliplr(num2str(dec2bin(aa*10000 + bb*1000 + cc*100 + bb*10 + aa))) == num2str(dec2bin(aa*10000 + bb*1000 + cc*100 + bb*10 + aa))
                Output = Output + aa*10000 + bb*1000 + cc*100 + bb*10 + aa;
            end 
        end
    end
end

%十万位
for aa = 1:9
    for bb = 0:9
        for cc = 0:9
            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))
                Output = Output + aa*100000 + bb*10000 + cc*1000 + cc*100 + bb*10 + aa;
            end 
        end
    end
end
toc
disp('此代码使用matlab编程')
disp(['Problem36所用时间为： ',num2str(toc),'秒'])
disp(['Problem36的答案为： ',num2str(Output)])

Trami

import time
start = time.time()

c = []
for i in range(1, 1000000):
    binary = bin(i)
    binary = str(binary)
    i = str(i)

    if i == i[::-1] and  binary[2:] == binary[::-1].replace('b0', ''):
        c.append(i)
print(sum(map(int, c)))

end = time.time()
print(end - start)

用时0.703022956848

k往事如烟k

numList = []

for num in range(1000000):
    decNumList = list(str(num))
    decNumTempList = list(str(num))
    binNumList = list(str(bin(num))[2:])
    binNumTempList = list(str(bin(num))[2:])
    decNumTempList.reverse()
    binNumTempList.reverse()
    if decNumList == decNumTempList:
        if binNumList == binNumTempList:
            numList.append(num)

print(sum(numList))

872187

王小召

送分题：872187

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

#include<iostream>
using namespace std;


int main() {
    int i, j, res = 0, sum = 0;

    for (i = 1; i < 1000000; i++) {
        j = i;

        while (j) {
            res = (res << 1) | (j & 1);
            j >>= 1;
        }

        if (res == i) {
            while (res) {
                j = j * 10 + res % 10;
                res /= 10;
            }

            if (j == i) {
                sum += i;
            }
        }
        else {
            res = 0;
        }
    }

    cout << sum << endl;
    return 0;
}

debuggerzh

872187

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

#include<iostream>
#include<vector>
using namespace std;

const int M = 1e6;
vector<int> decimal;
vector<int> bin;

bool judge(int x,int base,vector<int> & v){
  while(x){
    v.push_back(x % base);
    x /= base;
  }
  int len = v.size();
  for (int i = 0;i < v.size()/2;i++)
    if (v[i] != v[len-1-i]) return false;

  return true;
}

int main(){
  int ans = 0;
  for (int i = 1;i < M;i++){
    decimal.clear();
    bin.clear();
    if (judge(i,10,decimal) && judge(i,2,bin))  ans += i;
  }
  cout << ans << endl;
  return 0;
}

a1351468657

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

void reverse(char str[], char rts[]);
void Dec2bin(int, char []);

void reverse(char str[], char rts[])//回文
{
        int i, j, k;
        k = strlen(str);

        for (i = 0, j = k - 1; i < k; i++, j--)
        {
                rts[i] = str[j];
        }
        rts[k] = '\0';
}
void Dec2bin(int num, char bin[])//十进制转二进制
{
        int i = 0, j, k;
        j = num;
        while (j)
        {
                k = j % 2;
                bin[i++] = k + '0';
                j /= 2;                
        }
        bin[i] = '\0';

}
main()
{
        char str[128], rts[128], bin[128];
        int i, j, k, len, flag = 1, sum = 0;

        for (i = 1; i < 1000000; i += 2) //由于要二进制回文后也相等，所以只能是偶数
        {
                sprintf(str, "%d", i);
                reverse(str, rts);
                k = atoi(rts);
                if (k == i)
                {
                        Dec2bin(i, bin);
                        reverse(bin, rts);
                        len = strlen(bin);
                        for (j = 0; j < len; j++)
                        {
                                if (bin[j] != rts[j])
                                {
                                        flag = 0;
                                        break;
                                }
                        }
                        if (flag)
                        {
                                sum += i;
                                printf("%d ", i);
                        }
                        flag = 1;
                }        
        }
        printf("\n%d\n", sum);
}

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

总和为：872187

B1tetheDust

import time as t

start = t.perf_counter()
palindromic_nums = []
for num in range(1000000):
    num_str = str(num)
    num_bin = str(bin(num)).lstrip('0b')
    if num_str == num_str[::-1] and num_bin == num_bin[::-1]:
        palindromic_nums.append(num)

print(palindromic_nums)
print(sum(palindromic_nums))
print("It costs %f s" % (t.perf_counter() - start))

mathtimes

结果

$ time ./main
872187

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

两个判断回文的函数

fn palindrome(x: u32) -> bool {
    let mut x = x;
    let bits: &mut [u8] = &mut [0; 10];
    let mut i: usize = 0;
    while x != 0 {
        bits[i] = (x % 10) as u8;
        i += 1;
        x /= 10;
    }
    for j in 0..=i / 2 {
        if bits[j] != bits[i - 1 - j] {
            return false;
        }
    }
    true
}

fn palindrome2(x: u32) -> bool {
    let len = u32::BITS - x.leading_zeros();
    for j in 0..len / 2 {
        if ((x >> j) ^ (x >> (len - 1 - j))) & 1 != 0 {
            return false;
        }
    }
    true
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_palindrome() {
        assert!(palindrome(123321));
        assert!(palindrome(12321));
        assert!(!palindrome(2321));
        assert!(palindrome(1));
        assert!(palindrome(585));
    }
    #[test]
    fn test_palindrome2() {
        assert!(palindrome2(0b101101));
        assert!(palindrome2(0b101));
        assert!(!palindrome2(0b1010));
        assert!(palindrome2(0b1));
        assert!(palindrome2(585));
    }
}

主程序

fn main() {
    let mut sum = 0;
    for i in 1..1e6 as u32 {
        if palindrome2(i) && palindrome(i) {
            sum += i;
        }
    }
    println!("{sum}");
}