www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Puzzle 8-13-2008

reply Wyverex <wyverex.cypher gmail.com> writes:
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.
Aug 13 2008
next sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
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
Aug 13 2008
next sibling parent reply BCS <ao pathlink.com> writes:
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?
Aug 13 2008
parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"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
Aug 13 2008
prev sibling parent Wyverex <wyverex.cypher gmail.com> writes:
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!
Aug 13 2008
prev sibling next sibling parent BCS <ao pathlink.com> writes:
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);
}
Aug 13 2008
prev sibling next sibling parent reply Wyverex <wyverex.cypher gmail.com> writes:
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
Aug 13 2008
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"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
Aug 13 2008
parent reply Wyverex <wyverex.cypher gmail.com> writes:
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
Aug 13 2008
parent BCS <ao pathlink.com> writes:
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
 



 
 //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.
Aug 13 2008
prev sibling next sibling parent bearophile <bearophileHUGS lycos.com> writes:
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
Aug 13 2008
prev sibling parent "Simen Kjaeraas" <simen.kjaras gmail.com> writes:
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
Aug 14 2008