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 2^a * 3^b will result in 5^max(a,b). A more complicated example: inputting 2^a * 3^b into {7/11, 11/(3*7), 1/7, (5*7)/2, 3/5} will result in 3^a (if a>0).

Find a list of fractions such that inputting an integer 2^a * 3^b will result in 5^ab.

How about a list that, when the input is 2^a * 3^b, results in 5^{a^b} (with b>0)?

(In reply to Solution? by Joel)

Here is a somewhat smaller list for part 2:

(11/13, (7*13*13)/(11*11*2), 13/(11*11),  (17*2*13)/(11*7), (13*13)/(5*11), 1/11, 5/17, (11*11)/(5*3), 17/(2*5), (11*7)/2, 1/3)

Here is the something akin to code describing the progression (where a is two 11s present, b is one 11 present, c is no 11s  but 5/17s present, and d is no 11s,5s, or 17s present):

d) if there is a 2 create a 5 and goto c
    else delete all 3s and quit
c) convert all 17s to 5s
    if there is a 3 consume a 5 and 3 and goto a
    else delete all 2s and quit
a) convert all 2s to 7s
b) convert all 7s to 17s and 2s
    if there is a 5 consume it and goto a
    else goto c

Posted by Joel on 2006-11-22 00:25:03