![]() |
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). |
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 |
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. |
[SPOILER]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.[/SPOILER] |
| All times are UTC. The time now is 20:20. |
Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.