From df081f42009611d870879c4e69e17ea248f06a8d Mon Sep 17 00:00:00 2001 From: James Smith Date: Tue, 4 Jan 2022 17:15:49 +0000 Subject: Update README.md --- challenge-146/james-smith/README.md | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/challenge-146/james-smith/README.md b/challenge-146/james-smith/README.md index b1509962ae..d40944cdb2 100644 --- a/challenge-146/james-smith/README.md +++ b/challenge-146/james-smith/README.md @@ -42,7 +42,7 @@ so the last element is the 10,001st prime. # Challenge 2 - Curious Fraction Tree -*** Can't really describe this - best to look at the image on the website at https://theweeklychallenge.org/blog/perl-weekly-challenge-146/.*** +***Can't really describe this - best to look at the image on the website at https://theweeklychallenge.org/blog/perl-weekly-challenge-146/.*** ## The solution -- cgit From 962b29f06c9b542023bf0c377830f3c97c27e5be Mon Sep 17 00:00:00 2001 From: James Smith Date: Tue, 4 Jan 2022 17:28:19 +0000 Subject: Update README.md --- challenge-146/james-smith/README.md | 18 ++++++++++++++++++ 1 file changed, 18 insertions(+) diff --git a/challenge-146/james-smith/README.md b/challenge-146/james-smith/README.md index d40944cdb2..49035b9035 100644 --- a/challenge-146/james-smith/README.md +++ b/challenge-146/james-smith/README.md @@ -44,6 +44,24 @@ so the last element is the 10,001st prime. ***Can't really describe this - best to look at the image on the website at https://theweeklychallenge.org/blog/perl-weekly-challenge-146/.*** +``` + 1/1 + | + +-------------------+-------------------+ + 1/2 2/1 + | | + +---------+---------+ +---------+---------+ + | | | | + 1/3 3/2 2/3 3/1 + | | | | + +----+----+ +----+----+ +----+----+ +----+----+ + | | | | | | | | + 1/4 4/3 3/5 5/2 2/5 5/3 3/4 4/1 + | | | | | | | | + +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ + | | | | | | | | | | | | | | | | +1/5 5/4 4/7 7/3 3/8 8/5 5/7 7/2 2/7 7/5 5/8 8/3 3/7 7/4 4/5 5/1 +``` ## The solution We notice that: -- cgit From d6c169bd464d2cd85804ea60f4fb7130734f0262 Mon Sep 17 00:00:00 2001 From: James Smith Date: Tue, 4 Jan 2022 19:33:01 +0000 Subject: Update README.md --- challenge-146/james-smith/README.md | 13 ++++++++++--- 1 file changed, 10 insertions(+), 3 deletions(-) diff --git a/challenge-146/james-smith/README.md b/challenge-146/james-smith/README.md index 49035b9035..5636403eb1 100644 --- a/challenge-146/james-smith/README.md +++ b/challenge-146/james-smith/README.md @@ -62,11 +62,18 @@ so the last element is the 10,001st prime. | | | | | | | | | | | | | | | | 1/5 5/4 4/7 7/3 3/8 8/5 5/7 7/2 2/7 7/5 5/8 8/3 3/7 7/4 4/5 5/1 ``` + +For a given node `n/d` the children are `n/(n+d)` and `(n+d)/d`. + ## The solution -We notice that: - * if you have a top-heavy fraction then the parent has the same denominator, and the new demoninator is the difference between the numerator and denominator. - * otherwise the numerator stays the same and the denominator becomes the difference between the numerator and denominator. +We note that the left-child is always less than one, the right child is always greater than 1. + +* To get the parent of the left child we note that `n+d = D` and `n = N`, so the parent denominator is `N-D` and numerator doesn't change +* To get the parent of a right child we note that `n = N+D` and `d = D`, so the parent numerator is `N-D` and denominator doesn't change. +* For all nodes the numerator/denominator are co-prime. + +If it is a member of the tree we repeat until both `n` & `d` are 1. If the node is such that the numbers aren't coprime we eventually stop when We repeat this until we get to the top of the tree where both the denominator and numerator are less than 2. (In the tree is always 1/1) as all tree members have co-prime numerators and denominators. Other values end when the numerator is 0. The `stringify` function just converts the tree into a single string (list of fractions) so we can test the tree code. -- cgit