042. 编码三角数(coded triangle numbers)

三角数数列的第\(n\)项可以通过公式\(t_n=n(n+1)/2\)来确定,所以前十个三角数分别为:

$$ 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ... $$
通过把一个单词中的每个字母转化为其在字母表中的位置序数,并将这些数相加可以形成一个单词值。例如,单词SKY的单词值为\(19 + 11 + 25 = 55 =t_{10}\)。如果一个单词的单词值是一个三角数,我们就称这个单词是三角单词。

在题目给出的words.txt这个16K的文本文件中有单约两千个单词,这些单词中有多少个是三角词?

分析:这道题相对容易,首先我们需要编写一个函数计算每个单词对应的单词值,首先计算字母在字母表的序数值,这里使用了内置函数ord(),它可以计算字符对应的ASCII值,用特定字母的ASCII值减去字母A的ASCII值即为该字母在字母表的顺序值,然后将这些顺序值加总起来即为每个单词的单词值。在计算出单词值后,如何判断其是否为一个三角数?

假设计算出的单词值是\(t\),则将其代入三角数的通项公式,则\(t=n(n+1)/2\),则解此二次方程并略去负数项,我们可以得到:

$$ n=\frac{-1+\sqrt{1+8t}}{2} $$

因此当且仅当\(\sqrt{1+8t}\equiv1(mod\ 2)\)时,\(n\)是一个正整数,满足题目的要求。我们根据这个条件对单词值进行筛选,统计筛选后满足条件的单词数量,即为所求。

from math import sqrt

def alphabet(word):
    alpha = lambda s : ord(s) - ord('A') + 1
    res = sum([alpha(x) for x in word])
    return res

def main():
    with open('euler/ep42.txt','r') as f:
        data = f.read().replace('"',"").split(',')
    word_value = [alphabet(x) for x in data]
    res = [x for x in word_value if sqrt(1+8*x)%2==1]
    return len(res)