For a given rational number
r, find a pair of integers
p,q so that
p/q=r and the number of less used bits in
q are minimized (details below).
A positive rational number
r can be expressed as the ratio of two positive integers,
r=p/q. The representation is not unique. For each of these representations, both
q can be expressed in its binary form and the number of
1s in the representation can be counted (not including leading zeros).
We count the number of appearance of the less appeared digit for both
g(q)) and finally define
For example, the number
35 can be written as
175/5, and we convert both the numerator and the denominator to binary. Then we can count
35 -> 100011, 3 zeros, 3 ones. g(35)=min(3,3)=3 1 -> 1, 0 zero , 1 one. g(1)=min(1,0)=0 f(35,1)=max(g(35),g(1))=3.
175 -> 10101111. 2 zeros, 6 ones. g(175)=min(2,6)=2 5 -> 101. 1 zero, 2 ones. g(5)=min(1,2)=1. f(175,5)=max(g(175),g(5))=2.
Therefore, if we want to minimize
f(p,q) while keeping the rate of
p=175,q=5 is a better choice than
p=35,q=1. An even better choice is
f(1015,29)=1. It is also easy to prove that there are no valid choice that makes
0, so this the optimal choice.
Your task is to write a full program or function that computes a choice of
(p,q) for a given rational number
r such that
f(p,q) is minimized (sub-optimal solutions are OK but there are penalties), while keeping the program as short as possible.
The outputs are not unique.
Input Output 63/1 63/1 0 17/9 119/63 1 35/1 1015/29 1 563/1 2815/5 2
You may also wish to see whether you can get an answer without penalty(see below) for
Your score will be composed of two parts: the code-length and the penalties. The code-length is measured in bytes.
The penalties are calculated by running your program on all test cases in the given test set. For each
r in the test set, if your program outputs
p,q, you get a penalty of
max(f(p,q)-2,0). That is, you get no penalty (nor bounty) for any answer that gives a
f value less than or equal to
The final score is calculated by
final_penalty*codelength^(1/4), with lower score better.
The test set for calculating the penalty can be found in this pastebin.
Basically, it contains all rational numbers which when expressed in reduced fraction
p/q has the property
128>p>q (and of course,
(p,q) coprime), along with all integers from
1023(inclusive). The second column in the pastebin are the
f(p,q) calculated by a naive method. The final line in the pastebin shows the total penalty of this naive method. It is
- Input can be given in any reasonable form. For example, a rational if your program supports it, or a tuple or a list of the numerators and denominators in any order (and you should assume them to be coprime). Same flexiblility for output.
- You need to output
qin a reasonable form and also
f(p,q)(To avoid 0-byte programs, thanks to @Lynn).
- You should be able to score your own program (Thanks for the suggestion by @user202729). So in your answer, please specify all of the following: the final penalty, the code length in bytes, and the score. Only the score needs to be included in the title of your answer.