The following algorithm can be applied to a list of fractions and an integer input. You go down the list and multiply the input by the first fraction that will result in an integer. Taking this product as the new input, you repeat, using the same list of fractions. The algorithm ends when none of the fractions will result in an integer.
For example, if the list of fractions is {5/6, 5/2, 5/3}, then inputting an integer 2a * 3b will result in 5max(a,b). A more complicated example: inputting 2a * 3b into {7/11, 11/(3*7), 1/7, (5*7)/2, 3/5} will result in 3a (if a>0).
Find a list of fractions such that inputting an integer 2a * 3b will result in 5ab.
How about a list that, when the input is 2a * 3b, results in 5a^b (with b>0)?
|
|
Submitted by Tristan
|
|
Rating: 4.1818 (11 votes)
|
|
|
Solution:
|
(Hide)
|
|
This algorithm is called FRACTRAN, and was created by John Conway.
2a * 3b to 5ab:
{ (7*11*5)/13, 13/(2*11), 1/11, 2/7, 11/3, 1/2 }
2a * 3b to 5a^b:
{ (7*11*19)/23, 23/(2*19), 17/19, 2/11, 19/(5*17), 13/17, 5/7, 17/(3*13), (5*17)/3, 1/2, 1/13 }
Other, and perhaps better, solutions are possible. |
