2007-09-04, 18:43 | #1 |
May 2004
New York City
3×17×83 Posts |
Divisible up to Square Root
Find all positive integers n that are
divisible by all positive integers k < sqrt(n) (and show that those are all of them). |
2007-09-05, 13:59 | #2 |
Jun 2003
Oxford, UK
1,933 Posts |
Maybe I misunderstood the question, but the list of such integers must be factorials by definition, otherwise there is no guarantee to catch every integer < sqrt(n)
n=24 i.e. 4! can be factored as 1*2*3*4, and floor(sqrt(24))=4, so this qualifies 2!,3! have prime factors 2,3 which are > floor(sqrt(2,3))= 1,2 so if I read the question rightly I am not sure these qualify. 5! and above have holes: floor(sqrt(5!))=10, and 7,9 not factors of 5! floor(sqrt(6!))=26, and 7,11,13,14,17,19,21,22,23 are not factors of 6! As the floor function increases at a fast rate the non factors will increase quickly and will never be zero (needs a proof) So I would bet n=24 is a unique solution, according to this approach. But 24 has factors 6,8,12,24 which are > sqrt, so maybe I am not understanding the question, at least the bit in brackets |
2007-09-05, 14:44 | #3 |
Feb 2006
Denmark
2·5·23 Posts |
You are reading it wrongly.
"Find all positive integers n that are divisible by all positive integers k < sqrt(n)" n must be divisible by each number <= sqrt(n), but not necessarily by their product. And n is allowed to have prime factors above sqrt(n). I get 8 solutions. |
2007-09-05, 15:59 | #4 |
Jun 2003
7·167 Posts |
The solutions are 1, 2, 3, 4, 6, 8, 12, and 24. No solutions above 24 exist.
Proof: We first show that no solution >49 exists. Suppose the contrary. Suppose s>49 is a solution. Let n be the greatest integer less than sqrt(s), then n >=7 and s is divisible by all positive integers <=n. In particular s is divisible by n, n-1 and n-2, hence by lcm(n, n-1,n-2) However these three numbers are pairwise co-prime except possibly n and n-2 which at worst can have a common factor of 2. Therefore lcm(n, n-1, n-2) >= n(n-1)(n-2)/2 = (n^3 - 3n^2 +2n)/2 >= (7n^2 - 3n^2 + 2n)/2 (because n>=7) = (4n^2 + 2n)/2 = n(2n+1) = n(n+1) +n^2 > n(n+1) + (n+1) = (n+1)(n+1) = (n+1)^2 Since s is divisible by lcm(n,n-1,n-2) it cannot be less than this, hence s>(n+1)^2 but then n+1<sqrt(s) which is a contradiction. To complete the proof, note that if s is a solution > 24 then s must be divisible by 3, 4, and 5 hence divisible by (hence not less than) lcm(3, 4, 5) = 60, which is impossible by the above. Last fiddled with by Mr. P-1 on 2007-09-05 at 16:17 Reason: Fixed minor algebraic slip-up. |
Thread Tools | |
Similar Threads | ||||
Thread | Thread Starter | Forum | Replies | Last Post |
All square roots failed | chris2be8 | Msieve | 13 | 2020-10-14 07:08 |
Square Root Days | davar55 | Lounge | 0 | 2016-03-16 20:19 |
NFS Square root problems | paul0 | Factoring | 10 | 2015-01-19 12:25 |
square root crash | bsquared | Msieve | 17 | 2010-04-09 14:11 |
Square root of 3 | Damian | Math | 3 | 2010-01-01 01:56 |