Project Euler [Problem 42]

平日は難しい

うー

問題

Coded triangle numbers

The nth term of the sequence of triangle numbers is given by, tn = \frac{n(n+1)}{2}; so the first ten triangle numbers are:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

By converting each letter in a word to a number corresponding to its alphabetical position and adding these values we form a word value. For example, the word value for SKY is 19 + 11 + 25 = 55 = t_{10}. If the word value is a triangle number then we shall call the word a triangle word.

Using words.txt (right click and 'Save Link/Target As...'), a 16K text file containing nearly two-thousand common English words, how many are triangle words?

私訳

コード化された三角数

三角数の第 n 項は t_n = \frac{n(n+1)}{2} で与えられる。 したがって最初の10個の三角数は:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

単語の各文字を、そのアルファベット上の位置の数字として足し合わせたものを「単語価 word value」とする。 単語価が三角数なら、その単語を「三角語 triangle word」と呼ぶ

words.txt に含まれるほぼ 2000語 の英単語のリストを用いて、その中にいくつ三角語が含まれるか求めよ。

解答方針

単語価を決定するのは難しくないから、あとは三角数の判定を如何に行うかだ。 求めたいのは n であり、特定の式が整数になることを確認できればよい。 候補を k とすると、 k = \frac{n(n+1)}{2} ならば 2k = n^2+n = (n+\frac{1}{2})^2-\frac{1}{4} したがって 8k+1 = (2n+1)^2, n について解けば n = \frac{\sqrt{8k+1} - 1}{2}