Find the largest integer n such that n is divisible by all positive integers less than 3 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.
Thank you for your solution.
I don't understand why n having to be divisible by 9 would be a problem, though. We should take a multiple of L 9 . Of course, as L 9 = 2 5 2 0 > 1 3 3 , we have to take a multiple of L 1 3 , and so on.
I think that the question is: is L n > ( n + 1 ) 3 for all n > 7 ? It seems to be so, but how can we prove it?
Log in to reply
Good point. I'm not sure if I had something in mind 18 months ago but regardless, I think that Bertrand's Postulate, (BP), might be useful here. As you point out, if the number we are seeking is greater than 4 2 0 then it must be at least 8 4 0 , and so it must be must be divisible by 2 5 2 0 , and so must be divisible by 3 6 0 3 6 0 , and so on. As these successive intervals are at the very least doubling in length, by BP each interval will contain a new prime, at this stage in excess of 1 1 > 8 , and so the cubed root will increase by a factor greater than 2 , guaranteeing by BP the introduction of another prime in the next interval. And so on, ad infinitum. Not a formal proof, but I hope the concept makes sense.
Log in to reply
It's convincing! Thank you for the quick answer :)
Why wouldn't the answer be the third power of x factorial for x approaching infinity? The cube root of x factorial cubed is x factorial, which includes all factors of x factorial.
Log in to reply
I don't think that is the case. Take n = ( 3 ! ) 3 = 2 1 6 as an example. We would then require that 2 1 6 is divisible by all integers less than 3 ! = 6 , but 2 1 6 is not divisible by 5 . In general ( m ! ) 3 is not divisible by m ! − 1 , at the very least.
how is it that 11^(1/3)~2.23, but 11 is not divisible by 2?
Log in to reply
We're just looking for the largest integer n ; it doesn't matter if smaller values don't meet the condition.
Definition: g : N → N , g ( n ) : = l c m ( 1 ; … ; ⌈ 3 ( n ) ⌉ − 1 ) )
We have to find the largest n ∈ N such that n = c g ( n ) , c ∈ N . Obviously, g ( n ) only increases after every perfect cube n = m 3 - lets take a look at the first few values: m a m : = m 3 + 1 g ( a m ) 5 1 2 6 6 0 6 2 1 7 6 0 7 3 4 4 4 2 0 8 5 1 3 8 4 0 9 7 3 0 2 5 2 0 1 0 1 0 0 1 2 5 2 0 1 1 1 3 3 2 2 7 7 2 0 …
It seems to be the case that g ( a m ) > a m + 1 for m ≥ 8 . If we can prove that fact, there cannot be a solution n ≥ a 8 ! Using link Betrand's Postulate ( ∗ ) , we can be sure to have a prime factor 8 ⋅ 2 k < p k < 8 ⋅ 2 k + 1 , k ≥ 0
These prime factors are the reason that g ( a m ) grows very fast for m ≥ 8 g ( a 8 ⋅ 2 k ) g ( a 8 ⋅ 2 k + 1 ) a m + 1 a 2 m + 1 = l c m ( 1 ; … ; 8 ⋅ 2 k ) l c m ( 1 ; … ; 8 ⋅ 2 k + 1 ) ( ∗ ) ≥ p k > 8 ⋅ 2 k ≥ 8 = ( m + 1 ) 3 + 1 ( 2 m + 1 ) 3 + 1 ≤ ( m + 1 ) 3 + 1 ( 2 m + 2 ) 3 + 8 ≤ 8 ⇒ ⇒ g ( a 8 ⋅ 2 k ) a 8 ⋅ 2 k + 1 < g ( a 8 ) ⋅ 8 k ≤ a 9 ⋅ 8 k < g ( a 8 ) ⋅ 8 k = g ( a 8 ⋅ 2 k ) , k ≥ 0
Both sequences are monotonically increasing, so there can not be a solutiom in any interval [ a 8 ⋅ 2 k ; a 8 ⋅ 2 k + 1 ) and k ≥ 0 . Using the table, we find the largest solution to n = c g ( n ) < a 8 = 5 1 3 to be n = 4 2 0
Rem.: It is important that both sequences are monotonic: We only checked them on the borders of intervals and assumed nothing bad happens in between. The fact that both sequences are increasing makes sure there is no point in between where the lower sequence shortly has greater values than the other!
we're looking for where the floor[{n=LCM(1,2,3...x)}^1/3]=x which happens at x=7 n=420
x | x^3 | n=LCM(1 to x) |
1 | 1 | 1 |
2 | 8 | 2 |
3 | 27 | 6 |
4 | 64 | 12 |
5 | 125 | 60 |
6 | 216 | 60 |
7 | 343 | 420 |
8 | 512 | 840 |
9 | 729 | 2520 |
Problem Loading...
Note Loading...
Set Loading...
First note that we can rule out the option of n being a perfect cube k 3 with k > 2 , since then n could not be divisible by k − 1 . (With n = k = 1 there are no positive integers less than 3 n , and with n = 8 , k = 2 , while we do have n divisible by all integers less than k we will be able to find larger n satisfying the requirements.) This follows from the fact that
( k − 1 ) ∣ ( k 3 − 1 ) , and thus n = k 3 ≡ 1 ( m o d ( k − 1 ) ) .
Now let m = ⌊ 3 n ⌋ . Then for n (not a perfect cube) to be divisible by all positive integers ≤ m we require it to be a multiple of L m = l c m ( 1 , 2 , . . . . , ( m − 1 ) , m ) .
Now L 8 = 2 3 ∗ 3 ∗ 5 ∗ 7 = 8 4 0 > 9 3 , so any such n would also have to be divisible by 9 . Thus we will require that n < 8 3 = 5 1 2 . Next, we have that L 7 = 2 2 ∗ 3 ∗ 5 ∗ 7 = 4 2 0 > 7 3 = 3 4 3 , and since this is the greatest integer n less than 8 3 and greater than 7 3 that is divisible by all positive integers less than 3 n we can conclude that 4 2 0 is the number we are seeking.