mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Puzzles (https://www.mersenneforum.org/forumdisplay.php?f=18)
-   -   Divisible up to Square Root (https://www.mersenneforum.org/showthread.php?t=9192)

davar55 2007-09-04 18:43

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).

robert44444uk 2007-09-05 13:59

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

Jens K Andersen 2007-09-05 14:44

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.

Mr. P-1 2007-09-05 15:59

[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.