Re: Powers and logic

On Mon, 20 Aug 2007 00:39:10 -0400, quasi <quasi@xxxxxxxx> wrote:

On 19 Aug 2007 22:35:21 -0400, hrubin@xxxxxxxxxxxxxxxxxxxx (Herman
Rubin) wrote:

In article <uefhc392t8pu0j9amus3scqdlil9v0rvll@xxxxxxx>,
quasi <quasi@xxxxxxxx> wrote:
On Sun, 19 Aug 2007 15:07:27 +0100, Angus Rodgers
<twirlip@xxxxxxxxxxx> wrote:

On Sat, 18 Aug 2007 16:36:47 -0400, quasi
<quasi@xxxxxxxx> wrote:

To dramatize the issue, here's a challenge problem ...

Find the sum of the digits (base 10) of 9^(9^(9^9)).

I spent a fruitless half hour banging my head against
this last night. Please reassure me that there is a
solution. Then I'll bang my head against the thing
some more, because it looks like a very nice problem.

I apologize -- it's not a nice problem -- it wasn't intended to be.

I have no idea how to solve it.

While the answer is provably within range of physical storage (it's
easy to show that it's less than 10 gigabytes), I know of no tractable
way of finding it. I'm not saying that there is no tractable method --
just that if there is, I don't see it.

No, 9^(9^9) takes about 30 megabytes of storage. Raising
9 to such a power is beyond what most believe to be the
capabilities of the universe.

You didn't read the problem.

The problem was not to represent 9^(9^(9^9)) base 10.

I was well aware that such a result would be out of range.

The problem was to find the sum of its digits.

Unless I made a mistake, the sum of the decimal digits of 9^(9^(9^9))
is _not_ out of range -- I estimated that the space requirement to be
less than 10 gigabytes.

Let me propose a seemingly easier challenge ...

Let x = 9^(9^(9^9)).

What is the leading digit (base 10) of x?

Even for this problem, while it might be doable, I have no idea how to
do it.

It is easy to give an algorithm which could be calculated
in a terabyte or so cycle times.

Well, a terabyte of cycles is what -- half an hour of computing time?
Ok, out of curiosity, what's the answer? I'm not suggesting that you
do it -- the question is for anyone who is also curious and who feels
like fooling around with the required algorithms (and who was a
terabyte of cycles to spare).

Hint: how would you calculate the leading digit of 9^(9^9) rather
easily on a computer with sufficient accuracy, well within reach.

Since 9^(9^9) can be multiplied out in full, with successive squaring
to reduce the number of multiplications, and with the result stored in
a file, one can always find the leading digit by inspection.

However, such an almost brute force method can't possibly work for
9^(9^(9^9)) since the space requirement for the full representation is
out of bounds. Perhaps there's a way to truncate the partial products
to some kind of floating point representation, keeping both upper and
lower bounds, but as far as I can see, such truncation would lose too
much accuracy to be useful in finding the leading digit.

I'll have to think about it.

Unless one happens to be unlucky, the usual "double
precision" in which most floating arithmetic is done
is quite adequate.

I'm not saying I don't believe it -- but I do find that claim very
surprising.

To Herman Rubin:

Ok, I thought about your claim. I can't see it.

I suspect you made a mistake -- one extra 9 is major for this
question.

Let me restate the questions, together with some observations ...

Let x=9^(9^(9^9)).

I think it's clear that to write out the full decimal representation
of x is infeasible. The space requirement would exceed the capacity of
any possible medium.

Let s(x) be the sum of the digits of x. By my estimate, the space
requirement for the full decimal representation s(x) is less than 10
gigabytes. It's a crude upper bound, easily obtained. Perhaps someone
can do an independent estimate?

Ok, so based on the above, the value of s(x) could be easily stored on
a typical hard drive. However, I'm not saying there's any practical
algorithm to find s(x). I'm only saying that the result is not out
range in terms of the space required to store it.

This suggests a question ...

Question (1): Find s(x).

The next question is even simpler, or at least it seems like it should
be simpler.

Question (2): Find the leading digit of x.

Herman Rubin's reply (excerpted below) suggests that question (2) is
actually feasible.

quasi wrote:

|| Let x = 9^(9^(9^9)).
||
|| What is the leading digit (base 10) of x?"

Herman Rubin replied:

| It is easy to give an algorithm which could be calculated
| in a terabyte or so cycle times.

Perhaps I am misinterpreting, or perhaps there's some trick that I'm
failing to see, but for now, I don't believe Herman's claim.

Can anyone suggest an algorithm with reasonable time and space
requirements for either of the above questions? If not, is there
reason to believe that there is no such algorithm?

quasi
.

Relevant Pages

  • Re: Powers and logic
    ... quasi wrote: ... one can always find the leading digit by inspection. ... The space requirement would exceed the capacity of ... | in a terabyte or so cycle times. ...
    (sci.math)
  • Re: Powers and logic
    ... quasi wrote: ... one can always find the leading digit by inspection. ... The space requirement would exceed the capacity of ... Herman Rubin, Department of Statistics, Purdue University ...
    (sci.math)
  • Re: No Set Contains Every Computable Natural (was Church-Turing compared to Zuse-Fredkin thesis)
    ... Russell is right about Turing saying this, ... You might not want to call this an algorithm which has ... decimal representation of x digit by digit. ...
    (comp.theory)
  • Re: Large-numbers division way too slow -- what to do?
    ... > algorithm is now responsible for most of the slowness. ... I want to return the quotient or the remainder). ... In the division function, at the very bottom, I placed: ... processing the last digit becomes the remainder. ...
    (sci.crypt)
  • Re: continued fractions
    ... The "one bit at a time" algorithm is just a special case of the ... The dividend and divisor will be expressed as ... The crucial part here is the "guessing" of the digit. ... digit is 1, and the result of the subtraction is your new w; ...
    (comp.lang.forth)
Loading