wu :: forums « wu :: forums - No Perfect power » Welcome, Guest. Please Login or Register. Apr 10th, 2025, 2:50am

RIDDLES SITE WRITE MATH! Home Help Search Members Login Register

wu :: forums    riddles    medium (Moderators: Eigenray, william wu, ThudnBlunder, Icarus, SMQ, Grimbal, towr)    No Perfect power « Previous topic | Next topic » Pages: 1  Reply Notify of replies Send Topic Print    Author  Topic: No Perfect power  (Read 696 times) Aryabhatta Uberpuzzler     Gender: Posts: 1321 No Perfect power   « on: Jan 24th, 2006, 12:55pm » Quote Modify 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. IP Logged Eigenray wu::riddles Moderator Uberpuzzler     Gender: Posts: 1948 Re: No Perfect power   « Reply #1 on: Jan 26th, 2006, 4:39pm » Quote Modify The number of perfect powers between N and N2) is bounded above by [sum]k=2N (logkN2 - logkN) < log2N + [int]2N log N dt/log t  = log2N + log N Li(N)  ~ N. So you're putting ~N2 holes in ~N pigeons. IP Logged Aryabhatta Uberpuzzler     Gender: Posts: 1321 Re: No Perfect power   « Reply #2 on: Jan 26th, 2006, 5:58pm » Quote Modify Well done Eigenray. IP Logged wolverine Newbie     Gender: Posts: 1 Re: No Perfect power   « Reply #3 on: Jan 27th, 2006, 1:23am » Quote Modify can't we just use properties of the following sequence of numbers : n!, n!+1, n!+2, ...., n!+n-1 IP Logged towr wu::riddles Moderator Uberpuzzler Some people are average, some are just mean.     Gender: Posts: 13730 Re: No Perfect power   « Reply #4 on: Jan 27th, 2006, 1:25am » Quote Modify on Jan 26th, 2006, 4:39pm, Eigenray wrote: So you're putting ~N2 holes in ~N pigeons. Ouch, poor pigeons.. IP Logged Wikipedia, Google, Mathworld, Integer sequence DB pex Uberpuzzler     Gender: Posts: 880 Re: No Perfect power   « Reply #5 on: Jan 27th, 2006, 1:59am » Quote Modify Quote: can't we just use properties of the following sequence of numbers :   n!, n!+1, n!+2, ...., n!+n-1     I don't think so. Nothing prevents these numbers from being perfect powers: 4!+1=52, 4!+3=33, 5!+1=112, ... IP Logged Eigenray wu::riddles Moderator Uberpuzzler     Gender: Posts: 1948 Re: No Perfect power   « Reply #6 on: Jan 27th, 2006, 2:41am » Quote Modify on Jan 27th, 2006, 1:23am, wolverine wrote: can't we just use properties of the following sequence of numbers : n!, n!+1, n!+2, ...., n!+n-1 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? IP Logged Aryabhatta Uberpuzzler     Gender: Posts: 1321 Re: No Perfect power   « Reply #7 on: Jan 27th, 2006, 9:51am » Quote Modify on Jan 27th, 2006, 1:25am, towr wrote: Ouch, poor pigeons..   LOL!   Here is what I had in mind, which is slightly simpler than Eigenray's solution.     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.   IP Logged Eigenray wu::riddles Moderator Uberpuzzler     Gender: Posts: 1948 Re: No Perfect power   « Reply #8 on: Jan 27th, 2006, 3:18pm » Quote Modify on Jan 27th, 2006, 1:25am, towr wrote: Ouch, poor pigeons.. 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]. IP Logged Eigenray wu::riddles Moderator Uberpuzzler     Gender: Posts: 1948 Re: No Perfect power   « Reply #9 on: Jan 27th, 2006, 6:55pm » Quote Modify 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.) IP Logged Aryabhatta Uberpuzzler     Gender: Posts: 1321 Re: No Perfect power   « Reply #10 on: Jan 29th, 2006, 1:08pm » Quote Modify 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. IP Logged Pages: 1  Reply Notify of replies Send Topic Print Forum Jump: ----------------------------- riddles -----------------------------  - easy => medium   - hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board