mersenneforum.org Divisible up to Square Root
 Register FAQ Search Today's Posts Mark Forums Read

 2007-09-04, 18:43 #1 davar55     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 robert44444uk     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 Jens K Andersen     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 Mr. P-1     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 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post chris2be8 Msieve 13 2020-10-14 07:08 davar55 Lounge 0 2016-03-16 20:19 paul0 Factoring 10 2015-01-19 12:25 bsquared Msieve 17 2010-04-09 14:11 Damian Math 3 2010-01-01 01:56

All times are UTC. The time now is 10:14.

Thu May 6 10:14:19 UTC 2021 up 28 days, 4:55, 0 users, load averages: 2.11, 2.28, 1.92