## Poll

 I love math! 18 votes (50%) Math is great. 13 votes (36.11%) My religion is mathology. 5 votes (13.88%) Women didn't speak to me until I was 30. 2 votes (5.55%) Total eclipse reminder -- 04/08/2024 11 votes (30.55%) I steal cutlery from restaurants. 3 votes (8.33%) I should just say what's on my mind. 6 votes (16.66%) Who makes up these awful names for pandas? 5 votes (13.88%) I like to touch my face. 11 votes (30.55%) Pork chops and apple sauce. 8 votes (22.22%)

36 members have voted

Wizard
Joined: Oct 14, 2009
• Posts: 24200
December 7th, 2021 at 11:38:33 AM permalink

It's not whether you win or lose; it's whether or not you had a good bet.
Gialmere
Joined: Nov 26, 2018
• Posts: 2320
December 7th, 2021 at 11:38:42 AM permalink
Quote: ChesterDog

810,810,000 = 24345471111131

?

...you're definitely on the right path as 810,810,000 is the smallest number with 1,000 divisors.
Have you tried 22 tonight? I said 22.
Wizard
Joined: Oct 14, 2009
• Posts: 24200
Thanks for this post from:
December 7th, 2021 at 11:42:44 AM permalink

1,060,290,000 = 2^3 * 3^3 * 5^3 * 7 * 11 * 17
It's not whether you win or lose; it's whether or not you had a good bet.
ChesterDog
Joined: Jul 26, 2010
• Posts: 1025
December 7th, 2021 at 12:05:58 PM permalink
Quote: Gialmere

Quote: ChesterDog

810,810,000 = 24345471111131

?

...you're definitely on the right path as 810,810,000 is the smallest number with 1,000 divisors.

1,969,110,000 = 243454111131171

?
Gialmere
Joined: Nov 26, 2018
• Posts: 2320
December 7th, 2021 at 12:13:58 PM permalink
Quote: Wizard

1,060,290,000 = 2^3 * 3^3 * 5^3 * 7 * 11 * 17

Quote: ThatDonGuy

2^4 x 3^4 x 5^4 x 7 x 11 x 17 = 1,060,290,000

Correct!!

The number of divisors of a natural number may be determined by writing down its prime factorization. The Fundamental Theorem of Arithmetic guarantees that the prime factorization is unique.

Let n = p1a1 · ... · prar , where p1 ... pr are prime numbers, and a1 ... ar are positive integers.
Now, each divisor of n is composed of the same prime factors, where the ith exponent can range from 0 to ai.
Hence there are a1 + 1 choices for the first exponent, a2 + 1 choices for the second, and so on.
Therefore the number of positive divisors of n is (a1 + 1)(a2 + 1) ... (ar + 1).

The unique prime factorization of 1000 is 23 · 53, which contains six prime factors.
So if n has exactly 1000 positive divisors, each ai + 1 is a divisor of 1000, where i may take any value between 1 and 6.
At one extreme, when i = 1, a1 + 1 = 1000, so a1 = 999, and the smallest integer of this form is 2999, a number with 301 decimal digits.
At the other extreme, when i = 6, a1 = a2 = a3 = 1, and a4 = a5 = a6 = 4.
In this latter case, the smallest integer of this form is clearly 24 · 34 · 54 · 7 · 11 · 13 = 810,810,000.

In fact, of all the natural numbers with exactly 1000 divisors, 810,810,000 is the smallest. A demonstration by enumeration follows. Having established this result, it will be a simple matter to find the smallest integer greater than 1 billion that has 1000 divisors.

Let n = 24 · 34 · 54 · 7 · 11 · 13.
The smallest integer that can be obtained by combining the six prime factors in various ways is:

5 · 5 · 5 · 4 · 2, yielding 24 · 34 · 54 · 73 · 11 = (72/13)n > 3n
10 · 5 · 5 · 2 · 2, yielding 29 · 34 · 54 · 7 · 11 = (25/13)n > 2n
25 · 5 · 2 · 2 · 2, yielding 224 · 34 · 5 · 7 · 11 = (220/53 · 13)n > 500n
8 · 5 · 5 · 5, yielding 27 · 34 · 54 · 74 = (23 · 73/11 · 13)n > 10n
10 · 5 · 5 · 4, yielding 29 · 34 · 54 · 73 = (25 · 72/11 · 13)n > 10n
10 · 10 · 5 · 2, yielding 29 · 39 · 54 · 7 = (25 · 34/11 · 13)n > 15n
20 · 5 · 5 · 2, yielding 219 · 34 · 54 · 7 = (215/11 · 13)n > 200n
25 · 5 · 4 · 2, yielding 224 · 34 · 53 · 7 = (220/5 · 11 · 13)n > 1000n
Any other combination of the prime factors would contain a power of 2 greater than 30, which, on its own, would yield an integer greater than 1 billion.
Therefore, the smallest natural number with exactly 1000 divisors is 810,810,000.

To find the smallest number greater than 1 billion with exactly 1000 divisors, we must substitute larger prime(s) in the factorization of 810,810,000.
Logically, the smallest such substitution must be either: replace 54 · 7 with 5 · 74, or replace 13 with 17.
Arithmetically, we find that 24 · 34 · 5 · 74 · 11 · 13 = 2,224,862,640, while 24 · 34 · 54 · 7 · 11 · 17 = 1,060,290,000.

Therefore the smallest natural number greater than 1 billion that has exactly 1000 positive divisors is 1,060,290,000.

------------------------------------------------------------

...what color would your Lamborghini be?
Have you tried 22 tonight? I said 22.
ThatDonGuy
Joined: Jun 22, 2011
• Posts: 5356
Thanks for this post from:
December 7th, 2021 at 12:14:27 PM permalink
Quote: Gialmere

Find the smallest natural number greater than 1 billion (10^9) that has exactly 1000 positive divisors.

2^4 x 3^4 x 5^4 x 7 x 11 x 17 = 1,060,290,000

Wizard
Joined: Oct 14, 2009
• Posts: 24200
December 7th, 2021 at 12:35:19 PM permalink
Good puzzle. I think I'll make an Ask the Wizard question out of it. Here is a draft of my "solution."

First note the prime factorization of 1,000 is 5^3 * 2^3

Our answer should be in the form a^4 * b^4 * c^4 * d * e * f, where these terms are not necessarily different.

Why? Let's call the ultimate answer n.

All 1,000 factors of n will be have a prime factorization including 0 to 4 a's, for example. In other words, it can have 0 a's, 1 a, 2 a's, or 3 a's. That is five (0 to 4) possibilities for the number of a's in a factor.

All 1,000 factors of n will also have 0 to 4 b's, 0 to 4 c's, 0 or 1 d, 0 or 1 e, and 0 or 1 f.

This makes 5*5*5*2*2*2 = 1,000 possible factorizations.

Now, what should a to f be? It's obviousl they should all be prime. Let's start with the a=2, b=3, c=5, d=7, e=11, and f=13. 2^4 * 3^4 * 5^4 * 7 * 11 * 13 = 810,810,000, which is too small.

Let's increase f to 17 and we have 2^4 * 3^4 * 5^4 * 7 * 11 * 17 = 1,060,290,000, which meets the condition of being greater than a billion.

I realize this isn't proving there isn't another solution that is between a billion and my answer, but I have it on good authority my answer is correct.
It's not whether you win or lose; it's whether or not you had a good bet.
ThatDonGuy
Joined: Jun 22, 2011
• Posts: 5356
December 7th, 2021 at 2:01:35 PM permalink
Quote: Wizard

Good puzzle. I think I'll make an Ask the Wizard question out of it. Here is a draft of my "solution."

First note the prime factorization of 1,000 is 5^3 * 2^3

Our answer should be in the form a^4 * b^4 * c^4 * d * e * f, where these terms are not necessarily different.

