1
$\begingroup$

Which the least number n can we imagine in product n = a∙b like k ways? Products a∙b and b∙a is one of the way, where all numbers is natural (1≤ k ≤50)

I tried to loop from 1 to 1000000 and with each number perform the following:

looping from 1 to square root of that number and if number%i==0 then add to one variable and after reaching the square root check if var is equal to k if yes then print i,but this solution took too much time

$\endgroup$

2 Answers 2

2
$\begingroup$

Suppose $$n=2^{n_1}\cdot 3^{n_2}\dots \cdot p_r^{n_r}$$ where $p_r$ is the $r^{th}$ prime. The number of divisors of $n$ $$d(n)=(n_1+1)(n_2+1)\dots (n_r+1)$$

The number of factorisations is half of this unless $n$ is a square in which case it is half $d(n)+1$.

To find a number having $k$ factorisations, reverse this process. Look at factorisations of $2k$ and allocate the largest factors to the smallest primes. Check also factorisations of $2k-1$.


Suppose $k=2$ we need $d=2k=4$ or $d=2k-1=3$.

If $d=4$ we have either

(1) the single factor $4$ which gives exponent $4-1=3$ and choose the lowest prime, $2^3=8$ with factorisations $1\cdot 8$ and $2\cdot 4$

(2) The factors $2\cdot 2$ which gives two exponents equal to $2-1=1$. The lowest possibility is $2^13^1=6$ and factorisations $1\cdot 6$ and $2\cdot 3$

If $d=3$ we have just the factor $3$ and exponent $3-1=2$ which gives $2^2=4$ with $1\cdot 4$ and $2\cdot 2$

This tells us that the possible lowest numbers having two factorisations are $4, 6, 8$ - obviously $4$ is the one.


With $k=6$ we have $d=12$ or $d=11$

$d=12$ factorises

(1) as $12$ giving $2^{11}=2048$

(2) $6\cdot 2$ giving $2^5\cdot 3=96$

(3) $4\cdot 3$ giving $2^3\cdot 3^2=72$

(4) $3\cdot 2 \cdot 2$ giving $2^2\cdot 3\cdot 5=60$

$d=11$ gives just $2^{10}=1024$

Clearly $60$ is the number you want.


In this last case, how do we count the factors of $60$?

Well with the prime $2$ we have three possible factors $1,2,4$

With the prime $3$ we get $1,3$

With the prime $5$ we get $1,5$

We need to choose one factor associated with each of the primes, hence $3\times 2\times 2=12$ possibilities.


How do we know we got all the possibilities for $12=2^2\cdot 3^1$. Well this gives $d=6$ and $k=3$ for two factor factorisations, and there is just the fourth possibility $2\cdot 2\cdot 3$ - we got them all.

$\endgroup$
3
  • $\begingroup$ Can you please show an example with k being 2? I didn't understand your answer $\endgroup$
    – Murad
    Aug 14, 2017 at 17:54
  • $\begingroup$ @Murad I have added some examples. $\endgroup$ Aug 14, 2017 at 19:12
  • $\begingroup$ Thank you for your help! $\endgroup$
    – Murad
    Aug 14, 2017 at 20:01
0
$\begingroup$

If $n$ has $m$ factors (including $1$ and $n$) then when can express $n = a*b$ where $a$ is a factor and $b = \frac nb$. As there are $m$ possible choices for $a$ there are $m$ ways do do this.

However if $n = a*b$ is one way to do it then $n = b*a$ is also a way and we counted both separately. So the number of ways is $\lceil \frac m2 \rceil$. (BTW, $m$ is a odd number if and only if $n = k*k$ for some factor $k$. In other words, if and only if $n$ is a perfect square).

So in asking which is the smallest number that can be written a product of two numbers in $k$ ways, is the same as asking which is the smallest number with $2k$ or $2k-1$ factors.

So the question we must ask is how many factors does a number have.

If $n = \prod p_i^{k_i}$ is the prime factorization of $n$ then the factors of $n$ are the numbers of the form $\prod p_i^{m_i}$ where $m_i \le k_i$ or $m_i = 0....k_i$. For each $m_i$ there are $k_i+1$ choices so there are $\prod (k_i+1)$ factors of $n$.

So to find an $n$ with $2k$ or $2k-1$ factors we must find when $\prod(k_i+1) = 2k$ or $\prod(k_i+1) = 2k$.

So for example: to find the smallest number $n$ which can be written as $a*b$ in $5$ ways we must find $\{k_1..... k_m\}$ so that $\prod (k_i + 1) = 10$ or $9$.

So we can have $\{1,4\}$ (because $(1+1)(4+1) = 10$) or $\{9\}$ (because $(9+1) = 10$) or $\{2,2\}$ (because $(2+1)(2+1) = 9$) or $\{8\}$ (because $(8+1) = 9$.

So if $n = pq^4$ where $p,q$ are prime then $n$ can be written as $a*b$ in five ways: $1*pq^4, p*q^4, q*pq^3,pq*q^3, q^2*pq^2$

If $n = p^9$ for $p$ prime then $n$ can be written as $a*b$ in five ways: $1*p^9, p*p^8, p^2*p^7, p^3*p^6, p^4*p^5$.

If $n = p^2*q^2$ we can do this five ways: $1*p^2q^2, p*pq^2, q*p^2q,pq*pq, p^2*q^2$.

And if $n = p^8$ we can do this five ways: $1*p^8, p*p^7, ... , p^4*p^4$.

....

So which is the smallest? Well, obviously we should choose the smallest primes. $2,3$.

So $n$ equals one of these $2*3^4, 3*2^4, 2^9, 2^23^2, $ or $2^8$.

Well... clearly we should put the higher values to the lowest primes. That is $2*3^4 > 2^4*3$ obviously as the $3$ to a higher power in the LHS "outweighs" the $2$ to a higher power in the RHS.

Less obviously $2*3^4 < 2^9$ because it is smaller to "spread them out".

And finally, assuming the smallest prime factors, a square with $2n - 1$ factor will be smaller than a non-square with $2n$ factors.

So the smallest number that can be written as $a*b$ five ways is $2^2*3^2 = 36$ which can be written as $1*36, 2*18, 3*12, 4*9, 6*6$.

So in general. The smallest number that can be written $k$ ways will be square number $2^{2k_1}3^{2k_2}...$ where $(2k_1+1)*(2k_2 + 1) *..... = 2k -1$.

Example: The smallest number that can be written $8$ ways is: i) $2*8 = 16 = 15+1$ ii) $15= (2+1)(4+1)$ so the number is $2^4*3^2 = 144 = 1*144,2*72,3*46,4*36,6*24,8*18,9*16,12*12$.

$\endgroup$

You must log in to answer this question.

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