Problem 40 – Digits of an Irrational

by

I scored myself a programming internship for the summer, so I thought it might be a good idea to actually do some programming. This will have to count…

In problem 40 we consider the irrational number defined by concatenating the positive integers, in order, and putting them to the right of the decimal place. We are asked for the product of some particular subset of digits.

As a solution that’s fairly easy to check for correctness, we can build up a string containing the irrational until we have enough digits, and then just pick out the digits we want. The stated problem only picks out powers of 10 as the determined digits, and so I threw together:

def solve(boundpow):
    irr = ""
    idx = 1
    bound = 10**boundpow
    while len(irr) < bound:
        irr += str(idx)
        idx += 1
    ret = reduce(lambda x,y:x*y,[int(irr[10**n - 1]) for n in xrange(0,boundpow+1)])
    return ret

I do like the use of reduce and list comprehension here. And I came up with the following that seems to be a quicker way to generate the irr string (plus it’s only one line):

irr = "".join(map(str, xrange(1,bound//(boundpow-1))))

This generates longer strings, but takes less time. It bothers me, a little, that I have to do “”.join instead of just sum. But what do I know. Anyway, it seems pretty pointless to keep track of the entire string. If larger powers of 10 were required, we’d start getting in trouble. Also, why require powers of 10?

So I have a slightly more general solution, which seems to also work (on the little testing I’ve done). Basically the idea is that I don’t need to remember all the digits that came before, when I go to concatenate the next integer. I just need to know the length of the string of digits before. And to be more general, my solve function takes in a list of integers (and assumes it is sorted in ascending order) indicating the position of the digits requested (position 1 being the first digit after the decimal).

def solve(digseq):
    lensofar = 0
    idx = 1
    ret = 1
    while len(digseq):
        nextstr = str(idx)
        nextlen = lensofar + len(nextstr)
        while len(digseq) and nextlen >= digseq[0]:
            ret *= int(nextstr[digseq[0] - lensofar - 1])
            digseq.pop(0)
        lensofar = nextlen
        idx += 1
    return ret

Seems to work out fine. Actually slower than the first solution, but whatever. It catches up if you go out one more power of 10 (though not if you use the faster generation of irr), and it’s more flexible.

Clearly there’s a more elegant solution, sorting out what integer the n-th digit would be part of basically algebraically. But I only care so much.

Advertisements

Tags:

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s


%d bloggers like this: