Posts Tagged ‘prob40’

Problem 40 – Digits of an Irrational

May 11, 2010

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])
        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.