2 Fractions and a Prime

Weekly Challenge 146

TASK #1 › 10001st Prime Number

Task

Write a script to generate the 10001st prime number.

My solution

Easy peasy. Search it, print 104743 and we are done. Well not quite, but still a valid solution :)

This is a relatively straight forward task. Create a method called is_prime to determine if a number is a prime. Then have a counter to find the 10,001st prime number.

The Perl solution is transliteration of the Python code.

Examples

$ ./ch-1.py 
104743

$ ./ch-1.pl 
104743

TASK #2 › Curious Fraction Tree

Task

Consider the following Curious Fraction Tree:

You are given a fraction, member of the tree created similar to the above sample.

Write a script to find out the parent and grandparent of the given member.

My solution

Python has an fractions method. My original though was to create each level of the tree, and find out if we have a match.

However, looking at the tree, there is an obvious pattern to work out what the parent value is. If the fraction is greater than 1, we reduce the numerator (top value) by the value of the denominator (bottom value). If it is less than 1, we reduce the denominator by the numerator.

Using this theory, I have a method called get_parent that will return the parent Fraction value given a Fraction value. It will return None if it has no parent (either -1/1 or 1/1). I also have a method called f that generates a string to display as the Fractions str method, will not show the denominator if it is 1.

The Fraction method will automatically normalize the fraction. If we supply 6/-4, it will automatically become -3/2.

For the Perl solution, Dave Cross (a former Team PWC member) has written the Number::Fraction CPAN module, which acts the same as the Python equivalent. Regular readers of my blog posts will know that I tend not to use non-core Perl modules. I've decided to ease up on this, as it seems pointless to reinvent the wheel.

The Perl solution has the same underlying logic as the Python version.

Examples

$ ./ch-2.py 3/5
parent = '3/2' and grandparent is '1/2'

$ ./ch-2.py 4/3
parent = '1/3' and grandparent is '1/2'

$ ./ch-2.py 1/2
parent = '1/1' and grandparent is None

21