1
$\begingroup$

I would like to figure out how many ways there are to create product pairs equal to or less than a certain number. In other words, find a pair of integers $(n,m)$ such that $nm \le N$ for a given integer $N$.

I'm creating a math game and I have an idea for how to adjust the difficulty. In the preferences, you can set a maximum value $N$ for the answers. For the multiplication problems, I want to be able to control the number of $0\times n$, $n \times 0$, $1\times n$ and $n \times 1$ problems.

My plan is to do it by adjusting the frequency of those types of problems. I can calculate the number of the the other types of problems, but I can't calculate their frequency without knowing the total number of possible multiplication problems $n\times m \le N$.

For the ones I gave, the numbers are, for a maximum answer of N:

Including 0 as a factor: $2N+1$

Including 1 as a factor: $2N-1$

Doubles, such as $n \times n$: N even: $\frac{N+2}{2}$ N odd: $\frac{N+1}{2}$

My question is similar to two others, but these do not have complete or general answers:

Number of ordered pairs $(a,b)$ such that $ab \le 3600$

Number of pairs with product less than a given number.

An analytical solution is given here, but no explanation so I'm not sure if it is right or not.

Following up on the accepted answer. Here is the comparison between actual and $N\log{N}$:

N       Actual Number       N*Log(N)
   1            1           0.00
   2            3           1.39
   4            8           5.55
   8           20           16.64
  16           50           44.36
  32          119           110.90
  64          280           266.17
 128          645           621.06
 256         1466           1419.57
 512         3280           3194.02
1024         7262           7097.83
2048        15937           15615.22
4096        34720           34069.57

My matlab code is:

% scriptCountNumProducts.m

s = sprintf('  N\t\tActual Number\t\tN*Log(N)');
disp(s);

for q = 0:12

    N = 2^q;
    count = 0;
    for n=1:N
        for m = 1:N
            product = m*n;
            if product <= N
                count = count + 1;
            end
        end
    end

    s = sprintf(...
    '%4d  \t\t%5d\t\t\t%0.2f',N, count, N*log(N)...
    );
    disp(s);

end
$\endgroup$
  • $\begingroup$ Do $2 \times 3$ and $3 \times 2$ count as one or two examples? $\endgroup$ – Eric Towers Jun 13 '14 at 21:56
  • 2
    $\begingroup$ There is not an exact method for this - but see this question and answers (there are others similar) math.stackexchange.com/questions/486504/… - you are essentially counting the integer points underneath a hyperbola. $\endgroup$ – Mark Bennet Jun 13 '14 at 21:57
  • $\begingroup$ @EricTowers They count as different because I'm randomly generating math problems, and I wouldn't want to bias having always the bigger or smaller number first. So in the app, 2x3 and 3x2 are different math problems (obviously with the same answer). $\endgroup$ – abalter Jun 15 '14 at 1:55
1
$\begingroup$

As Mark Bennet points out, asking which integer $x$ and $y$ satisfy $xy \leq N$ is equivalent to asking which integer points lie underneath the hyperbola $y = \frac{N}{x}$. The integer points may be hard to count exactly, but the area containing these points is easier to compute with Calculus: $$ \int_1^N \frac{N}{x} dx = N \ln N. $$ Most of the area comes from unit squares lying totally under the curve. Each of these can be identified with its lower-left corner, which is an ordered pair of integers having product less than $N$. The method is not exact, since some of the area is coming from unit squares that lie only partly under the curve. Still, $N \ln N$ is a good estimate.

$\endgroup$
  • $\begingroup$ Thanks! For my purposes, having approximate probabilities is probably good enough. If they don't all add to one, I can just normalize what I have. $\endgroup$ – abalter Jun 14 '14 at 2:30
  • $\begingroup$ see what I added to the question... $\endgroup$ – abalter Jun 14 '14 at 4:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.