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
3 months, 3 weeks 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 - 3 months, 3 weeks 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 - 3 months, 3 weeks 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 - 3 months, 3 weeks 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 - 3 months, 3 weeks ago

Log in to reply

How did you calculate this?

Vinayak Srivastava - 3 months, 3 weeks 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 - 3 months, 3 weeks ago

Log in to reply

@Stef Smith WOW!!

Vinayak Srivastava - 3 months, 3 weeks ago

Log in to reply

Hey Stef, that is amazing! Great visualisation :)

Finnley Paolella - 3 months, 3 weeks ago

Log in to reply

Thanks.

Stef Smith - 3 months, 3 weeks 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 - 3 months, 3 weeks 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 - 3 months, 3 weeks 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 - 3 months, 3 weeks 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 - 3 months, 3 weeks ago

Log in to reply

@Stef Smith Lua??? Retro gaming?

Páll Márton (no activity) - 3 months, 3 weeks ago

Log in to reply

@Páll Márton (no activity) 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 - 3 months, 3 weeks 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 (no activity) - 3 months, 3 weeks ago

Log in to reply

@Páll Márton (no activity) 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 - 3 months, 3 weeks 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 - 3 months, 3 weeks ago

Log in to reply

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

Stef Smith - 3 months, 3 weeks 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 - 3 months, 3 weeks ago

Log in to reply

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

Mahdi Raza - 3 months, 3 weeks ago

Log in to reply

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

Vinayak Srivastava - 3 months, 3 weeks 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 - 3 months, 3 weeks 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 - 3 months, 3 weeks ago

Log in to reply

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 <iostream>
#include <vector>
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<b||b==-1)&&a!=-1) cout<<a;
        else cout << b;
        cout << endl;
    }
    return 0;
}
long long int power(int w, int b){
    int a=(w==0)?2:(w==1)?3:(w==2)?5:7;
    if(b<1)    return 1;
    long long int toreturn=a;
    for(int x=1;x<b;x++)
        toreturn*=a;
    return toreturn;
}
int check_power(int a, int b, int c, int d){
    if(a%2) return 0;
    if(b%2) return 0;
    if(c%2) return 0;
    if(d%2) return 0;
    return 1;
}
long long int solution(int j, int theta){
    int minimum[4];
    vector<vector<int> >possible;
    vector<int> 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;x<possible.size();x++){
        long long int k=1, l=1;
        for(int w=0;w<4;w++){
            int r=minimum[w]-possible[x][w];
            if(r<0) l*=power(w,-r);
            else if(r>0)    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;
}

Páll Márton (no activity) - 2 months, 2 weeks ago

Log in to reply

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.

Páll Márton (no activity) - 2 months, 2 weeks ago

Log in to reply

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

Stef Smith - 2 months, 2 weeks 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 - 3 months, 3 weeks 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 - 3 months, 3 weeks 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 - 3 months, 3 weeks ago

Log in to reply

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

Vinayak Srivastava - 3 months, 3 weeks 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 - 3 months, 3 weeks ago

Log in to reply

@Finnley Paolella Is it 6553665536?

Vinayak Srivastava - 3 months, 3 weeks ago

Log in to reply

@Vinayak Srivastava Yes ;)

Finnley Paolella - 3 months, 3 weeks ago

Log in to reply

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

Vinayak Srivastava - 3 months, 3 weeks ago

Log in to reply

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

Vinayak Srivastava - 3 months, 3 weeks 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 - 3 months, 3 weeks ago

Log in to reply

@Finnley Paolella I don't know programming :(

Vinayak Srivastava - 3 months, 3 weeks 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 - 3 months, 3 weeks ago

Log in to reply

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

Vinayak Srivastava - 3 months, 3 weeks ago

Log in to reply

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

Stef Smith - 3 months, 3 weeks ago

Log in to reply

@Stef Smith Oh no problem then :)

Vinayak Srivastava - 3 months, 3 weeks 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 - 3 months, 3 weeks ago

Log in to reply

Ah... I understand. Thanks.

Stef Smith - 3 months, 3 weeks 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 - 3 months, 3 weeks ago

Log in to reply

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

Vinayak Srivastava - 3 months, 3 weeks ago

Log in to reply

125000?

Páll Márton (no activity) - 3 months, 3 weeks 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 - 3 months, 3 weeks ago

Log in to reply

Log in to reply

@Vinayak Srivastava

Great Question, But yes has way too many solutions.

Vikram Karki - 3 months, 3 weeks ago

Log in to reply

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

Kriti Kamal - 2 months, 3 weeks ago

Log in to reply

Seems interesting! Please elaborate!

Vinayak Srivastava - 2 months, 3 weeks ago

Log in to reply

read it

Kriti Kamal - 2 months, 3 weeks ago

Log in to reply

@Kriti Kamal @Vinayak Srivastava,have you read it:-)

Kriti Kamal - 2 months, 2 weeks ago

Log in to reply

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

Vinayak Srivastava - 2 months, 2 weeks ago

Log in to reply

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

Páll Márton (no activity) - 2 months, 2 weeks ago

Log in to reply

@Páll Márton (no activity) Great!

Kriti Kamal - 2 months, 2 weeks ago

Log in to reply

@Kriti Kamal Ohh! I forgot to post the results :)

Páll Márton (no activity) - 2 months, 2 weeks ago

Log in to reply

@Vinayak Srivastava The same happens with me all time.😅

Kriti Kamal - 2 months, 2 weeks ago

Log in to reply

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

Páll Márton (no activity) - 2 months, 2 weeks ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...