The old Google Groups will be going away soon, but your browser is incompatible with the new version.
a number theory problem
 There are currently too many topics in this group that display first. To make this topic appear first, remove this option from another topic. There was an error processing your request. Please try again. Standard view   View as tree
 Messages 1 - 25 of 30 Newer >

From:
To:
Cc:
Followup To:
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.

More options Sep 5 2012, 10:43 pm
Newsgroups: sci.math, alt.math.recreational, sci.crypt
From: RichD <r_delaney2...@yahoo.com>
Date: Wed, 5 Sep 2012 19:43:27 -0700 (PDT)
Local: Wed, Sep 5 2012 10:43 pm
Subject: a number theory problem
Maybe this one is known, but not to me -

Consider 3 functions:
1)  repeated factorial
2)  repeated square root
3)  floor

(1)  means factorial applied repeatedly;
e.g 3!!! = ((3!)!)! = 720!

Similarly, (2) means square root of an argument,
applied repeatedly;
i.e.  for some m  ==>  m^(1/2^n), for some n

(3) is the integer part of any non-integer real

Now consider generating a positive integer k
via (3), then (2), then (1):  k = floor[(4!!...)^(1/2^n)]

In words, apply (1) to 4, followed by (2), then (3).

Finally, the problem:  is it possible to generate every
integer via this formula?  Does it matter that we

--
Rich

To post a message you must first join this group.
You do not have the permission required to post.
More options Sep 5 2012, 10:46 pm
Newsgroups: sci.math, alt.math.recreational, sci.crypt
From: RichD <r_delaney2...@yahoo.com>
Date: Wed, 5 Sep 2012 19:46:47 -0700 (PDT)
Local: Wed, Sep 5 2012 10:46 pm
Subject: Re: a number theory problem
On Sep 5, RichD <r_delaney2...@yahoo.com> wrote:

> 1)  repeated factorial
> 2)  repeated square root
> 3)  floor

> ....
> Now consider generating a positive integer k
> via (3), then (2), then (1):  k = floor[(4!!...)^(1/2^n)]

oops
Make that "... via (1), then (2), then (3):"

--
Rich

To post a message you must first join this group.
You do not have the permission required to post.
More options Sep 6 2012, 12:09 am
Newsgroups: sci.math, alt.math.recreational, sci.crypt
From: Tim Little <t...@little-possums.net>
Date: 06 Sep 2012 04:09:56 GMT
Local: Thurs, Sep 6 2012 12:09 am
Subject: Re: a number theory problem
On 2012-09-06, RichD <r_delaney2...@yahoo.com> wrote:

> Consider 3 functions:
> 1)  repeated factorial
> 2)  repeated square root
> 3)  floor
...
> Finally, the problem: is it possible to generate every integer via
> this formula?  Does it matter that we start with 4, or can any
> integer serve as a seed?

It does seem likely that every integer can be generated this way, and
I doubt it depends upon which integer you start with (greater than 2).
I'd be surprised if there was a known proof or disproof though.

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

--
Tim

To post a message you must first join this group.
You do not have the permission required to post.
More options Sep 6 2012, 12:59 am
Newsgroups: sci.math, alt.math.recreational, sci.crypt
From: Tim Little <t...@little-possums.net>
Date: 06 Sep 2012 04:59:26 GMT
Local: Thurs, Sep 6 2012 12:59 am
Subject: Re: a number theory problem
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.

requires only about 5813 square roots to get down to a single-digit
number (which is just 3 again).

The next iterate, 3!!!!! has more digits than I can conveniently
express and requires more than 10^1750 square roots to get down to any
writable integer.  Perhaps someone might be cleverly able to tell
whether it hits 4 or not in its sequence of square roots, but I
certainly can't.

It only gets worse from there.

--
Tim

