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

On Wed, 13 Aug 2008 21:12:19 +0200, Wyverex <wyverex.cypher@gmail.com> wrote:

A bit late, I know.

> I've yet to try these but they look more challenging!
>
>
> 1)  If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
>
> Find the sum of all the multiples of 3 or 5 below 1000.

uint sumDivisible(uint upTo, uint factor)
{
	return sumTo(upTo / factor) * factor;
}

uint sumTo(uint x)
{
	return x * (x + 1) / 2;
}

void main()
{
	writefln(sumDivisible(1000, 3) + sumDivisible(1000, 5) - sumDivisible(1000, 15));
}

> 2)  The prime factors of 13195 are 5, 7, 13 and 29.
>
> What is the largest prime factor of the number 600851475143 ?

ulong highestPrimeFactor(ulong n)
{
	for (long nRoot = cast(ulong)sqrt(cast(real)n); nRoot > 1; nRoot--)
	{
		if (n % nRoot == 0)
		{
			if (!highestPrimeFactor(nRoot))
				return nRoot;
		}
	}
	return 0; // Error code. 0 is definately not a factor.
}

void main()
{
	writefln(highestPrimeFactor(600851475143));
}

> 3)  A Pythagorean triplet is a set of three natural numbers, a  b  c, for which,
> a2 + b2 = c2
>
> For example, 32 + 42 = 9 + 16 = 25 = 52.
>
> There exists exactly one Pythagorean triplet for which a + b + c = 1000.
> Find the product abc.

A simple solution:

a = 0
b = 500
c = 500

Depending on your definition of natural numbers, this may or may not be correct.

Naive (and probably what you meant) solution:

void main()
{
	for (int a = 1; a < 500; a++)
	{
		for (int b = 1; b < min(1000 - a, a); b++)
		{
			int c = 1000 - a - b;
			if (a * a + b * b == c * c)
				writefln(a * b * c);
		}
	}
}

-- 
Simen