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.


2)  The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 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.

I actually found these quite easy :)

BTW, to denote squared, you should use a^2, the way you wrote the third problem had me very confused for a while :)  I thought there was a constraint like: a*10 + 2 + b*10 + 2 == c * 10 + 2.

import tango.io.Stdout;

void prob1()
{
    int s = 0;
    for(int i = 1; i < 1000; i++)
    {
        if(i % 3 == 0 || i % 5 == 0)
            s += i;
    }
    Stdout(s).newline;
}

void prob2()
{
    auto target= 600_851_475_143;
    for(ulong i = 3; i * i < target; i++)
        if(target % i == 0)
        {
            Stdout(i).newline;
            return;
        }
    Stdout(target)(" is prime!").newline;
}

void prob3()
{
    for(int i = 1; i < 1000; i++)
        for(int j = i; i + j < 1000; j++)
        {
            int k = 1000 - i - j;
            if(k < j)
                break;

            if(i * i + j * j == k * k)
            {
                Stdout(i, j, k).newline;
            }
        }
}

void main()
{
    prob1;
    prob2;
    prob3;
}

Answers:
233168
71
200, 375, 425

execution time:

real    0m0.004s
user    0m0.002s
sys     0m0.002s

Reply to wyverex,

> 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.
> 

233168

(took about 2 min with excel

int sum=0;
for(int i = 1; i < 1000; i++) if(!(i%3 && 1%5)) summ += i;

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

6857

import std.stdio;
void main()
{
	long v = 600851475143;
	long i = 2;
	while(i < v)
		if(v%i)	i++;
		else	v/=i;
	writef("%d\n", v);
}

Reply to Steven,

> I actually found these quite easy :)
> 
> BTW, to denote squared, you should use a^2, the way you wrote the
> third problem had me very confused for a while :)  I thought there was
> a constraint like: a*10 + 2 + b*10 + 2 == c * 10 + 2.
> 

ditto, i didn't even bother because of that

> import tango.io.Stdout;
> 
> void prob1()
> {
> int s = 0;
> for(int i = 1; i < 1000; i++)
> {
> if(i % 3 == 0 || i % 5 == 0)
> s += i;
> }
> Stdout(s).newline;
> }

nice

> void prob2()
> {
> auto target= 600_851_475_143;
> for(ulong i = 3; i * i < target; i++)
> if(target % i == 0)
> {
> Stdout(i).newline;
> return;
> }
> Stdout(target)(" is prime!").newline;
> }

doesn't that find the smallest factor?

Wyverex wrote:
> 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.

import tango.io.Stdout;

void main()
{
  int[] list;
  for(int i = 1; i < 1000; i++)
    if( (i % 5 == 0) || (i % 3 == 0) ) list ~= i;

  long sum;
  foreach(i;list) sum += i;

  Stdout(sum).newline;
}

output: 233168

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

import tango.io.Stdout;

T max( T )( T a, T b) { return ( a > b ? a : b ); }

void main()
{
  real i = 600851475143;
  real m = 0;

  real l = 2;
  while(l*l <= i)
  {
    if(i%l == 0)
    {
     m = max(m,l);
     Stdout(l)(" ");
     i /= l;
    }
    ++l;
  }
  Stdout(l).newline;
  m = max(m,l);
  Stdout("Max: ")(cast(long)m).newline;
}

output:
71.00 839.00 1471.00 1472.00
Max:1472

> 
> 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.



import tango.io.Stdout;

void main()
{
  long a, b, c;
  //  0 < a < b < c

  for(c = 1000; c > 0; c--)
    for(b = 1000-c; b > 0; b--)
    {
      a = 1000 - c - b;
      if( a == 0 || a > b || b > c ) continue;
      if((a*a) + (b*b) == (c*c))
        Stdout.formatln("A:{} B:{} C:{}", a,b,c);
    }
}

output:
A:200 B:375 C:425

Steven Schveighoffer wrote:
> I actually found these quite easy :)
> 
> BTW, to denote squared, you should use a^2, the way you wrote the third problem had me very confused for a while :)  I thought there was a constraint like: a*10 + 2 + b*10 + 2 == c * 10 + 2.

Opps sorry its was a copy issue!

"BCS" wrote
> Reply to Steven,
>> void prob2()
>> {
>> auto target= 600_851_475_143;
>> for(ulong i = 3; i * i < target; i++)
>> if(target % i == 0)
>> {
>> Stdout(i).newline;
>> return;
>> }
>> Stdout(target)(" is prime!").newline;
>> }
>
> doesn't that find the smallest factor?

Correction, smallest *prime* factor (which is also the smallest factor) :) Of course, I now realize that I misread the question...

Quick change to my code:

void prob2()
{
    auto target= 600_851_475_143;
    for(ulong i = 3; i * i <= target; i++)
        while(target % i == 0)
        {
            target /= i;
        }
    Stdout(target).newline;
}

New answer to 2:

6857

new times (pretty much the same):

real    0m0.004s
user    0m0.003s
sys     0m0.001s

-Steve

"Wyverex" wrote
>> What is the largest prime factor of the number 600851475143 ?
>>
>
> import tango.io.Stdout;
>
> T max( T )( T a, T b) { return ( a > b ? a : b ); }
>
> void main()
> {
>   real i = 600851475143;
>   real m = 0;
>
>   real l = 2;
>   while(l*l <= i)
>   {
>     if(i%l == 0)
>     {
>      m = max(m,l);
>      Stdout(l)(" ");
>      i /= l;
>     }
>     ++l;
>   }
>   Stdout(l).newline;
>   m = max(m,l);
>   Stdout("Max: ")(cast(long)m).newline;
> }
>
> output:
> 71.00 839.00 1471.00 1472.00
> Max:1472

1472 is not prime.

Hint for doing prime stuff, don't use floating point types :)

Also, the second to last line, taking the max of l and m is questionable.

-Steve

Steven Schveighoffer wrote:
> 
> 1472 is not prime.
> 
> Hint for doing prime stuff, don't use floating point types :)
> 
> Also, the second to last line, taking the max of l and m is questionable.
> 
> -Steve 
> 

Wow I messed that up!

//Proper way I should have done it!!!
import tango.io.Stdout;

void main()
{
  ulong i = 600851475143;
  ulong l = 2;

  while(l*l <= i)
  {
    if(i%l == 0)
    {
     Stdout(l)(" ");
     i /= l;
    }
    ++l;
  }
  Stdout(i).newline;
  Stdout("Max:")(i).newline;
}

Output:
71 839 1471 6857
Max:6857

Reply to wyverex,

> Steven Schveighoffer wrote:
> 
>> 1472 is not prime.
>> 
>> Hint for doing prime stuff, don't use floating point types :)
>> 
>> Also, the second to last line, taking the max of l and m is
>> questionable.
>> 
>> -Steve
>> 
> Wow I messed that up!
> 
> //Proper way I should have done it!!!
> import tango.io.Stdout;
> void main()
> {
> ulong i = 600851475143;
> ulong l = 2;
> while(l*l <= i)
> {
> if(i%l == 0)
> {
> Stdout(l)(" ");
> i /= l;
> }
> ++l;
> }
> Stdout(i).newline;
> Stdout("Max:")(i).newline;
> }
> Output:
> 71 839 1471 6857
> Max:6857

that still has a slight error, if the input number has any repeated factors it will fail.