Why? Let's call the ultimate answer n.

All 1,000 factors of n will be have a prime factorization including 0 to 4 a's, for example. In other words, it can have 0 a's, 1 a, 2 a's, or 3 a's. That is five (0 to 4) possibilities for the number of a's in a factor.

All 1,000 factors of n will also have 0 to 4 b's, 0 to 4 c's, 0 or 1 d, 0 or 1 e, and 0 or 1 f.

This makes 5*5*5*2*2*2 = 1,000 possible factorizations.

Now, what should a to f be? It's obviousl they should all be prime. Let's start with the a=2, b=3, c=5, d=7, e=11, and f=13. 2^4 * 3^4 * 5^4 * 7 * 11 * 13 = 810,810,000, which is too small.

Let's increase f to 17 and we have 2^4 * 3^4 * 5^4 * 7 * 11 * 17 = 1,060,290,000, which meets the condition of being greater than a billion.

I realize this isn't proving there isn't another solution that is between a billion and my answer, but I have it on good authority my answer is correct.

Actually, in the form a^4 * b^4 * c^4 * d * e * f, they do all have to be differrent. If, say, e = f, then you are counting the values with one f but not two twice.
It needs to be:
1000 = (P2 + 1) * (P3 + 1) * (P5 + 1) * (P7 + 1) * ...
where Pn is the number of times prime factor n appears in the number.
It could be a^4 b^4 c^4 d e f, but it could also be a^4 b^4 c^4 d^3 e, or a^4 b^4 c^4 d^7, or a^9 b^4 c^4 d e, among other possibilities. Add 1 to each exponent, and the product of the results = 1000.

TwelveOr21
Joined: Nov 18, 2018
• Posts: 58
December 8th, 2021 at 12:45:46 AM permalink
Quote: Gialmere

...what color would your Lamborghini be?

I like the quote - the billion dollars has probably already been through the charities over the years that are looking at solutions to famine, obviously not enough, so the billion probably wouldn't end world hunger.

For the record, I'd go Yellow, authentic.
Wizard
Joined: Oct 14, 2009
• Posts: 24200
December 8th, 2021 at 5:40:44 AM permalink
Quote: ThatDonGuy

First note the prime factorization of 1,000 is 5^3 * 2^3

Our answer should be in the form a^4 * b^4 * c^4 * d * e * f, where these terms are not necessarily different.

Why? Let's call the ultimate answer n.

All 1,000 factors of n will be have a prime factorization including 0 to 4 a's, for example. In other words, it can have 0 a's, 1 a, 2 a's, or 3 a's. That is five (0 to 4) possibilities for the number of a's in a factor.

All 1,000 factors of n will also have 0 to 4 b's, 0 to 4 c's, 0 or 1 d, 0 or 1 e, and 0 or 1 f.

This makes 5*5*5*2*2*2 = 1,000 possible factorizations.

Now, what should a to f be? It's obviousl they should all be prime. Let's start with the a=2, b=3, c=5, d=7, e=11, and f=13. 2^4 * 3^4 * 5^4 * 7 * 11 * 13 = 810,810,000, which is too small.

Let's increase f to 17 and we have 2^4 * 3^4 * 5^4 * 7 * 11 * 17 = 1,060,290,000, which meets the condition of being greater than a billion.

I realize this isn't proving there isn't another solution that is between a billion and my answer, but I have it on good authority my answer is correct.

Actually, in the form a^4 * b^4 * c^4 * d * e * f, they do all have to be differrent. If, say, e = f, then you are counting the values with one f but not two twice.
It needs to be:
1000 = (P2 + 1) * (P3 + 1) * (P5 + 1) * (P7 + 1) * ...
where Pn is the number of times prime factor n appears in the number.
It could be a^4 b^4 c^4 d e f, but it could also be a^4 b^4 c^4 d^3 e, or a^4 b^4 c^4 d^7, or a^9 b^4 c^4 d e, among other possibilities. Add 1 to each exponent, and the product of the results = 1000.