1
$\begingroup$

First, let me define the $\mathbb{E}$-zone as the set of all even integers.

I am told to find the smallest number with 4 different prime factorizations in this world.

I should also define what it means to be a prime in the $\mathbb{E}$-zone. A number is prime if it cannot be factored into a product of even numbers. For all intents, odd numbers do not exist.

For example, some of the first few primes are 2,6,10,14,18,22... We can see that a number is prime if it is congruent to 2 mod 4.

Now we also know that prime factorization in this world is not unique. For example, 180 has 3 prime factorizations. Namely, (10,18), (6, 30), and (2,90).

I managed to find a number 2940 that has 4 factorizations: (6,490), (10,294), (2,1470), and (30,98).

However, I do not know how to go about finding the $smallest$ such number.

$\endgroup$
1
$\begingroup$

An even integer $2n$ is prime in the $\Bbb{E}$-zone if and only if $2n \equiv 2 \pmod{4}$, which occurs if and only if $n$ is odd. So, factorization into primes amounts to writing $$ \begin{align} N &= 2n_1 \cdot 2n_2 \cdots 2n_k \\ &= 2^k \cdot n_1 \cdot n_2 \cdots n_k, \end{align} $$ where $n_1, \ldots, n_k$ are odd integers. Since we're looking for small numbers with many prime factorizations, and since the product of odd numbers is odd, we may as well assume that $k = 2$. (You seem to have done this implicitly by writing prime factorizations as pairs.)

If we want $4$ prime factorizations, then we're looking for $4$ pairs of prime factors, or an odd number with $8$ factors. (The factors are automatically odd, too.)

In the integers, the number of factors of the number $p_1^{e_1} \cdots p_r^{e_r}$, where $p_1, \ldots, p_r$ are usual primes, is $$ (1 + e_1) \cdots (1 + e_r). $$ So, we need to write $8$ (the number of factors we desire) as $2 \cdot 2 \cdot 2$ or as $4 \cdot 2$. We will consider each possibility in turn.


In the first case, we must consider a product of distinct (odd!) primes $p_1 \cdot p_2 \cdot p_3$. The smallest example of this is $3 \cdot 5 \cdot 7 = 105$, whose factors can be paired off as: $$ \begin{array}{ccc} 1 && 3 \cdot 5 \cdot 7 \\ 3 && 5 \cdot 7 \\ 5 && 3 \cdot 7 \\ 7 && 3 \cdot 5 \end{array} $$ Back in the $\Bbb{E}$-zone, these are prime factorizations of $$ 2^2 \cdot 3 \cdot 5 \cdot 7 = 420 $$ (by putting a $2$ on each factor of the pair): $$ \begin{array}{ccc} 2 && 210 \\ 6 && 70 \\ 10 && 42 \\ 14 && 30 \end{array} $$


In this case, consider a number of the form $p_1^3 \cdot p_2$. The smallest example of this is $3^3 \cdot 5 = 135$, which is larger than $105$, but I'll follow through the analysis anyway. The factors in pairs are: $$ \begin{array}{ccc} 1 && 3^3 \cdot 5\\ 3 && 3^2 \cdot 5 \\ 3^2 && 3 \cdot 5 \\ 3^3 && 5 \end{array} $$ Back in the $\Bbb{E}$-zone, these are prime factorizations of $$ 2^2 \cdot 3^3 \cdot 5= 540 $$ (by putting a $2$ on each factor of the pair): $$ \begin{array}{ccc} 2 && 270 \\ 6 && 90 \\ 18 && 30 \\ 54 && 10 \end{array} $$


So, $420$ is the smallest positive integer with $4$ prime factorizations in the $\Bbb{E}$-zone.

$\endgroup$
  • $\begingroup$ That was extremely helpful. Thank you very much. So if I want the smallest number with 3 distinct factors, for example, I would look for the smallest odd number I can create with 3 distinct odd factors or with 3 total factors, even if some repeat. (trying to make sure I understand this concept). This number would be 180 as $3^2*5 = 45$ and $45*2^2 =180$. Excellent. Thank you. $\endgroup$ – Tyler Murphy Feb 5 '14 at 8:49

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.