Find the greatest positive integer n for which n is divisible by all positive integers whose cube is not greater than n
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.
A simple way to solve this problem. I love your aspect
Let p 3 ≤ n < ( p + 1 ) 3 . n must be a multiple of the LCM of all integers on [1,p]. Usually, the LCM seems to increase when we increment 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?
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
Log in to reply
Brilliant!!! Thank you!
You should post this as a solution.
I don't quite understand the question. Say, 420 is divisible by 210 and 2 1 0 3 = 9 2 6 1 0 0 0 > 4 2 0 . Shouldn't 1 be the answer?
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).
A possible approach:
assume numbers from 1 to y divide a number in the range from y 3 to ( y + 1 ) 3 . then
y 3 ≤ l c m { i } i = 1 y < ( y + 1 ) 3
note that l c m { i } i = 1 y is the least common multiplier fall the numbers form 1 to y .
also, we have
l c m { i } i = 1 y = p < y ∑ p l o g p y
trying a few values for y suggests that y ≤ 7 , in order for the very first inequality to hold true. then we take l c m { i } i = 1 7 = 4 2 0 , which is the answer.
I am not convinced by this approach. How can you prove that there won't be a bigger number later?
1 3 < n < 2 3 we have numbers of the form m . Greatest is 7 .
2 3 < n < 3 3 we have numbers of the form 2 m . Greatest is 2 6 .
3 3 < n < 4 3 we have numbers of the form 6 m . Greatest is 6 0 .
4 3 < n < 5 3 we have numbers of the form 1 2 m . Greatest is 1 2 0 .
5 3 < n < 6 3 we have numbers of the form 6 0 m . Greatest is 1 8 0 .
6 3 < n < 7 3 we have numbers of the form 6 0 m . Greatest is 3 0 0 .
7 3 < n < 8 3 we have numbers of the form 4 2 0 m . Greatest is 4 2 0 .
8 3 < n < 9 3 we have numbers of the form 8 4 0 m . Too high.
9 3 < n < 1 0 3 we have numbers of the form 2 5 2 0 m . Too high.
1 0 3 < n < 1 1 3 we have numbers of the form 2 5 2 0 m . Too high.
Claim , for k t h prime p k greater than 3 , p k 4 > p k + 1 3 .
Hence, 1 1 3 < n < 1 2 3 and 1 2 3 < n < 1 3 3 we need a number ≥ 1 1 ∗ 2 5 2 0 > 1 1 4 > 1 3 3 . Too high.
For k > 6 , p k 3 < n < p k + 1 3 we need a number ≥ 1 1 ∗ 1 3 ∗ . . . ∗ p k ∗ 2 5 2 0 > 1 1 4 ∗ 1 3 ∗ . . . ∗ p k > p k 4 > p k + 1 3 . Too high.
Hence max n is 4 2 0 .
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.
Problem Loading...
Note Loading...
Set Loading...
1 − 7 divisible by 1
> 2 3 : All even from 8 − 2 6 are divisible by both 1,2 and < 3 3
> 3 3 : All factors of 6 from 3 0 − 6 0 are divisible by 1,2,3 and < 4 3
> 4 3 : All factors of 12 from 7 2 − 1 2 0 are divisible by 1,2,3,4 and < 5 3
> 5 3 : Only 1 8 0 is divisible by 1,2,3,4,5 and < 6 3
> 6 3 : All factors of 60 from 2 4 0 − 3 0 0 are divisible by 1,2,3,4,5,6 and < 7 3
> 7 3 : only 4 2 0 is divisible by 1,2,3,4,5,6,7 and < 8 3
After this, there is 8 4 0 is the next integer divisible by 1,2,3,4,5,6,7 but it is > 9 3 and not divisible by 9