|
||
|
Title: No Perfect power Post by Aryabhatta on Jan 24th, 2006, 12:55pm Prove/Disprove: Given any postive integer n, there exist n consecutive integers none of which is a perfect power. A Perfect power = any integer of the form st where s is a positive integer and t is a positive integer > 1. |
||
|
Title: Re: No Perfect power Post by Eigenray on Jan 26th, 2006, 4:39pm The number of perfect powers between N and N2) is bounded above by [hide] [sum]k=2N (logkN2 - logkN) < log2N + [int]2N log N dt/log t = log2N + log N Li(N) ~ N.[/hide] So you're putting ~N2 holes in ~N pigeons. |
||
|
Title: Re: No Perfect power Post by Aryabhatta on Jan 26th, 2006, 5:58pm Well done Eigenray. |
||
|
Title: Re: No Perfect power Post by wolverine on Jan 27th, 2006, 1:23am can't we just use properties of the following sequence of numbers : [hide]n!, n!+1, n!+2, ...., n!+n-1[/hide] |
||
|
Title: Re: No Perfect power Post by towr on Jan 27th, 2006, 1:25am on 01/26/06 at 16:39:23, Eigenray wrote:
|
||
|
Title: Re: No Perfect power Post by pex on Jan 27th, 2006, 1:59am Quote:
I don't think so. Nothing prevents these numbers from being perfect powers: 4!+1=52, 4!+3=33, 5!+1=112, ... |
||
|
Title: Re: No Perfect power Post by Eigenray on Jan 27th, 2006, 2:41am on 01/27/06 at 01:23:58, wolverine wrote:
But 3!+2, 4!+1, 4!+3, 5!+1, 7!+1 are powers (but the only ones with n<40). Perhaps you're thinking of the fact that n!+2, n!+3, . . ., n!+n are all composite? |
||
|
Title: Re: No Perfect power Post by Aryabhatta on Jan 27th, 2006, 9:51am on 01/27/06 at 01:25:29, towr wrote:
LOL! Here is what I had in mind, which is slightly simpler than Eigenray's solution. [hide] Let P = {Set of perfect powers}. Given an n, suppose at least one among every n consecutive integers is a perfect power. The we must have that the density of P is at least 1/n. We can easily show that the density of P is zero. Let P(M) be | P \intersection {1,2,...,M}| Now if st <= M, then we clearly have that s <= sqrt(M) and t <= log M (log is base 2) Thus P(M) <= sqrt(M) *log M. Thus P(M)/M -> 0 as M -> oo. [/hide] |
||
|
Title: Re: No Perfect power Post by Eigenray on Jan 27th, 2006, 3:18pm on 01/27/06 at 01:25:29, towr wrote:
It might not be as bad as all that. I erred -- I can only guarantee some pigeon gets ~N/log N holes. There may be more than x-y integers in the interval [x,y], of course. So the upper bound becomes log2N + log N (Li(N)+N) ~ N log N. So this isn't any better than the simpler estimate after all. I was going to write a lower bound of [int]2N/e [log N/log t - 1] dt = N/e [ log N /(log N-1) - 1] + log N N/e/(log N-1)2 + O(N/log N2) ~ 2/e N/log N, but this does not consider overcounting -- only summing over k not itself a power. But that's probably negligible, and the number of integers in [logkN, logkN2] probably spends just as much time near logkN - 1 as it does logkN + 1, so heuristically, I'd still expect ~N powers in [N,N2]. |
||
|
Title: Re: No Perfect power Post by Eigenray on Jan 27th, 2006, 6:55pm I don't know why I was making things so complicated. Seemed like a good idea at the time, I guess. The number of perfect powers in [1, N2] is precisely asymptotic to N. The lower bound is obvious. Two methods for the upper bound: 1) Count powers kr with 2<k<N, 2<r<logkN2. This is bounded above by [sum]k=2N (logkN2 - 1) < 2log N Li(N) - N + o(N) = N + o(N). 2) Count powers kr with 2<r<log2N2, 1<k<N2/r. This is bounded above by N2/2 + N2/3 + N2/4 + ... = N + O(N2/3log N). (Reminds me of von Mangoldt.) |
||
|
Title: Re: No Perfect power Post by Aryabhatta on Jan 29th, 2006, 1:08pm Indeed, Eigenray. The number of perfect powers less than N is asymptotic to sqrt(N). Look at the following: Problem 72, "A Problem Seminar" by Donald J Newman. |
||
|
Powered by YaBB 1 Gold - SP 1.4! Forum software copyright © 2000-2004 Yet another Bulletin Board |