Project Euler/64 - Revision history

Admin: Replacing charlesreid1.com:3000 with git.charlesreid1.com

2019-10-09T03:49:40Z

Replacing charlesreid1.com:3000 with git.charlesreid1.com

← Older revision		Revision as of 03:49, 9 October 2019
Line 7:		Line 7:
	==Also See==		==Also See==

	Blog post: Computing square roots using continued fractions: https://charlesreid1.com~~:3000~~/cs/euler/src/master/scratch/Round2_050-070/063/Problem063.java		Blog post: Computing square roots using continued fractions: https://git.charlesreid1.com/cs/euler/src/master/scratch/Round2_050-070/063/Problem063.java

	Problem 57 (also deals with continued fractions): [[Project Euler/57]]		Problem 57 (also deals with continued fractions): [[Project Euler/57]]
Line 29:		Line 29:
	==Code==		==Code==

	Link: https://charlesreid1.com~~:3000~~/cs/euler/src/master/scratch/Round2_050-070/064		Link: https://git.charlesreid1.com/cs/euler/src/master/scratch/Round2_050-070/064

	ContinuedFractionBig.java defines the ContinuedFractionBig class: https://charlesreid1.com~~:3000~~/cs/euler/src/master/scratch/Round2_050-070/064/ContinuedFractionBig.java		ContinuedFractionBig.java defines the ContinuedFractionBig class: https://git.charlesreid1.com/cs/euler/src/master/scratch/Round2_050-070/064/ContinuedFractionBig.java

	Problem064.java uses the ContinuedFractionBig class to solve the problem: https://charlesreid1.com~~:3000~~/cs/euler/src/master/scratch/Round2_050-070/064/Problem064.java		Problem064.java uses the ContinuedFractionBig class to solve the problem: https://git.charlesreid1.com/cs/euler/src/master/scratch/Round2_050-070/064/Problem064.java

	===Problem 64 Algorithm===		===Problem 64 Algorithm===

2018-01-08T11:03:30Z

← Older revision		Revision as of 11:03, 8 January 2018
Line 4:		Line 4:

	Link: https://projecteuler.net/problem=64		Link: https://projecteuler.net/problem=64

			==Also See==

	Blog post: Computing square roots using continued fractions: https://charlesreid1.com:3000/cs/euler/src/master/scratch/Round2_050-070/063/Problem063.java		Blog post: Computing square roots using continued fractions: https://charlesreid1.com:3000/cs/euler/src/master/scratch/Round2_050-070/063/Problem063.java

			Problem 57 (also deals with continued fractions): [[Project Euler/57]]

	==Solution Technique==		==Solution Technique==

	The blog post linked above contains some of the code used to solve this problem, but it basically boils down to implementing the recurrence relation formula that we already saw in ~~[[Project Euler/~~57]], with various initial conditions.		The blog post linked above contains some of the code used to solve this problem, but it basically boils down to implementing the recurrence relation formula that we already saw in Problem 57, with various initial conditions.

	Continued fractions are implemented as a class. Key functionality includes:		Continued fractions are implemented as a class. Key functionality includes:

2018-01-08T10:43:00Z

Magic Method for Square Roots

← Older revision		Revision as of 10:43, 8 January 2018
Line 30:		Line 30:

	Problem064.java uses the ContinuedFractionBig class to solve the problem: https://charlesreid1.com:3000/cs/euler/src/master/scratch/Round2_050-070/064/Problem064.java		Problem064.java uses the ContinuedFractionBig class to solve the problem: https://charlesreid1.com:3000/cs/euler/src/master/scratch/Round2_050-070/064/Problem064.java

			===Problem 64 Algorithm===

			Skipping the details of the continued fraction representation, here is the essential algorithm for Problem 64. Note that the <code>continuedFractionSqrtBig()</code> method is using an arbitrary precision decimal library to compute many, many terms of the continued fraction representation.

			<pre>
			public class Problem064 {
			public static void main(String[] args) {
			int oddConv = 0;
			for(int j=2; j<=10000; j++) {
			List<Integer> cf;
			try {
			cf = ContinuedFractionBig.continuedFractionSqrtBig(j);
			if(cf.size()%2==0) {
			oddConv++;
			//System.out.println(j+" : "+cf);
			}
			} catch(IllegalArgumentException e) {
			continue;
			}
			}
			System.out.println(oddConv);
			}
			}
			</pre>

	===Magic Method for Square Roots===		===Magic Method for Square Roots===

