Almost divisible by all

Find the largest integer n n such that n n is divisible by all positive integers less than n 3 \sqrt[3]{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.

3 solutions

First note that we can rule out the option of n n being a perfect cube k 3 k^{3} with k > 2 , k \gt 2, since then n n could not be divisible by k 1. k - 1. (With n = k = 1 n = k = 1 there are no positive integers less than n 3 , \sqrt[3]{n}, and with n = 8 , k = 2 , n = 8, k = 2, while we do have n n divisible by all integers less than k k we will be able to find larger n n satisfying the requirements.) This follows from the fact that

( k 1 ) ( k 3 1 ) , (k - 1)|(k^{3} - 1), and thus n = k 3 1 ( m o d ( k 1 ) ) . n = k^{3} \equiv 1 \pmod{(k - 1)}.

Now let m = n 3 . m = \lfloor \sqrt[3]{n} \rfloor. Then for n n (not a perfect cube) to be divisible by all positive integers m \le m we require it to be a multiple of L m = l c m ( 1 , 2 , . . . . , ( m 1 ) , m ) . L_{m} = lcm(1,2,....,(m-1),m).

Now L 8 = 2 3 3 5 7 = 840 > 9 3 , L_{8} = 2^{3}*3*5*7 = 840 \gt 9^{3}, so any such n n would also have to be divisible by 9. 9. Thus we will require that n < 8 3 = 512. n \lt 8^{3} = 512. Next, we have that L 7 = 2 2 3 5 7 = 420 > 7 3 = 343 , L_{7} = 2^{2}*3*5*7 = 420 \gt 7^{3} = 343, and since this is the greatest integer n n less than 8 3 8^{3} and greater than 7 3 7^{3} that is divisible by all positive integers less than n 3 \sqrt[3]{n} we can conclude that 420 \boxed{420} is the number we are seeking.

Thank you for your solution.

I don't understand why n n having to be divisible by 9 would be a problem, though. We should take a multiple of L 9 L_9 . Of course, as L 9 = 2520 > 1 3 3 L_9=2520>13^3 , we have to take a multiple of L 13 L_{13} , and so on.

I think that the question is: is L n > ( n + 1 ) 3 L_n>(n+1)^3 for all n > 7 n>7 ? It seems to be so, but how can we prove it?

Laurent Shorts - 4 years, 4 months ago

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 420 420 then it must be at least 840 840 , and so it must be must be divisible by 2520 2520 , and so must be divisible by 360360 360360 , 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 11 > 8 11 \gt 8 , and so the cubed root will increase by a factor greater than 2 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.

Brian Charlesworth - 4 years, 4 months ago

Log in to reply

It's convincing! Thank you for the quick answer :)

Laurent Shorts - 4 years, 4 months ago

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.

Buzz Breedlove - 4 years, 3 months ago

Log in to reply

I don't think that is the case. Take n = ( 3 ! ) 3 = 216 n = (3!)^{3} = 216 as an example. We would then require that 216 216 is divisible by all integers less than 3 ! = 6 3! = 6 , but 216 216 is not divisible by 5 5 . In general ( m ! ) 3 (m!)^{3} is not divisible by m ! 1 m! - 1 , at the very least.

Brian Charlesworth - 4 years, 3 months ago

how is it that 11^(1/3)~2.23, but 11 is not divisible by 2?

londov1 Lmgf - 3 years, 3 months ago

Log in to reply

We're just looking for the largest integer n n ; it doesn't matter if smaller values don't meet the condition.

Brian Charlesworth - 3 years, 3 months ago
Carsten Meyer
Sep 15, 2019

Definition: g : N N , g ( n ) : = lcm ( 1 ; ; ( 3 n ) 1 ) ) \begin{aligned} g:&&\mathbb{N}&\rightarrow\mathbb{N},&&&g(n)&:=\operatorname{lcm}\left(1;\:\ldots;\:\left\lceil\sqrt[3](n)\right\rceil-1)\right) \end{aligned}

We have to find the largest n N n\in\mathbb{N} such that n = c g ( n ) , c N n=cg(n),\quad c\in\mathbb{N} . Obviously, g ( n ) g(n) only increases after every perfect cube n = m 3 n=m^3 - lets take a look at the first few values: m 5 6 7 8 9 10 11 a m : = m 3 + 1 126 217 344 513 730 1001 1332 g ( a m ) 60 60 420 840 2520 2520 27720 \begin{array}{r | r r r r r r r r r} m & 5 & 6 & 7 & 8 & 9 & 10&11&\ldots\\[.5em] \hline a_m:=m^3 + 1& 126 & 217 & 344 & 513 & \red{730} &1001&1332\\[.5em] g(a_m) & 60 & 60 & 420 & \red{840} & 2520&2520&27720 \end{array}

It seems to be the case that g ( a m ) > a m + 1 \red{g(a_m) > a_{m+1}} for m 8 m\geq 8 . If we can prove that fact, there cannot be a solution n a 8 n\geq 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 8\cdot 2^k<p_k<8\cdot 2^{k+1},\qquad k\geq 0

These prime factors are the reason that g ( a m ) g(a_m) grows very fast for m 8 m\geq 8 g ( a 8 2 k + 1 ) g ( a 8 2 k ) = lcm ( 1 ; ; 8 2 k + 1 ) lcm ( 1 ; ; 8 2 k ) ( ) p k > 8 2 k 8 g ( a 8 2 k ) < g ( a 8 ) 8 k a 2 m + 1 a m + 1 = ( 2 m + 1 ) 3 + 1 ( m + 1 ) 3 + 1 ( 2 m + 2 ) 3 + 8 ( m + 1 ) 3 + 1 8 a 8 2 k + 1 a 9 8 k < g ( a 8 ) 8 k = g ( a 8 2 k ) , k 0 \begin{aligned} \frac{ g(a_{8\cdot 2^{k+1}}) }{ g(a_{8\cdot 2^k}) }&=\frac{ \operatorname{lcm}(1;\ldots;8\cdot 2^{k+1}) }{ \operatorname{lcm}(1;\ldots;8\cdot 2^{k}) }\underset{(*)}{\geq}p_k>8\cdot 2^k\geq 8&\Rightarrow && g(a_{8\cdot 2^k})&<g(a_8)\cdot 8^k\\[1.5em] \frac{a_{2m+1}}{a_{m+1}}&=\frac{ (2m+\green{1})^3+\orange{1} }{ (m+1)^3+\blue{1} }\leq \frac{ (2m+\green{2})^3+\orange{8} }{ (m+1)^3+1 } \leq 8&\Rightarrow&& a_{8\cdot 2^{k}+1}&\leq a_9\cdot 8^k< g(a_8)\cdot 8^k =g(a_{8\cdot 2^k}),&&k\geq 0 \end{aligned}

Both sequences are monotonically increasing, so there can not be a solutiom in any interval [ a 8 2 k ; a 8 2 k + 1 ) [a_{8\cdot 2^k};\:a_{8\cdot 2^{k+1}}) and k 0 k\geq 0 . Using the table, we find the largest solution to n = c g ( n ) < a 8 = 513 n=cg(n)<a_8=513 to be n = 420 \boxed{n=420}

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!

Bethany Waanders
Jan 8, 2021

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

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...