ThatDonGuy
ThatDonGuy
Joined: Jun 22, 2011
  • Threads: 78
  • Posts: 3334
October 27th, 2017 at 6:55:51 PM permalink
Quote: gamerfreak

It looks like Wolfram Alpha uses the Rabin-Miller test: http://mathworld.wolfram.com/PrimalityTest.html

I'm not sure how they do it so fast on their engine. Maybe they have precalculated tables? There doesn't seem to be a limit to how many digits you can enter, though.


I am not sure, but I think it tries a "fast" method of some sort. I entered 9,223,372,036,854,775,783 (which is 263 - 25), and it answered that it was prime quickly. It could be brute force, as it does return factorizations of nonprimes, but there are over 50 million primes less than 1 billion, so it would have to divide by each one of those, and even then, it may not work if the number is more than 1018.
gamerfreak
gamerfreak
Joined: Dec 28, 2014
  • Threads: 38
  • Posts: 2209
October 31st, 2017 at 6:55:12 AM permalink
Prime challenge is still open (or any other if you can do better). It's a very difficult problem to solve once you get into big numbers.

A Pythagorean triplet is a set of three natural numbers where a < b < c, for which a^2 + b^2 = c^2

For example:
3^2 + 4^2 = 9 + 16 = 25 = 5^2.

There exists exactly one Pythagorean triplet for which a + b + c = 1000.

Find the product abc.
Last edited by: gamerfreak on Oct 31, 2017
RS
RS 
Joined: Feb 11, 2014
  • Threads: 54
  • Posts: 6928
October 31st, 2017 at 8:00:52 AM permalink
Bruh, you should write x^2 instead of x2. Makes comprehending this much easier....assuming that's what you mean.

Is this the proper interpretation of the "For example:"

3^2 + 4^2 = 9 + 16 = 25 and that's equal to 5^2 ?

ie: a, b, c = 3, 4, 5 respectively?

Also, should use QUOTE or even SPOILER instead of CODE, because on some of the challenges you have to scroll right to read rest of description.
#TeamNathan
gamerfreak
gamerfreak
Joined: Dec 28, 2014
  • Threads: 38
  • Posts: 2209
October 31st, 2017 at 8:09:02 AM permalink
Quote: RS

Bruh, you should write x^2 instead of x2. Makes comprehending this much easier....assuming that's what you mean.

Is this the proper interpretation of the "For example:"

3^2 + 4^2 = 9 + 16 = 25 and that's equal to 5^2 ?

ie: a, b, c = 3, 4, 5 respectively?

Also, should use QUOTE or even SPOILER instead of CODE, because on some of the challenges you have to scroll right to read rest of description.


My bad, copy and paste got me on the squares, I edited.

And damn how small is your screen? I formatted so it even shows up on my phone without scrolling. BUT HAVE IT YOUR WAY, it's in a spoiler now.
RS
RS 
Joined: Feb 11, 2014
  • Threads: 54
  • Posts: 6928
October 31st, 2017 at 8:16:14 AM permalink
I said SOME of the previous challenges, ie: challenge #1.

And putting it in CODE within a SPOILER doesn't halp. Obvii in this case it doesn't matter b/c he's not too long, width-wise. But the earlier ones would still be wonky.
#TeamNathan
gamerfreak
gamerfreak
Joined: Dec 28, 2014
  • Threads: 38
  • Posts: 2209
October 31st, 2017 at 8:19:07 AM permalink
Quote: RS

I said SOME of the previous challenges, ie: challenge #1.

And putting it in CODE within a SPOILER doesn't halp. Obvii in this case it doesn't matter b/c he's not too long, width-wise. But the earlier ones would still be wonky.


It's all fixed and I'll do it that way from now on. Now go solve it.
CrystalMath
CrystalMath
Joined: May 10, 2011
  • Threads: 8
  • Posts: 1547
October 31st, 2017 at 9:58:39 AM permalink

a=200
b=375
c=425
a*b*c=31875000


public class FindPythagoreanTriplets {

public static void main(String[] args) {
new FindPythagoreanTriplets();
}

public FindPythagoreanTriplets() {
boolean solutionFound = false;
int a = 3;
int b = 0;
int c = 0;

while (1000 % (a + b + c) >0) {
a++;
if (a % 2 == 0) // even
{
b = a * a / 4 - 1;
c = b + 2;
} else {
b = (a * a - 1) / 2;
c = b + 1;
}
}
int mult = 1000 / (a + b + c);
a *= mult;
b *= mult;
c *= mult;
System.out.println(a + " " + b + " " + c + " " + a * b * c);
}
}

I heart Crystal Math.
ThatDonGuy
ThatDonGuy
Joined: Jun 22, 2011
  • Threads: 78
  • Posts: 3334
October 31st, 2017 at 10:01:13 AM permalink
Quote: gamerfreak

Prime challenge is still open (or any other if you can do better). It's a very difficult problem to solve once you get into big numbers.

A Pythagorean triplet is a set of three natural numbers where a < b < c, for which a^2 + b^2 = c^2