2018-01-08T10:41:15Z

Code

@@ Line 30: / Line 30: @@
 Problem064.java uses the ContinuedFractionBig class to solve the problem: https://charlesreid1.com:3000/cs/euler/src/master/scratch/Round2_050-070/064/Problem064.java
 ==Flags==
 {{ProjectEulerFlag}}

2018-01-08T10:41:09Z

Magic Method for Square Roots

@@ Line 22: / Line 22: @@
 \dfrac{P_n}{Q_n} = \dfrac{ a_n P_{n-1} + P_{n-2} }{ a_n Q_{n-1} + Q_{n-2} }
 </math>
 ==Code==

2018-01-08T10:40:59Z

Solution Technique

@@ Line 14: / Line 14: @@
 * Check if integer is perfect square
-* Find the continued fraction representation of an integer
+* Solve the Pell equation
 * Find the convergents P, Q of a continued fraction
 <math>
 \dfrac{P_n}{Q_n} = \dfrac{ a_n P_{n-1} + P_{n-2} }{ a_n Q_{n-1} + Q_{n-2} }
 </math>
 ==Code==

2018-01-08T10:37:59Z

Solution Technique

← Older revision		Revision as of 10:37, 8 January 2018
Line 10:		Line 10:

	The blog post linked above contains some of the code used to solve this problem, but it basically boils down to implementing the recurrence relation formula that we already saw in [[Project Euler/57]], with various initial conditions.		The blog post linked above contains some of the code used to solve this problem, but it basically boils down to implementing the recurrence relation formula that we already saw in [[Project Euler/57]], with various initial conditions.

			Continued fractions are implemented as a class. Key functionality includes:

			* Check if integer is perfect square
			* Find the continued fraction representation of an integer
			* Find the convergents P, Q of a continued fraction

			<math>
			\dfrac{P_n}{Q_n} = \dfrac{ a_n P_{n-1} + P_{n-2} }{ a_n Q_{n-1} + Q_{n-2} }
			</math>

	==Code==		==Code==

2018-01-08T10:35:59Z

Code

← Older revision		Revision as of 10:35, 8 January 2018
Line 14:		Line 14:

	Link: https://charlesreid1.com:3000/cs/euler/src/master/scratch/Round2_050-070/064		Link: https://charlesreid1.com:3000/cs/euler/src/master/scratch/Round2_050-070/064

			ContinuedFractionBig.java defines the ContinuedFractionBig class: https://charlesreid1.com:3000/cs/euler/src/master/scratch/Round2_050-070/064/ContinuedFractionBig.java

			Problem064.java uses the ContinuedFractionBig class to solve the problem: https://charlesreid1.com:3000/cs/euler/src/master/scratch/Round2_050-070/064/Problem064.java

	==Flags==		==Flags==

	{{ProjectEulerFlag}}		{{ProjectEulerFlag}}

2018-01-08T10:31:39Z

Solution Technique

← Older revision		Revision as of 10:31, 8 January 2018
Line 8:		Line 8:

	==Solution Technique==		==Solution Technique==

			The blog post linked above contains some of the code used to solve this problem, but it basically boils down to implementing the recurrence relation formula that we already saw in [[Project Euler/57]], with various initial conditions.

	==Code==		==Code==

2018-01-08T10:30:45Z

Problem Statement

← Older revision		Revision as of 10:30, 8 January 2018
Line 1:		Line 1:
	==Problem Statement==		==Problem Statement==

			More investigation of continued fractions and the continued fraction representation of square roots.

	Link: https://projecteuler.net/problem=64		Link: https://projecteuler.net/problem=64

			Blog post: Computing square roots using continued fractions: https://charlesreid1.com:3000/cs/euler/src/master/scratch/Round2_050-070/063/Problem063.java

	==Solution Technique==		==Solution Technique==