# How to find an $n$-digit number with $m$ number of factors?

I found on the Internet a question which I did not understand:

There is a $6$-digit number with $28$ distinct factors. What is the number?

I searched and found that

Number of factors of a number of the form ${p_1}^{m_1} \times {p_2}^{m_2} \times {p_3}^{m_3} \cdots$ is $(m_1 +1) \times (m_2 +1 ) \times (m_3 +1 ) \cdots$.

But I did not understand how one can answer this question.

Also, if there is some way, I would be glad to know

The general formula of $n$-digit number with $m$ number of factors?

Note by Vinayak Srivastava
3 months, 3 weeks ago

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

• Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
• Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
• Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$ ... $$ or $ ... $ to ensure proper formatting.
2 \times 3 $2 \times 3$
2^{34} $2^{34}$
a_{i-1} $a_{i-1}$
\frac{2}{3} $\frac{2}{3}$
\sqrt{2} $\sqrt{2}$
\sum_{i=1}^3 $\sum_{i=1}^3$
\sin \theta $\sin \theta$
\boxed{123} $\boxed{123}$

Sort by:

Hey Vinayak, here is an explanation of the formula for the number of factors: Let $n = p_1^{m_1} \cdot p_2^{m_2} \cdots$. Every factor of $n$ is a product of the prime numbers risen to some power: $f = p_1^{n_1} \cdot p_2^{n_2} \cdots$ with $0 \leq n_1 \leq m_1, 0 \leq n_2 \leq m_2 ...$. For example let $n = 12 = 2^2 \cdot 3^1$. All the factors of 12 are:

$2^0 \cdot 3^0 = 1$

$2^1 \cdot 3^0 = 2$

$2^2 \cdot 3^0 = 4$

$2^0 \cdot 3^1 = 3$

$2^1 \cdot 3^1 = 6$

$2^2 \cdot 3^1 = 12$

As you can see, for each power of the prime numer $p_n$ there are $m_n + 1$ choices $0, 1, ... m_n$. Therefore, the number of factors is $(m_1 + 1) \cdot (m_2+1) \cdots$. I hope this helps!

- 3 months, 3 weeks ago

Thanks @Finnley Paolella ! Now can you please tell me how to find the general formula of $n$-digit number with $m$ number of factors?

- 3 months, 3 weeks ago

I don't know if there is a general formula, but my strategy would be the following: try to factor $m$ to find the power of prime numbers. For example: $28 = 4 \times 7$. A number of the form $n = p_1 ^3 \times p_2 ^ 6$ will always have 28 factors. And then we can try:

$2^3 \times 3^6 = 5832$ is too small

$2^3 \times 5^6 = 125000$

And that is a solution to the original question!

However, the solution is not unique. Here is another solution:

$2^6 \times 11^1 \times 443^1 = 311872$

Number of factors: $(6 + 1) \times (1+ 1) \times (1 + 1) = 28$

- 3 months, 3 weeks ago

Interestingly, although there are 3,013 six-digit numbers with 28 factors, there are some numbers of factors for which there is only one six-digit number with that many factors. These are, I believe, 7, 13, 19, 38, each of which has only one six-digit number with that many factors. (edit: there are probably a lot more solo numbers of factors >50 but I aggregated everything with 50 or more factors to save on processor time.)

- 3 months, 3 weeks ago

How did you calculate this?

- 3 months, 3 weeks ago

Slightly educated brute force. I wrote a bit of simple code that worked out how many (distinct) factors a number had, looped it from 100,000 to 999,999, let it churn for a couple of hours and graphed the results.

- 3 months, 3 weeks ago

WOW!!

- 3 months, 3 weeks ago

Hey Stef, that is amazing! Great visualisation :)

- 3 months, 3 weeks ago

Thanks.

- 3 months, 3 weeks ago

Really awesome stuff! Interestingly you can also see that prime number of factors such as 7 and 11 are very less, fantastic!

- 3 months, 3 weeks ago

