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