2
$\begingroup$

Note: there is an older post How can all 3 of these be true? that is similar to this one, but I'm trying to find what's wrong.

If we pick two positive integers at random, then there is a 50-50 chance of being even or odd. If we multiply them then the outcomes are
even * even -> even
even * odd -> even
odd * even -> even
odd * odd -> odd
So it seems that only 1 out of 4 composite numbers will be odd, the rest will be even.

But that is incorrect. Especially with large numbers (where primes are a tiny share), nearly all numbers are composite and half are odd. So the "multiply two numbers" approach above gives us 3:1 of even to odd, but it should be 1:1. That's what I'm trying to figure out.

Maybe this is it. There are many ways to get the same number by multiplying two integers. In fact, according to the above: there are three times as many ways to generate a given even number as there are to generate a given odd number. Is that correct?

EDIT: (after 7 comments and 1 answer)
Maybe this is what I'm looking for. Consider 10-digit numbers. Actually just their composite numbers (which is most of them, since only 4% are primes). Separate into evens and odds. Then get the prime factorization of each number, and determine how many ways those primes can be combined to make two numbers. According to the above, the even numbers will have three times as many combos as the odd numbers.

$\endgroup$
8
  • 2
    $\begingroup$ How do you "pick a positive integer at random"? Now, really; it's a serious question. There is no uniform probability distribution that you can define on the positive integers. Instead, you need to talk about the density of the set in question, which would be the limit, as $n\to \infty$, of the quantity of integers $x$, $0\leq x\leq n$ that are composite and even, divided by $n$. $\endgroup$ Commented Nov 2, 2021 at 19:25
  • 1
    $\begingroup$ "It should be 1:1"... no, it shouldn't. Even if you were able to properly define "pick a random integer", multiplying two random integers does not result in a uniformly distributed random integer. $\endgroup$ Commented Nov 2, 2021 at 19:29
  • $\begingroup$ @Henry: Badly phrased. The PNT says that $\lim_{x\to\infty}(\pi(x)/x)/(\ln(x)/x) = 1$. So the proportion of primes less than $x$ is approximated by $\ln(x)$. Density is the wrong word to use, you are correct. Deleting. $\endgroup$ Commented Nov 2, 2021 at 19:45
  • 5
    $\begingroup$ @MJD: If you pick uniformly from $1,\ldots,N$ twice, and multiply, you don't end up uniformly distributed in $[1,\ldots,N^2]$. So there is no reason to expect that the "answer" should be "fifty-fifty chance of getting even/odd". $\endgroup$ Commented Nov 2, 2021 at 19:46
  • 2
    $\begingroup$ @MJD: But doing it "in $1,\ldots,N$ is not "an integer at random". You are still doing a limiting process, rather than dealing with all integers. $\endgroup$ Commented Nov 2, 2021 at 20:00

2 Answers 2

1
$\begingroup$

I think your mistake is the probability of the results of choosing two random numbers from a finite set of numbers and then multiplying them together are different than the probability associated with all numbers. For example, assuming you choose two random numbers m and n both from the finite set of the first 6 natural numbers, you will generate 36 results but these 36 results will overlap each other and will not generate the entire set of natural numbers less than or equal to 36. In the multiplication table below note the results include 9 odd numbers and 27 even numbers and hence 1/4 of the total results are odd as predicted, but the results are missing the 8 primes between 6 and 36 (i.e. 7, 11, 13, 17, 19, 23, 29, and 31) which are all odd. The results below are also missing 10 composite numbers between 6 and 36 (14, 21, 22, 26, 27, 28, 32, 33, 34, 35) 4 of which are odd and 6 of which are even.

$$\begin{array}{ccccccc} m/n & 1 & 2 & 3 & 4 & 5 & 6 \\ 1 & 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 2 & 4 & 6 & 8 & 10 & 12 \\ 3 & 3 & 6 & 9 & 12 & 15 & 18 \\ 4 & 4 & 8 & 12 & 16 & 20 & 24 \\ 5 & 5 & 10 & 15 & 20 & 25 & 30 \\ 6 & 6 & 12 & 18 & 24 & 30 & 36 \\ \end{array}$$

$\endgroup$
0
$\begingroup$

As discussed by others, the problem is in being careful about definitions.

That said, it is true that the majority of composite numbers are even, since of course every prime other than 2 is odd. The larger the numbers get, the less noticeable this becomes, as the primes take up an ever-smaller slice of the integers.

A few values for percentage of composites that are even through the first $n$ positive integers:

     n    %
---------------
    100  66.2%
   1000  60.0%
  10000  57.0%
 100000  55.3%
1000000  54.3%
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .