> Got a math story problem where the question involves determining how
> many moves it will take to move a stack of various sized disks from one
> place to another with certain constraints.
>
> It works out that for n disks, it takes (2^n)-1 moves to accomplish the
> task. The problem states n=64 and that each move takes one second, and
> asks how long it will take to move the pile.
>
> If I want to give the answer in years, I have [(2^64)-1]/(60*60*24*365)
> or [2^64)-1]/31536000.
Using an HP49 calculator, I find
[2^64)-1]/31536000 = 58492417355 + 151441/31536000 exactly.
Note that a more careful analysis will note that the average year length
is nearer to 365.24 days, when you make some allowance for leap years.
>
> 2^64 is a *big* number (1.844674407e19) <g>. Using a calculator causes
> a loss of some of the significant digits. What's the best way to
> manipulate this expression to minimize that problem?
Get a better calculator
>
> I though about expressing the denominator as 2^x, then I could subtract
> exponents before expanding. I'd need to solve 2^x=31536000 for x, and
> I'm drawing a blank on how to do that.
>
> Dave
It works out that for n disks, it takes (2^n)-1 moves to accomplish the
task. The problem states n=64 and that each move takes one second, and
asks how long it will take to move the pile.
If I want to give the answer in years, I have [(2^64)-1]/(60*60*24*365)
or [2^64)-1]/31536000.
2^64 is a *big* number (1.844674407e19) <g>. Using a calculator causes
a loss of some of the significant digits. What's the best way to
manipulate this expression to minimize that problem?
I though about expressing the denominator as 2^x, then I could subtract
exponents before expanding. I'd need to solve 2^x=31536000 for x, and
I'm drawing a blank on how to do that.
Dave
--
remove alphabet to reply
(By the way, to do that, you'd want to take the log(base 2) of n, which is
simply ln(n) / ln(2).)
Instead, you can start with the list of factors you have for the
denominator and pull the 2's out from there, which also allows you to see
exactly what you're doing.
60*60*24*365 = (2^2*15)^2 *(2^3 *3) * 365
= 2^7 * 15*3*365,
which doesn't get you very far, but it does demonstrate the method.
-Doug Magnoli
Dave Lyle <dave...@execpc.com> wrote in alt.algebra.help:
>If I want to give the answer in years, I have [(2^64)-1]/(60*60*24*365)
>or [2^64)-1]/31536000.
There is essentially no difference between 2^64 and 2^64-1. (The
difference is one part in 2^64, which is roughly one part in
16*10^18 since 2^10 = approx 10^3.) So you can simply drop the -1
from the numerator, compute 2^64/31536000,and you're done.
(365 is not quite the right factor for converting days to years, by
the way. When there are a large number of years, 365.25 is more
accurate, though still not exact.)
>I though about expressing the denominator as 2^x, then I could subtract
>exponents before expanding.
That would be incorrect. The error is negligible in this particular
case, but still you should not think you can simplify
(2^a - 1) / 2^b
If you divide top and bottom by 2^b you then have
(2^(a-b) - 2^(-b))
which still has two powers of 2 to contend with. However, as I say,
in this particular problem with a = 64, the difference between the
actual numerator and plain 2^64 is numerically negligible.
> I'd need to solve 2^x=31536000 for x, and
>I'm drawing a blank on how to do that.
It's a moot point in this particular problem, but the general way to
solve exponential equations is to take log of both sides. (You can
use any base, as long as you use the same base on both sides.)
2^x = 31536000
log(2^x) = log(31536000)
log(a^b) = b*log(a), so
x*log(2) = log(31536000)
x = log(31536000)/log(2)
--
Stan Brown, Oak Road Systems, Cortland County, New York, USA
http://oakroadsystems.com
FAQs and math resources: http://oakroadsystems.com/math/resource.htm
more FAQs: http://oakroadsystems.com/tech/faqget.htm
[2^64)-1]/31536000
(2^64)/31536000-1/31536000
The last term can be dropped since it won't be significant enough to change
the result (it will affect the 8th decimal place), the first term can be
manipulated as follows:
=2^64/(2^7*3^3*5^3*73)
=2^57/(3^3*5^3*73)
=[2^28/(3^3*5^3*73)]*[2^29/(3^3*5^3*73)]
=[268435456/31536000]*[536870912/31536000]
=8.5120324*17.024065
=144.90939
Since you are dividing a nine digit number by an 8 digit number you will
have a result with eight significant digits. Then you multiply two eight
digit number resulting in a number with eight digit accuracy. Most
calculators will do nine digits.
"Dave Lyle" <dave...@execpc.com> wrote in message
news:39e7e805$0$1593$3929...@news.execpc.com...
>In article <39e7e805$0$1593$3929...@news.execpc.com>, Dave Lyle
><dave...@execpc.com> wrote:
>
>> Got a math story problem where the question involves determining how
>> many moves it will take to move a stack of various sized disks from one
>> place to another with certain constraints.
>>
>> It works out that for n disks, it takes (2^n)-1 moves to accomplish the
>> task. The problem states n=64 and that each move takes one second, and
>> asks how long it will take to move the pile.
>>
>> If I want to give the answer in years, I have [(2^64)-1]/(60*60*24*365)
>> or [2^64)-1]/31536000.
>Using an HP49 calculator, I find
>[2^64)-1]/31536000 = 58492417355 + 151441/31536000 exactly.
You dropped a digit: it should be 5849_4_2417355.
>Note that a more careful analysis will note that the average year length
>is nearer to 365.24 days, when you make some allowance for leap years.
365.2422 is a very good approximation. This yields 584554529390
years, 15 hours, 18 minutes, 45 seconds (to the nearest second). Of
course this ignores changes in the length of the year, and 365.2422 is
just a hair large.
[...]
Brian M. Scott
> >Using an HP49 calculator, I find
> >[2^64)-1]/31536000 = 58492417355 + 151441/31536000 exactly.
>
> You dropped a digit: it should be 5849_4_2417355.
Quite correct, thank you.
Neat! I'll have to remember that method. Thanks.
And thanks to all the others that replied.
--
Dave
remove alphabet to reply
Looks like your HP49 has two more significant digits than this TI-83
Plus.
Thanks!
> It's a moot point in this particular problem, but the general way to
> solve exponential equations is to take log of both sides. (You can
> use any base, as long as you use the same base on both sides.)
> 2^x = 31536000
> log(2^x) = log(31536000)
> log(a^b) = b*log(a), so
> x*log(2) = log(31536000)
> x = log(31536000)/log(2)
Got it, thanks.