Yeah. I'm a big fan of visualising data. You can see all the primes (two factors), all the squares (odd number of distinct factors), and a bit of the long tail of large numbers of factors (it was long tail before I cut it off).

- 3 months, 3 weeks ago

Stef, can you please share the process, I mean the code if you don't mind? It seems you used matplotlib to visualise after processing your data from code. Thanks!

- 3 months, 3 weeks ago

Happy to. It's not very optimised (after all, I only wanted to run it once) so please excuse the code. Also it's written in Lua which is quite like C, Java, JavaScript and Python. A few things to know, though:

1. Arrays (actually tables, but you can use them as arrays) are initialised with {} and referenced with []. Also they start at an index of 1. So, if a={10,11,12}, a[1]=10.
2. Instead of bracketing or indenting code, Lua uses the word end to end blocks of code so if ... then ... end, for ... do ... end etc. are common constructions.
3. You can put multiple statements on a line if you separate them with semi-colons.
4. Variables are weakly typed, automatically coerced and don't need declaring: every variable just holds the value of nil unless you give it a value.
5. Anything else just ask... :)
6. (edit) output was in comma separated format that I could paste straight into Apple Numbers as it takes CSV from the clipboard.
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 function factors(n) c=0 for f=1,n do if (n//f)==(n/f) then c=c+1 end if c==50 then break end end return c end -- set parameters min=100000 max=999999 step=1000 -- used to track progress ns=min+step -- used to track progress -- initialise array a={} for f = 1,50 do a[f] = 0 end -- calculate factors for f=min,max do if f==ns then print(f); ns = ns + step; end -- display progress n=factors(f) a[n] = a[n] + 1 end -- display output s="" for f=1,50 do s = s..f..","..a[f].."\n" end print(s) 

- 3 months, 3 weeks ago

Lua??? Retro gaming?

- 3 months, 3 weeks ago

lol. Yeah. Lua. Despite having spent more time with other languages than I have with Lua, I can get an idea out of my head and running faster in Lua than any other language.

Maybe it's the way my brain works, maybe it's the way that Lua works but, if I don't need to share or integrate with anything else, Lua has become my go-to.

(edit) You know that moment when you've spent an hour debugging a bit of code only to realise that the language didn't work the way you expected it to...? I get that with C, JavaScript, Python and Swift. I don't get it with Lua.

- 3 months, 3 weeks ago

I like Lua. But my favourite language is c++. And I think Lua=C languages + Pascal :)

- 3 months, 3 weeks ago

I’ve not thought about Pascal in years. The whole do...end format is very Pascal-like. There’s one bit of syntax that I really miss from Pascal, and that’s using a:=b for assignment. No more accidentally assigning values in if statements. 😁

- 3 months, 3 weeks ago

Thanks Stef, i got the logic. Will see if i can run with my own code in python!

- 3 months, 3 weeks ago

Cool. Let me know how it goes?

- 3 months, 3 weeks ago

Also... check the min and max values. I was messing about with the code before I pasted it and didn't set them back to what they should have been (corrected in my code now).

- 3 months, 3 weeks ago

Sure, Thanks! Will paste it here if it does work :)

- 3 months, 3 weeks ago

