PyPE solution to PE problem 99

Registered by Scott Armitage

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

Sprints

Whiteboard

    ProjectEuler.net problem 99
    ===========================

    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)

(?)

Work Items

This blueprint contains Public information 
Everyone can see this information.

Subscribers

No subscribers.