# 赏花归去马如飞--关乎回文

2018-04-21

## 1(P4),Largest palindrome product

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

Find the largest palindrome made from the product of two 3-digit numbers.


#include <stdio.h>

int is_palindrome( int number ){
int res = 0;
int n = number;
if ( n < 0 ){
return 0;
}
do{
res = res * 10 + n % 10;
n = n / 10;
} while ( n );

if ( res == number ){
return 1;
}
return 0;
}

int solution(){
int x, y, v, largest_number;
largest_number=0;

for(x = 999; x > 100; x--){
for(y = 999; y > 100; y--){
v = x * y;
if(v > largest_number && is_palindrome(v) == 1){
largest_number = v;
}
}
}
return largest_number;
}

int main(){
return solution();
}


## 2(P36),Double-base palindromes

The decimal number, 585 = 10010010012 (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.)


def huiwen_judge(string):
if str(string) == str(string)[::-1]:
return True
else:
return 0
def jinzhi_change(n):
if n==0:
return '0'
list = ''
while n>=1:
if n%2==0:
list += '0'
else:
list += '1'
n=int(n/2)
return list[::-1]
sum=0
for i in range(1,1000000):
if huiwen_judge(str(i)) and huiwen_judge(jinzhi_change(i)):
sum+=i
print sum


## 3(P55),Lychrel numbers

If we take 47, reverse and add, 47 + 74 = 121, which is palindromic.

Not all numbers produce palindromes so quickly. For example,

349 + 943 = 1292,
1292 + 2921 = 4213
4213 + 3124 = 7337

That is, 349 took three iterations to arrive at a palindrome.

Although no one has proved it yet, it is thought that some numbers, like 196, never produce a palindrome. A number that never forms a palindrome through the reverse and add process is called a Lychrel number. Due to the theoretical nature of these numbers, and for the purpose of this problem, we shall assume that a number is Lychrel until proven otherwise. In addition you are given that for every number below ten-thousand, it will either (i) become a palindrome in less than fifty iterations, or, (ii) no one, with all the computing power that exists, has managed so far to map it to a palindrome. In fact, 10677 is the first number to be shown to require over fifty iterations before producing a palindrome: 4668731596684224866951378664 (53 iterations, 28-digits).

Surprisingly, there are palindromic numbers that are themselves Lychrel numbers; the first example is 4994.

How many Lychrel numbers are there below ten-thousand?

NOTE: Wording was modified slightly on 24 April 2007 to emphasise the theoretical nature of Lychrel numbers.


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

vector<int> findDigits(int n){
vector<int> output;
while(n>0){output.push_back(n%10);n /=10;}
return output;
}

vector<int> output;int length=input.size();
for(int k=0;k<length;++k){output.push_back(input[k]+input[length-1-k]);}

int temp=0;
for(int k=0;k<output.size()-1;++k){if(output[k]>=10){temp=output[k];output[k]=temp%10;output[k+1]+=temp/10;}}
while(output.back()>=10){temp=output.back();output[output.size()-1]=temp%10;output.push_back(temp/10);}

return output;
}

bool isPalindrome(vector<int> input){
//判断是否为回文数
for(int k=0;k<=input.size()/2;++k){if(input[k] != input[input.size()-k-1]){return 0;}}
return 1;
}

int findLychrelNumbers(int upperBound,int iterationBound){
//寻找符合条件的数，最后返回个数
//这儿有两个参数，一个是范围，一个是约束
int iterations, count=upperBound-1;vector<int> data;
for(int k=1;k<upperBound;++k){
iterations=0;data=findDigits(k);
while( (++iterations) < iterationBound){
if(isPalindrome(data)){--count;break;}
}
}
cout << count<<endl;
return count;
}

int main (int argc, char * const argv[]) {

findLychrelNumbers(10000,50);
return 0;
//不得不说C语言写起来太繁琐了
}

def fanzhuan(n):
return int(str(n)[::-1])
count=10000
for num in range(10000):
i = num
for j in range(50):
i += fanzhuan(i)
if i==fanzhuan(i):
count-=1
break
print count
##似乎python写起来简单多了:)


## 4(P125),Palindromic sums

The palindromic number 595 is interesting because it can be written as the sum of consecutive squares: 6^2 + 7^2 + 8^2 + 9^2 + 10^2 + 11^2 + 12^2.

There are exactly eleven palindromes below one-thousand that can be written as consecutive square sums, and the sum of these palindromes is 4164. Note that 1 = 02 + 12 has not been included as this problem is concerned with the squares of positive integers.

Find the sum of all the numbers less than 108 that are both palindromic and can be written as the sum of consecutive squares.

这个题目不简单，主要的难点在于一个整数怎么取特定的数，然后其平方之和为这个整数，解决了这个问题，其他的便好做。这个题目使用函数式编程语言Haskell解决，下面给出代码：

import Data.List ( tails )
import Data.Set ( foldl,fromList )

main = let n = 10^8 in print $Data.Set.foldl (+) 0$ fromList
$filter (\x -> let z = show x in z == reverse z)$ concatMap
(takeWhile (<n) . drop 1 . scanl1 (+)) $tails$ takeWhile
(< div n 2) \$ map (^2) [1..]