Puzzle 8-13-2008

[bearophile]

My D solutions using my libs:

import d.all, std.math;

void main() {
    // 1) -----------------------
    putr(sum(xfilter( (int x){return !(x % 3) || !(x % 5);}, xrange(1, 1000) )));

    // 2) -----------------------
    //long n = 10000004400000259;
    long n = 600_851_475_143;
    OUTER:
        foreach (p; xprimes(cast(long)sqrt(cast(real)n)))
            while (!(n % p)) {
                if (n == p)
                    break OUTER;
                n /= p;
            }
    putr(n);

    // 3) -----------------------
    auto xnumbers = xrange(1, 1_000);
    auto squares = map((int x){return x * x;}, xnumbers);
    auto squares_set = new int[24_593]; // this is fit for 1..10000

    int[int] sqs;
    foreach (i, x; squares)
        sqs[x] = i + 1;

    foreach (sq; squares)
        squares_set[sq % squares_set.length] = sq;

    int ntriples;

    OUTER2:
        foreach (i, aa; squares[0 .. $-1])
            foreach (bb; squares[i+1 .. $]) {
                int cc = squares_set[(aa + bb) % squares_set.length];
                if ((aa + bb) == cc && (sqs[aa] + sqs[bb] + sqs[cc] == 1000)) {
                    putr(sqs[aa], " ", sqs[bb], " ", sqs[cc]);
                    break OUTER2;
                }
            }
}

The first solution is just a filtering, all operations are lazy.

The second solution uses a fast Sieve, and just divides by successive prime numbers. For example if n = 10000004400000259 it finds the solution (100000037) with a total running time (of the 3 solutions) of about 0.36 s on my PC.

The third solution is over engineered for this problem, time ago I have seen that squares of pitagorean triples create a natural hash function, so the third solution is very fast (takes about 3-4 seconds even if n=10_000). The handmade hash is designed for squares up to 10_000 so for this situation it can be made smaller. In C compiled with GCC this third parts runs about 2.2 times faster than the same part compiled with DMD.

Bye,
bearophile