Puzzle 8-13-2008

Simen Kjaeraas simen.kjaras at gmail.com
Thu Aug 14 18:25:18 PDT 2008


On Wed, 13 Aug 2008 21:12:19 +0200, Wyverex <wyverex.cypher at 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


More information about the Digitalmars-d-learn mailing list