Can I learn Lua :) (I don't know anything about programming)?

- 3 months, 3 weeks ago

Lua and Python are both good languages to learn how to program. Python is much more commonly used, especially on brilliant.org. Brilliant.org even has a Programming with Python course. If you want to learn Lua after that, the fundamentals will carry over.

So, despite my liking for Lua, I'd recommend learning Python. 🙃

- 3 months, 3 weeks ago

OK, although I purchased the Premium for math, I will do it if I have time from school!

- 3 months, 3 weeks ago

Can you help me? I wrote a C++ program, but the numbers are too big. I heard in python there are no limits :) I'm not familiar in python programming. I can solve it with hours of programming(vectors, save to txt, read from txt etc.), but I think you can help me.

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 #include #include using namespace std; long long int power(int w, int b); int check_power(int a, int b, int c, int d); long long int solution(int n, int theta); int main() { for(int n=1;n<=50;n++){ int j=2*n; long long int a=solution(j,0), b=solution(j-1,1); if((a >possible; vector temp; temp.resize(4); for(int a=1;a<=j;a++) for(int b=a;b>0;b--) for(int c=b;c>0;c--){ int d=(j)/(a*b*c); if(a*b*c*d!=j||d>c||check_power(a-1,b-1,c-1,d-1)!=theta) continue; temp[0]=a; temp[1]=b; temp[2]=c; temp[3]=d; possible.push_back(temp); } if(possible.size()==0) return -1; for(int x=0;x<4;x++) minimum[x]=possible[0][x]; for(int x=1;x0) k*=power(w,r); } if(l>k) continue; for(int w=0;w<4;w++) minimum[w]=possible[x][w]; } long long int output=1; for(int x=0;x<4;x++) output*=power(x,minimum[x]-1); return output; } 

- 2 months, 2 weeks ago

The program isn't complete. As you can see this works with only 2,3,5 and 7. I need to add other primes. This is the problem.

- 2 months, 2 weeks ago

I heard in python there are no limits :)

And the garbage collector is made of gold. :) In truth, I hear a lot of good things about Python but never really liked it much myself. Much of what I do these days most of what I do is in Lua, which has 64-bit numbers. If I need an integer bigger than that then I either look to see if I can simplify the problem or pull out my clunky-and-in-need-of-a-rewrite library that stores integers as strings and has functions that can add, subtract etc.

There are libraries that handle big numbers. You should be able to find one (or many) for C++. Or, if you go down the route of writing your own solution, that's quite rewarding, too.

(I just had a glance at the problem and don't see where big numbers come into it. Did you link the right problem? Or have I missed something?) (edit: looked at your output. OK... those numbers are bigger than I would have expected).

- 2 months, 2 weeks ago

A factor $f$ of a number $n = p_{1}^{m_{1}} \cdot p_{2}^{m_{2}} \cdot p_{3}^{m_{3}} \ldots$ must be a number with prime exponents which are less than or equal to the exponents of the number. To make things simple, here is an example: $60 = 2^2 \cdot 3^1 \cdot 5^1$. Without Brute-forcing, we can think logically here. If a factor $f$ can be represented here, say 15 which is equal to $3^1 \cdot 5^1$, the factor's prime exponents will be less than or equal to the prime exponents of $n$. In this case, they are equal

Taking this a step further, for each prime exponent say $m_{1}$, there will be $m_{1} + 1$ options to choose for a power. For the number 60 and specifically prime power of 2, we have $2^{m_{1}}, m_{1} \in \{0, 1, 2\}$ so there are 3 options.

Similarly each of the $m_{i^{th}}$ exponent will have $m_{i} + 1$ options.

The total options will thus equal the product of all $= (m_{1} + 1) \cdot (m_{2} + 1) \cdot (m_{2} + 1) \ldots$

- 3 months, 3 weeks ago

Thanks @Mahdi Raza! Also, as @Finnley Paolella stated, the answer to the question can be $125000$, can there be a general formula of that also?

- 3 months, 3 weeks ago

I don't think there is a closed-from general formula. It also depends on the base we choose, a number in base 2 will have more digits than a number in base 10. As I said in my comment, the general strategie will be the following:

1. factor $m$

2. try out different possibilites

- 3 months, 3 weeks ago

So if we are given 1 more condition, can there be a unique solution?

- 3 months, 3 weeks ago

The thing about those number theories problems is that it is hard to tell how many solutions there are, because prime numbers are more or less randomly distributed along the number line. So it can easily be that there is just one solution, especially if the number m can only be factored in a few different ways. For example, if we were to find a 5 digit number with 17 factors, there will be a unique solution! You can find it using the strategy I provided :)

- 3 months, 3 weeks ago

Is it $65536$?

- 3 months, 3 weeks ago

Yes ;)

- 3 months, 3 weeks ago

That was easy.. $2^{16}$

- 3 months, 3 weeks ago

