Re: Powers and logic
- From: quasi <quasi@xxxxxxxx>
- Date: Mon, 20 Aug 2007 00:39:10 -0400
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.
quasi
.
- Follow-Ups:
- Re: Powers and logic
- From: quasi
- Re: Powers and logic
- References:
- Powers and logic
- From: almeidabatista@xxxxxxx
- Re: Powers and logic
- From: quasi
- Re: Powers and logic
- From: Angus Rodgers
- Re: Powers and logic
- From: quasi
- Re: Powers and logic
- From: Herman Rubin
- Powers and logic
- Prev by Date: Re: confused about field axioms
- Next by Date: A simple group problem
- Previous by thread: Re: Powers and logic
- Next by thread: Re: Powers and logic
- Index(es):
Relevant Pages
|
