aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorMohammad S Anwar <Mohammad.Anwar@yahoo.com>2022-01-04 22:23:34 +0000
committerGitHub <noreply@github.com>2022-01-04 22:23:34 +0000
commitf9378afd589e2a5314dd7bde3edad9e404a8f438 (patch)
treeeeaeb82dd93738039a1165b2e0130506ef64a4c7
parentaf32440afeb5e13f3b57b154ba27cfba2efd4fce (diff)
parentd6c169bd464d2cd85804ea60f4fb7130734f0262 (diff)
downloadperlweeklychallenge-club-f9378afd589e2a5314dd7bde3edad9e404a8f438.tar.gz
perlweeklychallenge-club-f9378afd589e2a5314dd7bde3edad9e404a8f438.tar.bz2
perlweeklychallenge-club-f9378afd589e2a5314dd7bde3edad9e404a8f438.zip
Merge pull request #5476 from drbaggy/master
Changes to notes re ch-2
-rw-r--r--challenge-146/james-smith/README.md33
1 files changed, 29 insertions, 4 deletions
diff --git a/challenge-146/james-smith/README.md b/challenge-146/james-smith/README.md
index b1509962ae..5636403eb1 100644
--- a/challenge-146/james-smith/README.md
+++ b/challenge-146/james-smith/README.md
@@ -42,13 +42,38 @@ 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/.***
+
+```
+ 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
+```
+
+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.