Karin Posted January 28, 2010 Share Posted January 28, 2010 Does anyone have any good tips on how to think about when I want to show that Pn <2 ^ 2 ^ n and Pn denotes the nth prime number and n = 1,2,3, .. ? Link to comment Share on other sites More sharing options...
Mr Skeptic Posted January 28, 2010 Share Posted January 28, 2010 Well, the prime numbers seem to grow at n*ln(n), a much slower rate of growth than the exponential one (Is that 2^(2^n)?). It may help you to know that if you multiply all the prime numbers up to a point and add one, you get a number that is not divisible by any of those prime numbers. Link to comment Share on other sites More sharing options...
khaled Posted April 22, 2010 Share Posted April 22, 2010 f(n) = 2^(2^n), P(n) = n*log(n) f(0) = 1,.. P(0) = 0 ..(initial condition TRUE) f(1) = 4,... P(1) = 0 f(2) = 16,... P(2) = 1.4 f(3) = 256,.... P(3) = 3.3 ... f(10) = 309.8, P(10) = 23 P(n) is less than f(n) for n <= k, now let's prove it for n = k+1 f(k+1) = 2^(2^k+1) = 2^(2^k) * 2^(2^1) = f(k) * 2^2 P(k+1) = (k+1) * log(k+1) = k * log(k+1) + log(k+1) .. = k * log(k+1) + log(k+1) ..(i'll consider log(k+1) = log(k) + epsilon) ... = k * log(k) + epsilon + log(k+1) .... = P(k) + (epsilon + log(k+1)) growth rate of f(k) = f(k) * 2^2 / f(k) * 100 % = 400% growth rate of P(k) = P(k) + epi + log(k+1) / P(k) * 100% .. = P(k)/P(k) + epi/P(k) + log(k+1)/P(k) * 100% ... = 1 + 0 (canceled) + log(k+1)/k * log(k) .... = log(k) + epi /k * log(k) = log(k)/k * log(k) + epi/P(k) * 100% ..... = 1/k + 0 * 100% ...... = 1/k * 100% = 100 k^-1 % since, f(K) > P(K) and, growth rate of f(k) >> 100% > growth rate of P(k) then f(K+1) > P(K+1) is TRUE also, Link to comment Share on other sites More sharing options...
Recommended Posts
Create an account or sign in to comment
You need to be a member in order to leave a comment
Create an account
Sign up for a new account in our community. It's easy!
Register a new accountSign in
Already have an account? Sign in here.
Sign In Now