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

• Wyverex (12/12) Aug 13 2008 I've yet to try these but they look more challenging!
• Steven Schveighoffer (54/54) Aug 13 2008 I actually found these quite easy :)
• BCS (4/33) Aug 13 2008 nice
• Steven Schveighoffer (21/34) Aug 13 2008 Correction, smallest *prime* factor (which is also the smallest factor) ...
• Wyverex (2/7) Aug 13 2008 Opps sorry its was a copy issue!
• BCS (16/26) Aug 13 2008 233168
• Wyverex (52/72) Aug 13 2008 import tango.io.Stdout;
• Steven Schveighoffer (5/31) Aug 13 2008 1472 is not prime.
• Wyverex (23/32) Aug 13 2008 Wow I messed that up!
• BCS (3/37) Aug 13 2008 that still has a slight error, if the input number has any repeated fact...
• bearophile (41/41) Aug 13 2008 My D solutions using my libs:
• Simen Kjaeraas (53/65) Aug 14 2008 On Wed, 13 Aug 2008 21:12:19 +0200, Wyverex
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
"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;
}

233168
71
200, 375, 425

execution time:

real    0m0.004s
user    0m0.002s
sys     0m0.002s
```
Aug 13 2008
```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
"Steven Schveighoffer" <schveiguy yahoo.com> writes:
```"BCS" wrote
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;
}

6857

new times (pretty much the same):

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

-Steve
```
Aug 13 2008
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
```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
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
"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
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
```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.
```
Aug 13 2008
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
"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