Short Question, Long Number

How many digits does the least common multiple of the numbers 1 1 , 2 2 , 3 3 , 4 4 , ..., 100 100 have?


The answer is 41.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

here is a solution, that is fundamentally not different from what is provided by @Kaizen Cyrus . However, there are estimations involved, which may influence the accuracy of the final solution.

If we define L C M ( 1 , 2 , , n ) = f ( n ) LCM(1,2,\dots,n)=f(n) , then there is a relation

e Λ ( n ) = f ( n ) f ( n 1 ) e^{\Lambda(n)}=\frac{f(n)}{f(n-1)}

Λ ( n ) \Lambda(n) is Mangoldt function.

e Λ ( n ) e Λ ( n 1 ) e Λ ( 2 ) = f ( n ) f ( n 1 ) f ( n 1 ) f ( n 2 ) f ( 2 ) f ( 1 ) = f ( n ) f ( 1 ) = f ( n ) 1 e^{\Lambda(n)}\cdot e^{\Lambda(n-1)} \cdot \dots \cdot e^{\Lambda(2)} =\frac{f(n)}{f(n-1)} \cdot \frac{f(n-1)}{f(n-2)} \cdot \dots \cdot \frac{f(2)}{f(1)}=\frac{f(n)}{f(1)}=\frac{f(n)}{1}

For n = 100 n=100

e n = 2 100 Λ ( n ) = e n = 1 100 Λ ( n ) = f ( 100 ) e^{\sum_{n=2}^{100} \Lambda(n)}=e^{\sum_{n=1}^{100} \Lambda(n)} =f(100)

It has been proven that

lim x n = 1 x Λ ( n ) x = 1 \lim _{x \rightarrow \infty }\frac{\sum_{n=1}^{x} \Lambda(n)}{x}=1

hence n = 1 x Λ ( n ) \sum_{n=1}^{x} \Lambda(n) can be approximated by x x . Therefore, the answer to our question can be approximated to be

f ( 100 ) = e n = 2 100 Λ ( n ) e 100 f(100)= e^{\sum_{n=2}^{100} \Lambda(n)} \approx e^{100}

the number of digits is calculated to be log 10 e 100 = 43 \log_{10}e^{100}=43 , which is 2 units away from the correct answer.

Kaizen Cyrus
Jun 4, 2020

To find the LCM of the said sequence of numbers, we must find all largest p n p^{n} , where p p is a prime number and that p n < 100 p^{n}<100 , and multiply them.

The p n p^{n} are:

2 6 43 3 4 47 5 2 53 7 2 59 11 61 13 67 17 71 19 73 23 79 29 83 31 89 37 97 41 \begin{array}{cccccccccc} 2^{6} &&&&&&&&& 43 \\ 3^{4} &&&&&&&&& 47 \\ 5^{2} &&&&&&&&& 53 \\ 7^{2} &&&&&&&&& 59 \\ 11 &&&&&&&&& 61 \\ 13 &&&&&&&&& 67 \\ 17 &&&&&&&&& 71 \\ 19 &&&&&&&&& 73 \\ 23 &&&&&&&&& 79 \\ 29 &&&&&&&&& 83 \\ 31 &&&&&&&&& 89 \\ 37 &&&&&&&&& 97 \\ 41 &&&&&&&&& \end{array}

The product of the numbers above is 6.972 × 1 0 40 \approx 6.972 × 10^{40} , which has 41 \boxed{41} digits.

Isn't there any other (more elegant) method to solve this?

Vinayak Srivastava - 1 year ago

Log in to reply

There is. Take log and then add the values. You'll get 40.52 something, accounting for 41 digits.

Aryan Sanghi - 1 year ago

Log in to reply

I haven't studied log.

Vinayak Srivastava - 1 year ago

Log in to reply

@Vinayak Srivastava Ok.... Then you need to multiply using a calculator.

Aryan Sanghi - 1 year ago

Log in to reply

@Aryan Sanghi I did that only :)

Vinayak Srivastava - 1 year ago

There's no other way. This question is pure brute force only.

Pi Han Goh - 1 year ago

Log in to reply

Yes sir, in that sense, there isn't any method.

Aryan Sanghi - 1 year ago

I was also on the path to multiplying all the primes, and its powers less than 100, but I thought there has to be a better way. If anyone get's another approach, please share!

Mahdi Raza - 1 year ago

As I said to Vinayak, you can take log and all all values.

Aryan Sanghi - 1 year ago

Log in to reply

That is also very tedious!

Mahdi Raza - 1 year ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...