To post a message you must first join this group.
You do not have the permission required to post.
More options Sep 6 2012, 12:13 pm
Newsgroups: sci.math, alt.math.recreational, sci.crypt
From: "Scott Fluhrer" <sfluh...@ix.netcom.com>
Date: Thu, 6 Sep 2012 12:12:03 -0400
Local: Thurs, Sep 6 2012 12:12 pm
Subject: Re: a number theory problem

"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

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.

To post a message you must first join this group.
You do not have the permission required to post.
More options Sep 6 2012, 2:01 pm
Newsgroups: sci.math, alt.math.recreational, sci.crypt
From: "dilettante" <n...@nonono.no>
Date: Thu, 6 Sep 2012 13:01:22 -0500
Local: Thurs, Sep 6 2012 2:01 pm
Subject: Re: a number theory problem

"RichD" <r_delaney2...@yahoo.com> wrote in message

It would seem to be true that any seed greater than 2 would generate all
integers from a kind of probability argument: for each iteration of the
factorial, we generate a sequence (via the square root) descending to one.
So we get to take an infinite number of shots at hitting any particular
integer. Surely we can't be so unlucky as to miss every time, unless there
is some mysterious relationship between factorials and squares that is not
apparent! (Of course I am not making even the pretense of a rigorous
argument of any kind.)

To post a message you must first join this group.
You do not have the permission required to post.
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"

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.

To post a message you must first join this group.
You do not have the permission required to post.
More options Sep 6 2012, 10:05 pm
Newsgroups: sci.math, alt.math.recreational, sci.crypt
From: Tim Little <t...@little-possums.net>
Date: 07 Sep 2012 02:05:28 GMT
Local: Thurs, Sep 6 2012 10:05 pm
Subject: Re: a number theory problem
On 2012-09-06, Scott Fluhrer <sfluh...@ix.netcom.com> wrote:

> 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

The problem required the steps to be done in order.  All the
factorials, then all the square roots, then the floor.

--
Tim

To post a message you must first join this group.
You do not have the permission required to post.
More options Sep 6 2012, 10:27 pm
Newsgroups: sci.math, alt.math.recreational, sci.crypt
From: Tim Little <t...@little-possums.net>
Date: 07 Sep 2012 02:27:52 GMT
Local: Thurs, Sep 6 2012 10:27 pm
Subject: Re: a number theory problem
On 2012-09-06, Robert Wessel <robertwess...@yahoo.com> wrote:

> 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

Let's use notation F(n) for F(0) = 3, F(n+1) = F(n)!.  Then after
taking m square roots, we get S(n,m) = F(n)^(2^-m).

For any integer k > 1 and for all n such that F(n) > k, there exists m
such that S(n,m) is in [k,k^2).  I.e. every sufficiently large value
of n gives a "sample" in that interval, and any of those samples
landing in [k,k+1) means k is reachable.

I would expect that for every k, there would be infinitely many
repetitions of the factorial that result in k, with an average density
greater than 1/k^2.

--
Tim

To post a message you must first join this group.
You do not have the permission required to post.
More options Sep 7 2012, 4:34 am
Newsgroups: sci.math, alt.math.recreational, sci.crypt
From: Noob <r...@127.0.0.1>
Date: Fri, 07 Sep 2012 10:34:17 +0200
Local: Fri, Sep 7 2012 4:34 am
Subject: Re: a number theory problem

RichD wrote:
> Consider 3 functions:
> 1)  repeated factorial
> 2)  repeated square root
> 3)  floor

> [...]
> Finally, the problem:  is it possible to generate every
> integer via this formula?  Does it matter that we
> start with 4, or can any integer serve as a seed?

A somewhat related exercice is proving the Collatz conjecture.

To post a message you must first join this group.
You do not have the permission required to post.
More options Sep 7 2012, 12:18 pm
Newsgroups: sci.math, alt.math.recreational, sci.crypt
From: unruh <un...@invalid.ca>
Date: Fri, 07 Sep 2012 16:18:33 GMT
Local: Fri, Sep 7 2012 12:18 pm
Subject: Re: a number theory problem
On 2012-09-06, dilettante <n...@nonono.no> wrote:

Well, no. WE also get a much larger number  of possible numbers it could hit.  The step size gets very large.

> So we get to take an infinite number of shots at hitting any particular

An infinite number of shots but with each value of "q" (3!!!!...! q
times) the range gets much much larger and the step sizes get larger.

To post a message you must first join this group.
You do not have the permission required to post.
More options Sep 7 2012, 12:45 pm
Newsgroups: sci.math, alt.math.recreational, sci.crypt
From: "dilettante" <n...@nonono.no>
Date: Fri, 7 Sep 2012 11:44:51 -0500
Local: Fri, Sep 7 2012 12:44 pm
Subject: Re: a number theory problem

"unruh" <un...@invalid.ca> wrote in message

The step size in the vicinity of the number we are "trying to hit" doesn't
really change much. Say we are trying to hit 79. If we start from 4!!!! we
get one sequence of numbers descending to one. If we start from 4!!!!!!! we
get another sequence descending to one. In both cases, we are bound to hit
some number between n and n^2 for every n. So we hit some number between 9
and 81 every time. That gives us a very good chance of hitting 79, or at
least it seems so at first blush. Of course, for larger numbers the odds get
steeper for one shot, but we get infintely many shots.I still like our
chances.

>> So we get to take an infinite number of shots at hitting any particular

> An infinite number of shots but with each value of "q" (3!!!!...! q
> times) the range gets much much larger and the step sizes get larger.

As I noted above, the step size in the vicinity of any particular integer
doesn't change much. We are always taking square roots, so we always hit
something between n and n^2.

To post a message you must first join this group.
You do not have the permission required to post.
More options Sep 7 2012, 4:00 pm
Newsgroups: sci.math, alt.math.recreational, sci.crypt
From: "dilettante" <n...@nonono.no>
Date: Fri, 7 Sep 2012 15:00:09 -0500
Local: Fri, Sep 7 2012 4:00 pm
Subject: Re: a number theory problem

On a tangentially related note, who can give the shortest proof of the
following fact: there do not exist integers k and n > 1 such that n! = k ^2.

To post a message you must first join this group.
You do not have the permission required to post.
More options Sep 7 2012, 4:36 pm
Newsgroups: sci.math, alt.math.recreational, sci.crypt
From: Rotwang <sg...@hotmail.co.uk>
Date: Fri, 07 Sep 2012 21:36:53 +0100
Local: Fri, Sep 7 2012 4:36 pm
Subject: Re: a number theory problem
On 07/09/2012 21:00, dilettante wrote:

> On a tangentially related note, who can give the shortest proof of the
> following fact: there do not exist integers k and n > 1 such that n! = k
> ^2.

I don't know about shortest, but it occurs to me that that follows quite
quickly from Bertrand's postulate (there's always a prime p such that m
< p < 2m, whenever m >= 2): suppose such n and k exist. Let p be a prime
that divides k, so that p^2 divides n!. Then n >= 2*p, since otherwise
there aren't enough factors of p among the product of natural numbers <=
n. But then there's a prime q such that p < q <= n, so q divides n! =
k^2 and therefore q divides n. So if any prime divides k then so does a

--
I have made a thing that superficially resembles music:

To post a message you must first join this group.
You do not have the permission required to post.
More options Sep 7 2012, 4:38 pm
Newsgroups: sci.math, alt.math.recreational, sci.crypt
From: quasi <qu...@null.set>
Date: Fri, 07 Sep 2012 16:40:04 -0500
Local: Fri, Sep 7 2012 5:40 pm
Subject: Re: a number theory problem

dilettante wrote:
>On a tangentially related note, who can give the shortest
>proof of the following fact: there do not exist integers
>k and n > 1 such that n! = k^2.

There is a prime p such that n/2 < p <= n.

quasi

To post a message you must first join this group.
You do not have the permission required to post.
More options Sep 7 2012, 4:59 pm
Newsgroups: sci.math, alt.math.recreational, sci.crypt
From: RichD <r_delaney2...@yahoo.com>
Date: Fri, 7 Sep 2012 13:59:22 -0700 (PDT)
Local: Fri, Sep 7 2012 4:59 pm
Subject: Re: a number theory problem
On Sep 6, "Scott Fluhrer" <sfluh...@ix.netcom.com> wrote:

> >> It does seem likely that every integer can be
> >> generated this way,

"likely" is slippery - I'd say meaningless -
in the context of infinity -

> >>The number of square roots required would become
> >>insanely large very quickly.
> 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)

Succinctly put.

> Given how comparitively rare factorials are and how
> narrow these ranges are for large x,

I call them the ranges and the gaps.
To generate the desired integer x, n!!!...
has to fall into one of the ranges.

Intuition will not answer the question.

> it is not at
> all obvious to me whether they would be a solution
> for every integer x.

um, and you said what, above?

--
Rich

To post a message you must first join this group.
You do not have the permission required to post.
More options Sep 7 2012, 5:01 pm
Newsgroups: sci.math, alt.math.recreational, sci.crypt
From: RichD <r_delaney2...@yahoo.com>
Date: Fri, 7 Sep 2012 14:01:28 -0700 (PDT)
Local: Fri, Sep 7 2012 5:01 pm
Subject: Re: a number theory problem
On Sep 6, Tim Little <t...@little-possums.net> wrote:

> > 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

> The problem required the steps to be done in order.
> All the factorials, then all the square roots, then the floor.

Correct.

--
Rich

To post a message you must first join this group.
You do not have the permission required to post.
More options Sep 7 2012, 5:50 pm
Newsgroups: sci.math, alt.math.recreational, sci.crypt
From: "dilettante" <n...@nonono.no>
Date: Fri, 7 Sep 2012 16:50:07 -0500
Local: Fri, Sep 7 2012 5:50 pm
Subject: Re: a number theory problem
This is in fact the proof I had in mind when I posed the problem. Quasi
also cites Bertrand's Postulate (I didn't know it was called that, but
recalled that Erdos had given a proof (not the first I think)), and doesn't
elaborate, but surely has the same argument in mind.

"Rotwang" <sg...@hotmail.co.uk> wrote in message

news:k2dlt9\$j6g\$1@dont-email.me...

To post a message you must first join this group.
You do not have the permission required to post.
More options Sep 8 2012, 2:04 pm
Newsgroups: sci.math, alt.math.recreational, sci.crypt
From: unruh <un...@invalid.ca>
Date: Sat, 08 Sep 2012 18:04:08 GMT
Local: Sat, Sep 8 2012 2:04 pm
Subject: Re: a number theory problem
On 2012-09-07, dilettante <n...@nonono.no> wrote:

> On a tangentially related note, who can give the shortest proof of the
> following fact: there do not exist integers k and n > 1 such that n! = k ^2.

Consider p, the largest prime less than n. p^2 is greater than n but p
must divide k.
Of course by "shortest proof" you need to specify what you mean by
"proof". Must the proof be in terms of the Peano axioms?
Or what established literature can be used?

To post a message you must first join this group.
You do not have the permission required to post.
More options Sep 8 2012, 2:41 pm
Newsgroups: sci.math, alt.math.recreational, sci.crypt
From: quasi <qu...@null.set>
Date: Sat, 08 Sep 2012 14:43:10 -0500
Local: Sat, Sep 8 2012 3:43 pm
Subject: Re: a number theory problem

unruh wrote:
>dilettante wrote:

>> On a tangentially related note, who can give the shortest
>> proof of the following fact: there do not exist integers
>> k and n > 1 such that n! = k^2.

>Consider p, the largest prime less than n.

Yes, that prime works, but the reason you give below
is insufficient.

>p^2 is greater than n but p must divide k.

The inequality p^2 > n doesn't imply p^2 doesn't divide n!.
The inequality you need is 2p > n, since if 2p <= n, then
p^2 _does_ divide n!.

