Project Euler/64
From charlesreid1
Contents
Problem Statement
More investigation of continued fractions and the continued fraction representation of square roots.
Link: https://projecteuler.net/problem=64
Also See
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
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 Problem 57, with various initial conditions.
Continued fractions are implemented as a class. Key functionality includes:
- Check if integer is perfect square
- Solve the Pell equation
- Find the convergents P, Q of a continued fraction
- Find the (shorter than 10-long) continued fraction representation of an integer (uses normal float type)
- Find the (really long) continued fraction representation of an integer (uses arbitrary precision BigDecimal type)
Code
Link: https://git.charlesreid1.com/cs/euler/src/master/scratch/Round2_050-070/064
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://git.charlesreid1.com/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 continuedFractionSqrtBig()
method is using an arbitrary precision decimal library to compute many, many terms of the continued fraction representation.
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); } }
Magic Method for Square Roots
In the process of implementing this, I needed to compute square roots to arbitrary precision - something that BigDecimal does NOT do!
I found this (magical) arbitrary precision BigDecimal square root algorithm that is extremely handy:
/** Find the square root of a BigDecimal to precision SCALE. */ public static BigDecimal sqrtBig(BigDecimal A, final int SCALE) { BigDecimal x0 = new BigDecimal("0"); BigDecimal x1 = new BigDecimal(Math.sqrt(A.doubleValue())); while (!x0.equals(x1)) { x0 = x1; x1 = A.divide(x0, SCALE, RoundingMode.HALF_UP); x1 = x1.add(x0); x1 = x1.divide(BigDecimal.valueOf(2), SCALE, RoundingMode.HALF_UP); } return x1; }
Flags
Project Euler project euler notes
Round 1: Problems 1-20 Problem 1 · Problem 2 · Problem 3 · Problem 4 · Problem 5 · Problem 6 · Problem 7 · Problem 8 · Problem 9 · Problem 10 Problem 11 · Problem 12 · Problem 13 · Problem 14 · Problem 15 · Problem 16 · Problem 17 · Problem 18 · Problem 19 · Problem 20 Round 2: Problems 50-70 Problem 51 · Problem 52 · Problem 53 · Problem 54 · Problem 55 · Problem 56 · Problem 57 · Problem 58 · ... · Problem 61 · Problem 62 · Problem 63 · Problem 64 · Problem 65 · Problem 66 · Problem 67 Round 3: Problems 100-110 Problem 100 · Problem 101 · Problem 102 Round 4: Problems 500-510 Problem 500 · Problem 501 * · Problem 502 * Round 5: Problems 150-160 Round 6: Problems 250-260 Round 7: Problems 170-180
|