Find a random integer which creates another integer, when using percentages

Question

Solved, for the precise solution for my problem, see my answer

I am sorry about the confusing title, let me clarify my problem:

My Java program is supposed to ask a math question with percentages.

It should create a question in this format:

25% of 4616 = ?

The requirements are:

• the percentage is always dividable by 5 (no problem)
• the number (here 4616) has to be between 100 and 9999 (also not a problem)
• the number as well as the result has to be an integer (this is my problem)

Is there any fast method to find a random number which fulfills the last requirement?

The only solution I can think of is to find the percentage, then create a loop which will not stop until a random number is found which fulfills the requirement (in the example until number % 4 == 0 is true)

But this loop could run thousands of times until a correct number is found.

Is there a better method for my problem?

Edit: It seems that I didn't make clear what my problem is, I don't want double numbers as a result, only integer.

E.g.: If my percentage is 65%, then a possible question would be

65% of 7620 = ?

because the solution 4953 is also a whole number.

I want to find a random number between 100 and 9999 which is a whole number AND has a whole number as a result to the equation p * x = y.

Answer 1

Let p be the percentage (the numerator, i.e. 25%), x by the initial value and y be the resulting integer.

Since p is a percentage which is a multiple of 5 and from 0 to 100 then we can represent it as p = 5a/100 = a/20 where 0 <= a <= 20.

For x we have the constraint that 100 <= x <= 999.

First pick an a that satisfies 0 <= a <= 20.

Next we pick an x. Well, for p * x = (a/20) * x to be an integer result we just need 20 to divide a * x. Well, we know that 20 | (a * x) ("20 divides a * x") if and only if

j = (a * x) / 20 (<- j is some integer)
<=> j = (a * x) / (2^2 * 5^1)

Since we have a we can replace it by its prime factorization:

j = (p1^e1 * p2^e2 * ... * pn^en) * x / (2^2 * 5^1)

Now realize that a is less than 20 so it's prime factorization is probably pretty simple and likely to "overlap" with the prime factorization. For example, if a = 5 then the above equation simplifies to

j = x / 4

In which case it's easy to see how we can generate x that will produce an integer j (multiples of 4. Though you need 100 <= x <= 9999 too!). So "overlapping" (i.e. prime factors in the numerator which are the same as the denominator) are super beneficial. That's where the greatest common divisor comes into play. The GCD(a, 20) is the largest integer that divides both a and 20. The prime factorization of the GCD is precisely the overlap. It also has the nice property that, once we "remove" the overlap, the resulting values:

j = b * x / c

Have the nice property that b and c are coprime. From that we know that b * x / c is an integer if and only if c | x.

So let GCD(a, 20) = k. Then by definition we have a/k = b and 20/k = c, so a/20 = b/c. Therefore let x = c * m where m is an integer. Then we have:

100 <= m * c <= 9999
=> 100 / c <= m <= 9999 / c

So we can do a floor(rand(100 / c, 9999 / c)) to produce your m.

To summarize:

a = rand(0, 20)
p = 5*a
c = 20 / GCD(a, 20)
m = floor(rand(100 / c, 9999 / c))
x = c * m
y = (p / 100) * x

Note that a = 0 is actually an edge case and furthermore, floor() won't give you a completely uniform distribution. If you need these to be covered I can probably think about it and tweak the answer a bit. Also, the euclidean algorithm is trivial to implement, you can look it up. Heck, since a < 20 you could probably just hardcode the function :)

edit I forgot to define c in my summary the first time through. Here's an example to produce the counter-example you had below:

a = 5
p = 25
c = 20 / GCD(5, 20) = 20 / 5 = 4
m = some integer in [25, 2500). In this case so we randomed 879
x = 3516
y = 879

Conveniently in this example we have GCD(a, 20) = 5 so it turns out that m = y, but that's not always the case.

Answer 2

Okay, thanks to roliu I finally found a solution. This is how my final solution looks like:

Create a random number between 1 and 20 (because percentage is dividable by 5):

a = rand(1,20)

Find greatest common divisor:

b = gcd(a,20)

Create a random number in the range divided by 20/gcd (see denis answer if you dont know why):

c = rand(floor(100/(20/b)),floor(9999/(20/b)))

Multiply the random number by 20/gcd to get a number in the range, our x:

x = floor(c * (20/b))

Multiply the number by the percentage to get the solution y:

y = floor(x * (a/20))

Converting the percentage to the correct value to be printed:

p = a * 5

Final equation:

p % of x = y

Answer 3

You're right, the divider is dependant on the p value. So, pick p first, then use it to calculate the divider to select the random number in the range:

For 5% it should be dividable by 20 (5/100 = 1/20)
For 10% it should be dividable by 10 (10/100 = 1/10)
For 15% it should be dividable by 20 (15/100 = 3/20)
For 20% it should be dividable by 5 (20/100 = 1/5)
For 25% it should be dividable by 4 (25/100 = 1/4)
For 30% it should be dividable by 10 (30/100 = 3/10)
...

You can calculate it by reducing the fraction p/100 and picking the denominator

below answer is not correct

Looks like you'll have to pick numbers from the range of 100-9999 which are dividable by 20.

answer = x * p/100 = x * k/20 (since p is dividable by 5)
k = rand(1,494)
x = 100 + 20*k
p = 5*rand(1,20)

Answer 4

I would just select a percentage and work backwards from the answer to arrive at the question:

p * x = answer | 0 < p < 100, p = 5k, 100 <= x < 10000

So, pick your percentage:

p = (5 * rand(1, 9)) / 100.0;

Make sure your 100 <= answer / p < 10000:

answer = rand(100, p * 9999);

Solve for the 'unknown':

x = p / y