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.
- 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
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
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
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 thatimport 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; }nicevoid 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> "BCS" wroteReply to Steven,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 -Stevevoid 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 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 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: 2331682) 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:14723) 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
"Wyverex" wrote1472 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. -SteveWhat 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
Aug 13 2008
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. -SteveWow 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:that still has a slight error, if the input number has any repeated factors it will fail.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. -SteveWow 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
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
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