125. 回文数之和(Palindromic sums)

回文数\(595\)很有趣,因为它可以表示为连续平方的和\(6^2+7^2+8^2+9^2+10^2+11^2+12^2\)。一千以下的回文数中恰好有十一个可以表示为连续平方的和,而这些回文数的总和为\(4164\)。需要注意的是\(1=0^2+1^2\)并没有包括在内,因为这里我们只关心正整数的平方。找出\(10^8\)以内所有可以被表示成连续平方数之和的回文数,求它们的总和。

分析:要找到符合题目要求的数可有两种思路,一种是找到一个回文数然后看其是否可以表示成连续平方数之和,另一种思路是计算连续平方数之和,再看结果是否是一个回文数。显然后一种思路更加容易处理,而且我们在之前的题目中已经编写过判断一个数是否为回文数的函数,这里可以直接使用。

解题的关键点有两个:一是某些回文数表示成连续平方数的和的方式有几种,因此在计算总和时会重复计算,为了避免这个问题,我们可以用集合来存储符合要求的回文数,避免重复。二是筛选上界问题,即在\(10^8\)的范围内,当一个数\(n\)可以被表示成为连续平方数之和时,数\(n\)最大为多少?显然数\(n\)被表示成为两个平方数之和时,比它被表示成三个及以上平方数之和时,数\(n\)可以取到更大的值。则为求上界只需要解以下不等式:

$$ n^2+(n-1)^2=2n^2-2n+1<10^8\Rightarrow n<7071.57 $$

对于更一般的上界\(N\),我们有:

$$ 2n^2-2n+1<N \Rightarrow n<\sqrt{2N-1}+\frac{1}{2}\approx\sqrt{N/2} $$

代码如下:

# time cost = 224 ms ± 1.35 ms

def is_palindromic(n):
    n = str(n)
    return n == n[::-1]

def main(N=10**8):
    psos = set()
    u = int((N/2)**0.5)
    for i in range(1,u):
        sos = i*i
        while sos < N:
            i += 1
            sos += i*i
            if is_palindromic(sos): 
                psos.add(sos)
    return sum(psos)