For example:
3^2 + 4^2 = 9 + 16 = 25 = 5^2.

There exists exactly one Pythagorean triplet for which a + b + c = 1000.

Find the product abc.



Sometimes, just some good old-fashioned math will do.

C = 1000 - (A + B)
A^2 + B^2 = C^2 = (1000 - (A + B))^2
A^2 + B^2 = 1,000,000 - 2000 A - 2000 B + A^2 + 2AB + B^2
0 = 1,000,000 - 2000 A - 2000 B + 2AB
1000 A + 1000 B = 500,000 + AB
This means AB is a multiple of 1000

1000 B - AB = 500,000 - 1000 A
B = (500,000 - 1000 A) / (1000 - A)
= 1000 (500 - A) / (1000 - A)
= 1000 ((1000 - A) - 500) / (1000 - A)
= 1000 - 500,000 / (1000 - A)
(1000 - A) must be a factor of 500,000
Also, 500,000 / (1000 - A) < 1000, as otherwise B <= 0
This means 500,000 < 1,000,000 - 1000 A
1000 A < 500,000
A < 500
1000 - A > 500

The only integers between 500 and 1000 that are factors of 500,000 = 2^5 x 5^6 are 625 and 800
1000 - A = 625 -> A = 375 -> B = 200, but A < B is given
1000 - A = 800 -> A = 200 -> B = 375 -> C = 425
200^2 + 375^2 = 40,000 + 140,625 = 180,625 = 425^2 = (1000 - (200 + 375))^2

gamerfreak
gamerfreak
Joined: Dec 28, 2014
  • Threads: 38
  • Posts: 2209
November 8th, 2017 at 8:48:15 AM permalink
Quote: CrystalMath


a=200
b=375
c=425
a*b*c=31875000


public class FindPythagoreanTriplets {

public static void main(String[] args) {
new FindPythagoreanTriplets();
}

public FindPythagoreanTriplets() {
boolean solutionFound = false;
int a = 3;
int b = 0;
int c = 0;

while (1000 % (a + b + c) >0) {
a++;
if (a % 2 == 0) // even
{
b = a * a / 4 - 1;
c = b + 2;
} else {
b = (a * a - 1) / 2;
c = b + 1;
}
}
int mult = 1000 / (a + b + c);
a *= mult;
b *= mult;
c *= mult;
System.out.println(a + " " + b + " " + c + " " + a * b * c);
}
}


Correct answer. However I believe there is a more efficient solution using Primitive Triplets and Parametrization.

Quote: ThatDonGuy

Quote: gamerfreak

Prime challenge is still open (or any other if you can do better). It's a very difficult problem to solve once you get into big numbers.

A Pythagorean triplet is a set of three natural numbers where a < b < c, for which a^2 + b^2 = c^2

For example:
3^2 + 4^2 = 9 + 16 = 25 = 5^2.

There exists exactly one Pythagorean triplet for which a + b + c = 1000.

Find the product abc.



Sometimes, just some good old-fashioned math will do.

C = 1000 - (A + B)
A^2 + B^2 = C^2 = (1000 - (A + B))^2
A^2 + B^2 = 1,000,000 - 2000 A - 2000 B + A^2 + 2AB + B^2
0 = 1,000,000 - 2000 A - 2000 B + 2AB
1000 A + 1000 B = 500,000 + AB
This means AB is a multiple of 1000

1000 B - AB = 500,000 - 1000 A
B = (500,000 - 1000 A) / (1000 - A)
= 1000 (500 - A) / (1000 - A)
= 1000 ((1000 - A) - 500) / (1000 - A)
= 1000 - 500,000 / (1000 - A)
(1000 - A) must be a factor of 500,000
Also, 500,000 / (1000 - A) < 1000, as otherwise B <= 0
This means 500,000 < 1,000,000 - 1000 A
1000 A < 500,000
A < 500
1000 - A > 500

The only integers between 500 and 1000 that are factors of 500,000 = 2^5 x 5^6 are 625 and 800
1000 - A = 625 -> A = 375 -> B = 200, but A < B is given
1000 - A = 800 -> A = 200 -> B = 375 -> C = 425
200^2 + 375^2 = 40,000 + 140,625 = 180,625 = 425^2 = (1000 - (200 + 375))^2


¯\_(ツ)_/¯

I can code but I'm terrible at math :(
gamerfreak
gamerfreak
Joined: Dec 28, 2014
  • Threads: 38
  • Posts: 2209
March 21st, 2018 at 10:25:55 AM permalink
Here is a fun one:


Consider the fraction, n/d, where n and d are positive integers. If n<d and HCF(n,d)=1, it is called a reduced proper fraction.

If we list the set of reduced proper fractions for d ≤ 8 in ascending order of size, we get:

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8

It can be seen that 2/5 is the fraction immediately to the left of 3/7.

By listing the set of reduced proper fractions for d ≤ 1,000,000 in ascending order of size, find the numerator of the fraction immediately to the left of 3/7.


  • Jump to: