PyPE solution to PE problem 99
PyPE solution to PE problem 99
Blueprint information
- Status:
- Complete
- Approver:
- None
- Priority:
- Undefined
- Drafter:
- None
- Direction:
- Needs approval
- Assignee:
- None
- Definition:
- Approved
- Series goal:
- None
- Implementation:
- Implemented
- Milestone target:
- None
- Started by
- Scott Armitage
- Completed by
- Scott Armitage
Related branches
Related bugs
Sprints
Whiteboard
ProjectEule
===
Comparing two numbers written in index form like 2^(11) and 3^(7) is not
difficult, as any calculator would confirm that
2^(11) = 2048 < 3^(7) = 2187.
However, confirming that 632382^(518061) > 519432^(525806) would be much
more difficult, as both numbers contain over three million digits.
Using base_exp.txt (right click and 'Save Link/Target As...'), a 22K text
file containing one thousand lines with a base/exponent pair on each line,
determine which line number has the greatest numerical value.
NOTE: The first two lines in the file represent the numbers in the example
given above.
Solution
--------
First we read the data from the file and split it into a list of (b,e)
tuples. Once we know the (b,e) tuple that has the greatest numerical value
of b^e, we find the index, adding one because Python counts lists from 0
whereas PE counts them from 1.
The only interesting step is finding this maximum value. Instead of trying
to calculate these large numbers, we use the fact that
ln(b^e) = e*ln(b),
and our knowledge that the ln function is monotonic (i.e. if b1^e1 > b2^e2,
then ln(b1^e1) > ln(b2^e2). This greatly simplifies the computations.
Answer
------
709 (895447, 504922)