a number theory problem

[RichD]

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
start with 4, or can any integer serve as a seed?



--
Rich

[RichD]

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

[Tim Little]

On 2012-09-06, RichD <r_dela...@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

[Tim Little]

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.

It only gets worse from there.


--
Tim

[Scott Fluhrer]

"Tim Little" <t...@little-possums.net> wrote in message
news:slrnk4gbd...@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.

[dilettante]

"RichD" <r_dela...@yahoo.com> wrote in message
news:ade88422-29fc-457f...@k3g2000pbr.googlegroups.com...

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

>
>
>
> --
> Rich

[Robert Wessel]

On Thu, 6 Sep 2012 12:12:03 -0400, "Scott Fluhrer"
<sflu...@ix.netcom.com> wrote:

>
>"Tim Little" <t...@little-possums.net> wrote in message
>news:slrnk4gbd...@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.

[Tim Little]

On 2012-09-06, Scott Fluhrer <sflu...@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

[Tim Little]

On 2012-09-06, Robert Wessel <robert...@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

[Noob]

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.

https://en.wikipedia.org/wiki/Collatz_conjecture

[unruh]

On 2012-09-06, dilettante <n...@nonono.no> wrote:
>
> "RichD" <r_dela...@yahoo.com> wrote in message
> news:ade88422-29fc-457f...@k3g2000pbr.googlegroups.com...
>> 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
>> 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.

[dilettante]

"unruh" <un...@invalid.ca> wrote in message
news:t7p2s.61$Ht7...@newsfe10.iad...

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.

[dilettante]

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.

[Rotwang]

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:

http://soundcloud.com/eroneity/we-berated-our-own-crapiness

[quasi]

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

quasi

[RichD]

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

[RichD]

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

[dilettante]

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

[unruh]

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?

[quasi]

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

[Martin Michael Musatov]

On Sep 8, 11:41 am, 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, 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!.
>
> quasi

Musatov, the original P = NP prover.

[Martin Michael Musatov]

Sometimes it does before it gets better. Musatov

[unruh]

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.


>
> quasi

[Rotwang]

On 09/09/2012 16:17, unruh wrote:
> 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!.

[dilettante]

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

news:vq23s.9$1h...@newsfe01.iad...

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

[RichD]

On Sep 7, unruh <un...@invalid.ca> wrote:
> >> Consider 3 functions:
> >> 1)  repeated factorial
> >> 2)  repeated square root
> >> 3)  floor
>

> >> In words, apply (1) to 4, followed by (2), then (3).
>
> >> Finally, the problem:  is it possible to generate every
> >> integer via this formula?
>
>

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

Proving the conjecture is very hard, and disproving
it is even harder.

Also: suppose the conjecture is false. Then devise
an algorithm which determines, for any specified
integer, whether it's reachable via the formula.
That would be the hardest problem yet, maybe
undecidable.

--
Rich

[Tim Little]

On 2012-09-11, RichD <r_dela...@yahoo.com> wrote:
> Also: suppose the conjecture is false. Then devise an algorithm
> which determines, for any specified integer, whether it's reachable
> via the formula. That would be the hardest problem yet, maybe
> undecidable.

I'd guess that it's almost certainly true. Even if it were false, I
would not expect your problem to be undecidable.


- Tim

[Curlytop]

RichD set the following eddies spiralling through the space-time continuum:

> 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
> start with 4, or can any integer serve as a seed?

I've seen this expression presented as a solution" to the problem of
expressing various integers using a specified integer up to a specified
number of times using standard mathematical operators.

When expressed as:

n = -log_sqr(4) (log_4 ( sqr(sqr(sqr(sqr(....(4))...)) ))

where there are n nested sqr() signs, and log_k represents the logarithm to
base k, it becomes a schema for generating the infinity of integers using
three 4's.

It's an interesting exercise to program this up on a computer or even a
programmable calculator, to see how far it can go before (a) producing
silly answers and (b) crashing. The problem is that, as n increases, the
value returned from the chain of nested sqr()'s gets so close to 1 that the
floating point representation is limited in how accurately it can represent
the all-important difference from 1. Eventually it will give up and return
1 itself, the inner log operator then returns 0, and the outer log operator
bombs out.
--
ξ: ) Proud to be curly

Interchange the alphabetic letter groups to reply

[Martin Michael Musatov]

On 10 Set, 22:33, Tim Little <t...@little-possums.net> wrote:

Everything is decidable. Executable is up for debate. Musatov

[wilso]

A bit more precisely. You can have decidability or consistency, but not
both.

LEW
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/

--- news://freenews.netfront.net/ - complaints: ne...@netfront.net ---