Note: this challenge has been posted on the sandbox.
Introduction
This challenge is inspired by 2009 Putnam B1, a problem in an undergraduate mathematics competition. The problem is as follows:
Show that every positive rational number can be written as a quotient of products of factorials of (not necessarily distinct) primes. For example,
Challenge
Your challenge is to take a pair of relatively prime positive integers, representing the numerator and denominator of a positive rational number (or just the rational number itself) as input, and output two lists (or arrays, etc.) of prime numbers so that the inputted rational number is equal to the ratio of the product of the factorials of the primes in the first list to the product of the factorials of the primes in the second list.
Notes
- There may not be any primes that contained both in the first list and in the second list; however, a prime may appear as many times as one wishes in either list.
- The inputs can be assumed to each be (nonstrictly) between 1 and 65535; however, it cannot be assumed that the factorials of the numbers you will need to output will be in this range.
Example Input and Output
Here are examples of legal inputs and outputs.
input=>output
10,9 => [2,5],[3,3,3]
2,1 => [2],[]
3,1 => [3],[2]
1,5 => [2,3,2],[5] (elements of a list may be in any order)
3,2 => [3],[2,2]
6,1 => [3],[]
The inputs (2,2), (0,3), (3,0), (3,6) and (1,65536) are illegal inputs (i.e. your program doesn't need to behave in any particular way on them). Here are some examples of illegal outputs:
1,2 => [2],[2,2] (2 is in both returned lists)
5,2 => [5],[2,4] (4 is not prime)
2,1 => [2],[1] (1 is not prime either)
3,2 => [3],[2] (3!/2! = 3, not 3/2)
Scoring
This is code-golf, so the lowest score in bytes wins!
10/9
=[2*5]/[3*3]
=[(2!/1!) * (5!/4!)] / [(3!/2!) * (3!/2!)]
=[2! * 5! * 2! * 2!] / [3! * 3! * 1! * 4!]
=(2! * 2! * 2! *5!) / (3! * 3! * 4!)
. \$\endgroup\$10/9
rather than a pair of numbers10
and9
? \$\endgroup\$