ThatDonGuy
Joined: Jun 22, 2011
• Posts: 3398
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
Joined: Dec 28, 2014
• Posts: 2402
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
Joined: Feb 11, 2014
• Posts: 7360
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.
It's a piece of cake to bake a pretty cake. If the way is hazy. You gotta do the cookin' by the book. You know you can't be lazy. Never use a messy recipe. The cake will end up crazy. If you do the cookin' by the book. Then you'll have a... Break it down! Lemme see you bake it up! Drop that down low and pick that up. Break it down! Lemme see you bake it up! Drop that down low and pick that up Now back that Hey! Now back that. Hey! Now bake that. Hey! Now bake that. Hey! It's a piece of cake to bake a pretty cake (WHAT!) If the way is hazy (OKAY!) You gotta do the cookin' by the book, (WHAT!) You know you can't be lazy (YEAH!) Never use a messy recipe, (WHAT!) The cake will end up crazy (OKAY!) If you do the cookin' by the book, (YEEAAHHHH!) Then you'll have a...cake! Rub that, it's yours! Grab this, it's yours! Rub that, it's yours! Grab this, it's yours! Now turn around, put that on. Grind, make it get a little bigger! Now turn around, put that on. Grind, make it get a little bigger! You gotta do the cookin' by the book! HEY!
gamerfreak
Joined: Dec 28, 2014
• Posts: 2402
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
Joined: Feb 11, 2014
• Posts: 7360
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.
It's a piece of cake to bake a pretty cake. If the way is hazy. You gotta do the cookin' by the book. You know you can't be lazy. Never use a messy recipe. The cake will end up crazy. If you do the cookin' by the book. Then you'll have a... Break it down! Lemme see you bake it up! Drop that down low and pick that up. Break it down! Lemme see you bake it up! Drop that down low and pick that up Now back that Hey! Now back that. Hey! Now bake that. Hey! Now bake that. Hey! It's a piece of cake to bake a pretty cake (WHAT!) If the way is hazy (OKAY!) You gotta do the cookin' by the book, (WHAT!) You know you can't be lazy (YEAH!) Never use a messy recipe, (WHAT!) The cake will end up crazy (OKAY!) If you do the cookin' by the book, (YEEAAHHHH!) Then you'll have a...cake! Rub that, it's yours! Grab this, it's yours! Rub that, it's yours! Grab this, it's yours! Now turn around, put that on. Grind, make it get a little bigger! Now turn around, put that on. Grind, make it get a little bigger! You gotta do the cookin' by the book! HEY!
gamerfreak
Joined: Dec 28, 2014
• Posts: 2402
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
Joined: May 10, 2011
• Posts: 1587
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
Joined: Jun 22, 2011
• Posts: 3398
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
Joined: Dec 28, 2014
• Posts: 2402
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
Joined: Dec 28, 2014
• Posts: 2402
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.