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
start with 4, or can any integer serve as a seed?
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.
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.
3!!!! has about 4.54*10^1749 digits. That's still not too bad, it
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.
> 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.
> 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
> start with 4, or can any integer serve as a seed?
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.)
>"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:
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:
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.
> [...]
> 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.
>> 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
>> start with 4, or can any integer serve as a seed?
> 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.
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.
> 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.)
>>> 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
>>> start with 4, or can any integer serve as a seed?
>> 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.
> Well, no. WE also get a much larger number of possible numbers it could > hit. The step size gets very large.
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.
>> 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.)
> 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 larger prime, a contradiction.
-- I have made a thing that superficially resembles music:
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.
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.
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.
>> 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 larger > prime, a contradiction.
> -- > I have made a thing that superficially resembles music:
> 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?
>> 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!.
> >> 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, at prime works, but the reason you give below
> is inside the set of sufficient.
> >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!.
> 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.
> 3!!!! has about 4.54*10^1749 digits. That's still not too bad, it
> 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.
>>> 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!.
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.
> On 2012-09-08, quasi <qu...@null.set> wrote:
>> 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!.
> 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!.
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:
> On 2012-09-08, quasi <qu...@null.set> wrote:
>> 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!.
> 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!.
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.
