How to find an nn-digit number with mm number of factors?

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

There is a 66-digit number with 2828 distinct factors. What is the number?

I searched and found that

Number of factors of a number of the form p1m1×p2m2×p3m3{p_1}^{m_1} \times {p_2}^{m_2} \times {p_3}^{m_3} \cdots is (m1+1)×(m2+1)×(m3+1)(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 nn-digit number with mm number of factors?

Note by Vinayak Srivastava
1 month ago

No vote yet
1 vote

  Easy Math Editor

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.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. 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 1

paragraph 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×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

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

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

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

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

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

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

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

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

Finnley Paolella - 1 month ago

Log in to reply

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

Vinayak Srivastava - 1 month ago

Log in to reply

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

23×36=5832 2^3 \times 3^6 = 5832 is too small

23×56=125000 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:

26×111×4431=311872 2^6 \times 11^1 \times 443^1 = 311872

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

Finnley Paolella - 1 month ago

Log in to reply

A factor ff of a number n=p1m1p2m2p3m3n = 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=22315160 = 2^2 \cdot 3^1 \cdot 5^1. Without Brute-forcing, we can think logically here. If a factor ff can be represented here, say 15 which is equal to 31513^1 \cdot 5^1, the factor's prime exponents will be less than or equal to the prime exponents of nn. In this case, they are equal

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

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

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

Mahdi Raza - 1 month ago

Log in to reply

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

Vinayak Srivastava - 1 month ago

Log in to reply

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 mm

  2. try out different possibilites

Finnley Paolella - 1 month ago

Log in to reply

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

Vinayak Srivastava - 1 month ago

Log in to reply

@Vinayak Srivastava 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 :)

Finnley Paolella - 1 month ago

Log in to reply

@Finnley Paolella Is it 6553665536?

Vinayak Srivastava - 1 month ago

Log in to reply

@Vinayak Srivastava Yes ;)

Finnley Paolella - 1 month ago

Log in to reply

@Finnley Paolella That was easy.. 2162^{16}

Vinayak Srivastava - 1 month ago

Log in to reply

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

Vinayak Srivastava - 1 month ago

Log in to reply

@Vinayak Srivastava 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).

Finnley Paolella - 1 month ago

Log in to reply

@Finnley Paolella I don't know programming :(

Vinayak Srivastava - 1 month ago

Log in to reply

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.)

Stef Smith - 1 month ago

Log in to reply

How did you calculate this?

Vinayak Srivastava - 1 month ago

Log in to reply

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.

Stef Smith - 1 month ago

Log in to reply

@Stef Smith WOW!!

Vinayak Srivastava - 1 month ago

Log in to reply

Hey Stef, that is amazing! Great visualisation :)

Finnley Paolella - 1 month ago

Log in to reply

Thanks.

Stef Smith - 1 month ago

Log in to reply

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

Mahdi Raza - 1 month ago

Log in to reply

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).

Stef Smith - 1 month ago

Log in to reply

@Stef Smith 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!

Mahdi Raza - 1 month ago

Log in to reply

@Mahdi Raza 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)

Stef Smith - 1 month ago

Log in to reply

@Stef Smith Lua??? Retro gaming?

Páll Márton - 1 month ago

Log in to reply

@Páll Márton 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.

Stef Smith - 1 month ago

Log in to reply

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

Páll Márton - 1 month ago

Log in to reply

@Páll Márton 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. 😁

Stef Smith - 1 month ago

Log in to reply

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

Mahdi Raza - 1 month ago

Log in to reply

@Mahdi Raza Cool. Let me know how it goes?

Stef Smith - 1 month ago

Log in to reply

@Mahdi Raza 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).

Stef Smith - 1 month ago

Log in to reply

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

Mahdi Raza - 1 month ago

Log in to reply

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

Vinayak Srivastava - 1 month ago

Log in to reply

@Vinayak Srivastava 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. 🙃

Stef Smith - 1 month ago

Log in to reply

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

Vinayak Srivastava - 1 month ago

Log in to reply

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 22 distinct factors is 2×3=6(=3!)2 \times 3 = 6 ( = 3! )

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

...

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

...

The lowest composite number I can generate with 2828 distinct factors is 29!=8841761993739701954543616000000 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 2828 factors are prime factors, I get: 25663761175949994144795978153400716483944702566376117594999414479597815340071648394470.)

Stef Smith - 1 month ago

Log in to reply

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

Vinayak Srivastava - 1 month ago

Log in to reply

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

Stef Smith - 1 month ago

Log in to reply

@Stef Smith Oh no problem then :)

Vinayak Srivastava - 1 month ago

Log in to reply

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 :)

Finnley Paolella - 1 month ago

Log in to reply

Ah... I understand. Thanks.

Stef Smith - 1 month ago

Log in to reply

@Stef Smith 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).

Stef Smith - 1 month ago

Log in to reply

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

Vinayak Srivastava - 1 month ago

Log in to reply

125000?

Páll Márton - 1 month ago

Log in to reply

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

Vinayak Srivastava - 1 month ago

Log in to reply

Log in to reply

@Vinayak Srivastava

Great Question, But yes has way too many solutions.

Vikram Karki - 1 month ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...