So, the question which I gave is of no use?

- 3 months, 3 weeks ago

The problem hasn't got a unique solution. A more interesting problem would be: How many solutions are there? But I think this is a very time expensive problem (at least if you don't want to program it).

- 3 months, 3 weeks ago

I don't know programming :(

- 3 months, 3 weeks ago

I think it's possible that I don't understand the question. (edit: Narrator: "He didn't understand the question.")

The lowest composite number I can generate with $2$ distinct factors is $2 \times 3 = 6 ( = 3! )$

The lowest composite number I can generate with $3$ distinct factors is $2 \times 3 \times 4 = 24 ( = 4! )$

...

The lowest composite number I can generate with $n$ distinct factors is $(n+1)!$

...

The lowest composite number I can generate with $28$ distinct factors is $29! = 8841761993739701954543616000000$. This has a lot more than 6 digits. What is it that I don't understand here?

(Additional, just for laughs, if I insist that the $28$ factors are prime factors, I get: $2566376117594999414479597815340071648394470$.)

- 3 months, 3 weeks ago

@Stef Smith, Sir, I did not understand what you mean. Please elaborate!

- 3 months, 3 weeks ago

A misunderstading of how factors work. Some days my brain doesn't work so well. :)

- 3 months, 3 weeks ago

Oh no problem then :)

- 3 months, 3 weeks ago

Hey Stef, The number 24 has more than 3 factors. It has 8 factors: 1, 2, 3, 4, 6, 8, 12, 24. Therefore, applying the factorial function does not work because 29! factorial has way more factors than 29.

I hope this helps :)

- 3 months, 3 weeks ago

Ah... I understand. Thanks.

- 3 months, 3 weeks ago

So we're looking for something like 100032 which has the 28 factors (1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 48, 64, 96, 192, 521, 1042, 1563, 2084, 3126, 4168, 6252, 8336, 12504, 16672, 25008, 33344, 50016, 100032).

- 3 months, 3 weeks ago

I now think(thanks to @Finnley Paolella) that there are too many such numbers!

- 3 months, 3 weeks ago

125000?

- 3 months, 3 weeks ago

Yes, it is one of the answers I know of now, but as Finnley Paolella stated, it is not unique.

- 3 months, 3 weeks ago

- 3 months, 3 weeks ago

Great Question, But yes has way too many solutions.

- 3 months, 3 weeks ago

@Vinayak Srivastava,if product of factors are given,then a unique solution can be determined.

- 2 months, 3 weeks ago

- 2 months, 3 weeks ago

- 2 months, 3 weeks ago

- 2 months, 2 weeks ago

Read a little bit, but got bored, I don't know why!

- 2 months, 2 weeks ago

I started to read and found a programming task so I connected them and started to prove that to the first 50 numbers :)

- 2 months, 2 weeks ago

Great!

- 2 months, 2 weeks ago

Ohh! I forgot to post the results :)

- 2 months, 2 weeks ago

The same happens with me all time.😅

- 2 months, 2 weeks ago

Task: Find the least number n that can we represented as a product n = a ∙ b in k (1 ≤ k ≤ 50) ways. Products a ∙ b and b ∙ a are the same, all numbers are positive integers.

This isn't the same problem. For example 4 has 3 divisors(1,2,4), but we can write this in only two ways : 1x4 and 2x2.

The result is:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 1 1 2 4 3 12 4 24 5 36 6 60 7 192 8 120 9 180 10 240 11 576 12 360 13 1296 14 900 15 720 16 840 17 9216 18 1260 19 786432 20 1680 21 2880 22 15360 23 3600 24 2520 25 6480 26 61440 27 6300 28 6720 29 2359296 30 5040 31 3221225472 32 7560 33 46080 34 983040 35 25920 36 10080 37 206158430208 38 32400 39 184320 40 15120 41 44100 42 20160 43 5308416 44 107520 45 25200 46 2985984 47 9663676416 48 30240 49 233280 50 45360 

- 2 months, 2 weeks ago