aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJames Smith <js5@sanger.ac.uk>2022-01-04 19:33:01 +0000
committerGitHub <noreply@github.com>2022-01-04 19:33:01 +0000
commitd6c169bd464d2cd85804ea60f4fb7130734f0262 (patch)
treed31ad6b0e1c25deb9bc491ec86940257bbc45526
parent962b29f06c9b542023bf0c377830f3c97c27e5be (diff)
downloadperlweeklychallenge-club-d6c169bd464d2cd85804ea60f4fb7130734f0262.tar.gz
perlweeklychallenge-club-d6c169bd464d2cd85804ea60f4fb7130734f0262.tar.bz2
perlweeklychallenge-club-d6c169bd464d2cd85804ea60f4fb7130734f0262.zip
Update README.md
-rw-r--r--challenge-146/james-smith/README.md13
1 files 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.