Let us say that any number which can be represented as a string of bits with a single decimal point is "binary enodable"; all such numbers are positive, computable, and rational.

Suppose we have some arbitrary set of integers, N. (ex. [16 32 40 48] )

All elements in N are binary encodable, with the important feature that the decimal point always has 0's to the left of it.

(ex. [1000.0 10000.0 101000.0 110000.0] )

Every element in N has a bit string representation; that bit strings length (in terms of bits needed to uniquely identify it) is M, and the summation of all M's in N, is K. (ex [21])

Now let's suppose we performed a map transform on N, in which we multiplied each element in N, by the same number C which is binary encodable, represented in the same format as the elements in N (with the crucial change that it may have bits to the left of the decimal), and stored the results of this transform into set T.

(ex. [1000.0 10000.0 101000.0 110000.0] * 0.001 = [10.0 100.0 101.0 110.0] )

T would then have it's own summation of the bit string representations of it's constituents (now possibly rationals rather than integers), which we will call S.

Here is my question: is there an effective procedure that will determine, for any set N, the computable real C which yields a set T with the smallest possible S?

Said more plainly, for any arbitrary set of integers is there any way to determine a rational factor which will yield the smallest representative numbers that still maintain the same scale of the original set?

  • 1
    $\begingroup$ The first thing you should do is use the Euclidean algorithm to factor out the greatest common factor of the original set of integers. Once that's done, the problem reduces to finding the best power of $2$ to divide by, which should be pretty easy. $\endgroup$ Commented May 28, 2014 at 7:18


You must log in to answer this question.

Browse other questions tagged .