Project Euler 42

Problem 42

using System;
using System.Collections.Generic;
using System.IO;
using System.Text.RegularExpressions;
using System.Linq;

class PE042 {
    static bool IsTriangleWord(string word) {
        int sum = word.Select(c => c - 'A' + 1).Sum();

        int n = 0;
        for (int i = 1; ; i++) {
            n += i;
            if (n > sum) return false;
            if (n == sum) return true;
        }
    }
    
    static void Main() {
        string s = File.ReadAllText("../data/words.txt");
        var ss = Regex.Matches(s, "[A-Z]+").Cast<Match>().Select(m => m.Value).ToList();

        int ans = ss.Where(IsTriangleWord).Count();
        Console.WriteLine(ans);
    }
}

任意の自然数 x が三角数かどうか

上のプログラムでは、三角数かどうかを判定するために、一番小さな三角数から順番に調べています。

任意の自然数 x が三角数がどうかは、以下を計算すればいいようです。

これを解くと以下のようになります。

コードを書き直します。

using System;
using System.Collections.Generic;
using System.IO;
using System.Text.RegularExpressions;
using System.Linq;

class PE042 {
    static int SqrtInt(int n) {
        Func<int, int> fn = null; // 無名関数から、この変数を参照するために、まず宣言だけする
        fn = m => {
            int s = (m + n / m) / 2;
            return s >= m ? m : fn(s);
        };
        return fn(n);
    }
    
    static bool IsTriangleWord(string word) {
        int sum = word.Select(c => c - 'A' + 1).Sum();
        
        int x = SqrtInt(1 + 8*sum);
        return x * x == 1 + 8*sum;
    }
    
    static void Main() {
        string s = File.ReadAllText("../data/words.txt");
        var ss = Regex.Matches(s, "[A-Z]+").Cast<Match>().Select(m => m.Value).ToList();

        int ans = ss.Where(IsTriangleWord).Count();
        Console.WriteLine(ans);
    }
}

参考:

• 三角数 - Wikipedia
• ScalaでProject Euler（72） - 桃の天然水

Sage で方程式を解く

n^2 + n - 2t = 0 を Sage - Open-Source Mathematical Software System で解いてみました。

var('n t')
f = n^2 + n - 2*t
solve(f, n)

evaluate すると、結果は以下のようになります。

[n == -1/2*sqrt(8*t + 1) - 1/2, n == 1/2*sqrt(8*t + 1) - 1/2]