quasi

To post a message you must first join this group.
You do not have the permission required to post.
 Discussion subject changed to "a number theory solution" by Martin Michael Musatov
More options Sep 8 2012, 2:51 pm
Newsgroups: sci.math, alt.math.recreational, sci.crypt
From: Martin Michael Musatov <musatovatattdot...@gmail.com>
Date: Sat, 8 Sep 2012 11:51:44 -0700 (PDT)
Local: Sat, Sep 8 2012 2:51 pm
Subject: Re: a number theory solution
On Sep 8, 11:41 am, quasi <qu...@null.set> wrote:

Musatov, the original P = NP prover.

To post a message you must first join this group.
You do not have the permission required to post.
 Discussion subject changed to "a number theory problem" by Martin Michael Musatov
More options Sep 8 2012, 2:53 pm
Newsgroups: sci.math, alt.math.recreational, sci.crypt
From: Martin Michael Musatov <musatovatattdot...@gmail.com>
Date: Sat, 8 Sep 2012 11:53:57 -0700 (PDT)
Local: Sat, Sep 8 2012 2:53 pm
Subject: Re: a number theory problem
On Sep 5, 9:59 pm, Tim Little <t...@little-possums.net> wrote:

Sometimes it does before it gets better. Musatov

To post a message you must first join this group.
You do not have the permission required to post.
More options Sep 9 2012, 11:17 am
Newsgroups: sci.math, alt.math.recreational, sci.crypt
From: unruh <un...@invalid.ca>
Date: Sun, 09 Sep 2012 15:17:47 GMT
Local: Sun, Sep 9 2012 11:17 am
Subject: Re: a number theory problem
On 2012-09-08, quasi <qu...@null.set> wrote:

Uh, no. p is the largest prime less than or equal to n.
p^2>2p so between p and p^2 there must exist at least one other prime.
If p^2 were less then n, then that prime would be less than n,
contradicting the assumption that p is the largest prime less than or
equal to n. Thus p^2>n and cannot divide n!.

As I said, it depends on what you mean by a proof. What prior work is
allowed, and do I have to go back to the Peano axioms to prove the
statements. Clearly for you I had to go back further and spell out the
steps in more detail.

To post a message you must first join this group.
You do not have the permission required to post.
More options Sep 9 2012, 11:24 am
Newsgroups: sci.math, alt.math.recreational, sci.crypt
From: Rotwang <sg...@hotmail.co.uk>
Date: Sun, 09 Sep 2012 16:24:41 +0100
Local: Sun, Sep 9 2012 11:24 am
Subject: Re: a number theory problem
On 09/09/2012 16:17, unruh wrote:

quasi's point was that the fact that p^2 > n does not, by itself, imply
that p^2 does not divide n!. For example, 3^2 divides 6!.

--
I have made a thing that superficially resembles music:

To post a message you must first join this group.
You do not have the permission required to post.
More options Sep 9 2012, 11:45 am
Newsgroups: sci.math, alt.math.recreational, sci.crypt
From: "dilettante" <n...@nonono.no>
Date: Sun, 9 Sep 2012 10:45:05 -0500
Local: Sun, Sep 9 2012 11:45 am
Subject: Re: a number theory problem

"unruh" <un...@invalid.ca> wrote in message

Quasi is right. p^2 > n does not imply that p^2 doesn't divide n!. For
example, 3^2 > 6, but 3^2 divides 6!, and for any prime p > 2, we have p^2 >
2p, but p^2 divides (2p)!

> As I said, it depends on what you mean by a proof. What prior work is
> allowed, and do I have to go back to the Peano axioms to prove the
> statements.

Of course "shortest" does depend in a big way on what prior results are
allowed. One reason I posted the question was that I thought of the
Bertrand's postulate proof as soon as I thought of the problem, but wondered
if the result was obvious from some other elementary considerations.  The
Bertrand's postulate proof generalizes immediatley to higher exponents,
which is nice.