Account Options

  1. Sign in
The old Google Groups will be going away soon, but your browser is incompatible with the new version.
Google Groups Home
« Groups Home
Message from discussion a number theory problem
The group you are posting to is a Usenet group. Messages posted to this group will make your email address visible to anyone on the Internet.
Your reply message has not been sent.
Your post was successful
 
From:
To:
Cc:
Followup To:
Add Cc | Add Followup-to | Edit Subject
Subject:
Validation:
For verification purposes please type the characters you see in the picture below or the numbers you hear by clicking the accessibility icon. Listen and type the numbers you hear
 
Robert Wessel  
View profile  
 More options Sep 6 2012, 2:21 pm
Newsgroups: sci.math, alt.math.recreational, sci.crypt
From: Robert Wessel <robertwess...@yahoo.com>
Date: Thu, 06 Sep 2012 13:20:59 -0500
Local: Thurs, Sep 6 2012 2:20 pm
Subject: Re: a number theory problem
On Thu, 6 Sep 2012 12:12:03 -0400, "Scott Fluhrer"

<sfluh...@ix.netcom.com> wrote:

>"Tim Little" <t...@little-possums.net> wrote in message
>news:slrnk4gbdd.bvc.tim@soprano.little-possums.net...
>> On 2012-09-06, Tim Little <t...@little-possums.net> wrote:
>>> It does seem likely that every integer can be generated this way,

>> All the positive ones, anyway.

>>> The number of square roots required would become insanely large very
>>> quickly.

>> Just to follow up on this, 3! = 6 (which also yields 2 and 1 with
>> square roots).  3!! = 720, reducing to 5 in two square root.  3!!! has
>> 1747 digits and reduces down to 7 in 12 square roots.  The smallest
>> unreached number at this point is 4.

>Actually, you can reach 4 with a few more steps:

>- Start at 7 (which you've reach above); and compute floor( sqrt( sqrt(
>7! )) -- that's 8
>- Now, take the 8, and compute floor( sqrt( sqrt( 8! )) -- that's 14
>- Now, take the 14, and compute floor( sqrt( sqrt( sqrt( sqrt( 14! ))))) --  
>that's 4

My reading of the OP's requirements doesn't allow that kind of cycle -
he seem to specify one repeated factorial operation, one repeated
square root operation, and one floor operation.

>On the other hand, if every integer x is reachable, that would imply that,
>for every integer x, there are integers n and e s.t.

>x^(2^e) <= n! < (x+1)^(2^e)

>Given how comparitively rare factorials are and how narrow these ranges are
>for large x, it is not at all obvious to me whether they would be a solution
>for every integer x.

As you point out, the repeated factorials are clearly irrelevant.  3!!
is exactly the same as 6! and 3!!! is exatly the same as 720!.  And
your range is correct as well.  But there are an infinity of n's for
which you might find an appropriate e, and I hate the bet against
infinite sets unless there's a clear pattern (IOW, you're not going to
find an odd number in the infinite set of even numbers).

If we substitute 2^(n*lg(n)-n/ln(2)+lg(n)/2) for n! (approximately
Sterling's approximation), we can reduce(?) that to needing to find an
e, n and x where:

2^e <= (n*lg(n) - n/ln(2) + lg(n)/2)/lg(x) < (2^e)/(log(x,(x+1))

But I'm not sure that actually helps...

It does make the step sizes of the second term rather smaller than the
step sizes for the first term, but the difference first and third
terms remains relatively small because log(x,(x+1)) approaches unity
from below, OTOH very large e's will compensate for that.  So I think
we can make the difference between the first and third terms
arbitrarily large, while the second term's step size grows slowly. Can
we prove that:

((n+1)*lg(n+1)) - (n*lg(n)) < ((2^e)/(log(x,(x+1)) - 2^e)

when:

 n*lg(n) ~= 2^e

?

I don't think we can because that reduces to:

(n+1)*lg(n+1) < ((n*lg(n))/(log(x,(x+1)))

That implies that the step size of the middle term grows more than the
difference between the first and third terms.

Still, there are an infinity of n's and x's, and that's giving me
FLT-like nightmares�

And of course Sterling's approximation is not quite n!, but it is
close, and a bit more tractable.


 
You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.