Go Back > Fun Stuff > Puzzles

Thread Tools
Old 2007-09-04, 18:43   #1
davar55's Avatar
May 2004
New York City

3×17×83 Posts
Default 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).
davar55 is offline   Reply With Quote
Old 2007-09-05, 13:59   #2
robert44444uk's Avatar
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
robert44444uk is offline   Reply With Quote
Old 2007-09-05, 14:44   #3
Jens K Andersen
Jens K Andersen's Avatar
Feb 2006

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.
Jens K Andersen is offline   Reply With Quote
Old 2007-09-05, 15:59   #4
Mr. P-1
Mr. P-1's Avatar
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.
Mr. P-1 is offline   Reply With Quote

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

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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.