From: rusin@vesuvius.math.niu.edu (Dave Rusin) Subject: Re: LCM Date: 26 Dec 1999 23:55:02 GMT Newsgroups: sci.math, sci.math.symbolic Keywords: LCM of the first n integers, about exp(n) In article <1GJ84.2195$W3.52024@news.tpnet.pl>, Quba wrote: >Prove: > > LCM(1,2,3,...n) >= 2^(n-1) It's probably provably true since the expected value of the left side is more like e^n and so we expect the inequality to fail for at most a finite number of n. The term on the left has logarithm equal to Sum( log(p)* floor(log(n)/log(p)), p=prime, p <= n ) as can be seen by considering the prime factorizations of all the numbers whose LCM we seek. This is bounded above by a similar expression with the 'floor' term removed, which sums to log(n)*pi(n), and which is thus (by the prime number theorem) asymptotic to n . To get a lower bound, simply sum only over those primes greater than sqrt(n), for which the floor() expression equals 1. The sum of the logs of the primes less than n is n + o(n), so our restricted sum is also n + o(n), and certainly more than (n-1)*log(2) for sufficiently large n. I won't bother tracking down what "sufficiently large" means in this case; I got that estimate on the sum of log(p) from 95/p-sharp which in turn I took from some classic number-theory texts. dave ============================================================================== From: Nick Halloway Subject: Re: LCM Date: Sun, 26 Dec 1999 16:33:23 -0800 Newsgroups: sci.math In article <8469sm$qgm$1@gannett.math.niu.edu> rusin@vesuvius.math.niu.edu writes: >In article <1GJ84.2195$W3.52024@news.tpnet.pl>, >Quba wrote: >>Prove: >> >> LCM(1,2,3,...n) >= 2^(n-1) > >It's probably provably true since the expected value of the left side is >more like e^n and so we expect the inequality to fail for at most >a finite number of n. > >The term on the left has logarithm equal to > Sum( log(p)* floor(log(n)/log(p)), p=prime, p <= n ) This is the Chebyshev psi function and by the prime number theorem psi(x)/x --> 1 as x --> oo. So yes there can only be finitely many exceptions. If it is true it would give a good lower bound on pi(x), the # primes < x, since pi(x) = theta(x)/ln(x) + Int (2 to x) of theta(t)/(t*ln^2(t))dt theta(x) being the sum of the ln's of primes <= x. Since theta(x) is close to psi(x) you would get a good lower bound on pi(x). I thought about this a lot and didn't find out much more than this. Are there theorems on the max spacing between prime powers that are applicable? Or max spacing between primes? Before 929, a prime, 920-928 aren't prime powers, so you multiply by 1/(2^9) and log base 2 of 929 < 10. So it isn't even true that each prime power more than makes up for the 1/2 factors before it. ============================================================================== [Small typo corrected here as per followup post --djr] ============================================================================== From: Nick Halloway Subject: Re: LCM Date: Sun, 26 Dec 1999 20:44:22 -0800 (PST) Newsgroups: sci.math,alt.math.moderated Quba wrote: : Prove: : LCM(1,2,3,...n) >= 2^(n-1) Using Chebyshev's inequality 0.921 x/ln x <= pi(x) <= 1.105 x/ln x for x >= 30 and theta(x) = pi(x) ln(x) - integral (2 to x) [pi(t)/t dt] where theta(x) is the sum of the ln's of the primes <= x you get theta(x) >= 0.921x - 1.105*sqrt(x)/ln(30) - 1.105*x/ln(sqrt(x)) - 10*(ln(30)-ln(2)) so you want x big enough so theta(x)/x >= 0.921 - 1.105/[ln(30)*sqrt(x)] - 1.105/ln(sqrt(x)) - 10*(ln(30)-ln(2))/x > ln(2). x > 50,000 will do so all you have to do is check up to x=50,000. ============================================================================== From: Kurt Foster Subject: Re: LCM Date: Mon, 27 Dec 1999 23:31:32 GMT Newsgroups: sci.math In <1GJ84.2195$W3.52024@news.tpnet.pl>, Quba said: . I have an interesting problem: . Prove: . LCM(1,2,3,...n) >= 2^(n-1) Hmmm, taking natural logs, we have to prove that ln(LCM(1,2,... n)) >= (n-1)*ln(2) The left side is Psi(n), or SUM, m =< n, /\(m) where /\ (LAMBDA) is the Mangoldt function: /\(m) = ln(p) if m is a positive integer power of the prime p, and 0 otherwise. So the problem is to prove that Psi(n) >= (n-1)*ln(2) for every positive integer n. This is a non-trivial estimate; one version of the Prime Number Theorem is that LIMIT, x -> +infinity Psi(x)/x = 1. You might be able to get the required estimate using Chebyshev-type arguments.