Bounded by cubes

Find the greatest positive integer n n for which n n is divisible by all positive integers whose cube is not greater than n n


The answer is 420.

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.

4 solutions

Mr. India
Apr 21, 2019

1 7 1-7 divisible by 1 1

> 2 3 >2^3 : All even from 8 26 8-26 are divisible by both 1,2 and < 3 3 <3^3

> 3 3 >3^3 : All factors of 6 from 30 60 30-60 are divisible by 1,2,3 and < 4 3 <4^3

> 4 3 >4^3 : All factors of 12 from 72 120 72-120 are divisible by 1,2,3,4 and < 5 3 <5^3

> 5 3 >5^3 : Only 180 180 is divisible by 1,2,3,4,5 and < 6 3 <6^3

> 6 3 >6^3 : All factors of 60 from 240 300 240-300 are divisible by 1,2,3,4,5,6 and < 7 3 <7^3

> 7 3 >7^3 : only 420 420 is divisible by 1,2,3,4,5,6,7 and < 8 3 <8^3

After this, there is 840 840 is the next integer divisible by 1,2,3,4,5,6,7 but it is > 9 3 >9^3 and not divisible by 9

A simple way to solve this problem. I love your aspect

vu van luan - 2 years, 1 month ago

Let p 3 n < ( p + 1 ) 3 p^3\le n<(p+1)^3 . n n must be a multiple of the LCM of all integers on [1,p]. Usually, the LCM seems to increase when we increment p p by 1. Your solutions seems to imply the LCM will consistently increase quickly enough that, above a certain number (420), the gap between LCMs is always greater than the gap between perfect cubes.

The LCM does not always increase when we increment p. For example, the LCM for [1,5] and the LCM for [1,6] are both 60. How do we know there will not be a later point at which the LCMs stagnate and the cubes "catch back up" to the LCMs?

Eric Nordstrom - 2 years, 1 month ago

Log in to reply

You are right. His solution just gives the answer. Here is my solution: I used the fact that n is greater than or equal to the lcm of numbers 1,2,..., k and that is greater than or equal to the lcm of 4 consecutive integers (k-3,k-2,k-1,k). This lcm is greater than or equal to the 1/6 of their product (1/6*k(k-1)(k-2)(k-3), prove this by yourself!), and that number is greater than (k+1)^3, for k>12. The last inequality can easily be proved by induction. So we look at the cases when k<=12. For k>7 lcm of 1,2,...,k is greater than (K+1)^3. And for k=7 we get the solution n=420, and for smaller k, n is smaller than 420, so this is the answer

Djoko Maric - 2 years, 1 month ago

Log in to reply

Brilliant!!! Thank you!

Eric Nordstrom - 2 years, 1 month ago

You should post this as a solution.

Eric Nordstrom - 2 years, 1 month ago

Log in to reply

@Eric Nordstrom I'm lazy to do it XD

Djoko Maric - 2 years, 1 month ago

I don't quite understand the question. Say, 420 is divisible by 210 and 21 0 3 = 9261000 > 420 210^{3} = 9261000 > 420 . Shouldn't 1 be the answer?

nomen incognita - 2 years, 1 month ago

Log in to reply

I had the same thought at first. But the question doesn't ask for a number for which the cube of every divisor is no greater than the number; it asks for a number that is divisible by all whole numbers whose cube is not greater than the number (but could be divisible by other numbers as well).

Eric Nordstrom - 2 years, 1 month ago

A possible approach:

assume numbers from 1 1 to y y divide a number in the range from y 3 y^3 to ( y + 1 ) 3 (y+1)^3 . then

y 3 l c m { i } i = 1 y < ( y + 1 ) 3 y^3 \leq lcm\{i\}_{i=1}^{y} <(y+1)^3

note that l c m { i } i = 1 y lcm\{i\}_{i=1}^{y} is the least common multiplier fall the numbers form 1 1 to y y .

also, we have

l c m { i } i = 1 y = p < y p l o g p y lcm\{i\}_{i=1}^{y}= \sum_{p<y} p^{log_{p}y}

trying a few values for y y suggests that y 7 y \leq 7 , in order for the very first inequality to hold true. then we take l c m { i } i = 1 7 = 420 lcm\{i\}_{i=1}^{7}=420 , which is the answer.

I am not convinced by this approach. How can you prove that there won't be a bigger number later?

Eric Nordstrom - 2 years, 1 month ago
Alex Burgess
Apr 25, 2019

1 3 < n < 2 3 1^3<n<2^3 we have numbers of the form m m . Greatest is 7 7 .

2 3 < n < 3 3 2^3<n<3^3 we have numbers of the form 2 m 2m . Greatest is 26 26 .

3 3 < n < 4 3 3^3<n<4^3 we have numbers of the form 6 m 6m . Greatest is 60 60 .

4 3 < n < 5 3 4^3<n<5^3 we have numbers of the form 12 m 12m . Greatest is 120 120 .

5 3 < n < 6 3 5^3<n<6^3 we have numbers of the form 60 m 60m . Greatest is 180 180 .

6 3 < n < 7 3 6^3<n<7^3 we have numbers of the form 60 m 60m . Greatest is 300 300 .

7 3 < n < 8 3 7^3<n<8^3 we have numbers of the form 420 m 420m . Greatest is 420 420 .

8 3 < n < 9 3 8^3<n<9^3 we have numbers of the form 840 m 840m . Too high.

9 3 < n < 1 0 3 9^3<n<10^3 we have numbers of the form 2520 m 2520m . Too high.

1 0 3 < n < 1 1 3 10^3<n<11^3 we have numbers of the form 2520 m 2520m . Too high.

Claim , for k t h k^{th} prime p k p_k greater than 3 3 , p k 4 > p k + 1 3 p_k^4 > p_{k+1}^3 .

Hence, 1 1 3 < n < 1 2 3 11^3<n<12^3 and 1 2 3 < n < 1 3 3 12^3<n<13^3 we need a number 11 2520 > 1 1 4 > 1 3 3 \geq 11*2520 > 11^4 > 13^3 . Too high.

For k > 6 k>6 , p k 3 < n < p k + 1 3 p_k^3<n<p_{k+1}^3 we need a number 11 13 . . . p k 2520 > 1 1 4 13 . . . p k > p k 4 > p k + 1 3 \geq 11*13*...*p_k * 2520 > 11^4 *13*...*p_k > p_k^4 > p_{k+1}^3 . Too high.

Hence max n n is 420 420 .


I believe the claim is true, but don't have a formal proof to hand.

Searching for successful small integers gives the first break in the sequence at 9. These gives an upper limit to be considered of the LCM of the positive integers from 1 to 8, which is 840. Searching the range from 1 to 840 gives 1,2,3,4,5,6,7,8,10,12,14,16,18,20,22,24,26,30,36,42,48,54,60,72,84,96,108,120,180,240,300 and 420.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...