Solution to Prob #38

The problem statement is here. I spent some time thinking the best way to exit the brute force loop. I still don’t claim to have gotten it right, but this one is atleast not too slow and gets the right answer.


def list_to_number(l) :
    r = 0
    for i in l :
        r *= 10
        r += i
    return r

def number_to_list(n) :
    r = []
    while n :
        r.insert(0, n%10)
        n /= 10
    return r

def is_1to9_pandigital(l) :
    if len(l)  9 :
        return False
    for i in range(1, 10) :
        if i not in l :
            return False
    return True

def get_next_seed(s) :

    seed = s + 1
    while seed  9999 :
        return -1

    return seed

if __name__ == '__main__' :

    seed = 1
    pans = 0
    while True :
        pandigital = []
        n = 1
        while True :
            p = seed * n
            pl = number_to_list(p)
            fail = False
            for l in pl :
                if l in pandigital :
                    fail = True
                    break
            if fail :
                break
            pandigital.extend(pl)
            if is_1to9_pandigital(pandigital) :
                pd = list_to_number(pandigital)
                if pd >= pans :
                    pans = pd
                    print "Current Pandigital is ", pd
                    print seed, n

                fail = True
                break
            n += 1
            digits_left = []
            for i in range(1, 10) :
                if i not in pandigital :
                    digits_left.append(i)
            digits_left.sort(reverse=True)
            if n*seed > list_to_number(digits_left) :
                break
        seed = get_next_seed(seed)
        if seed == -1 :
            break
    print "Exhausted!"

I will upload this into the bitbucket repo real soon :)

Project Euler Solutions on Bitbucket

I am finally adding my solutions to a repository for better access and managing changes and/or incorporating suggestions. I have a dormant bitbucket account and since it is recently in news, I decided to make something out of the account :D

My bitbucket url.

Solution to Prob #44

The problem statement is here. I solved this problem a couple of days back trying to use lists and minimize the number of computations. Eventually, i found that the list could be a tad more expensive than the computation :D . Here is my final version of the solution, faster than I expected!

from math import sqrt

pentagonal = lambda n: n*((3*n)-1)/2

def is_pentagonal(num) :
    if num == 0 :
        return False
    n = int((1 + sqrt((1 + (24*num))))/6)
    return pentagonal(n) == num

# 1560090 7042750
#
if __name__ == '__main__' :

    max = 10
    done = False
    while not done:
        for i in xrange(2, max) :
            pi = pentagonal(i)
            for j in xrange(2, max) :
                pj = pentagonal(j)
                if not is_pentagonal(pi+pj) :
                    continue
                if is_pentagonal(abs(pi-pj)) :
                    print pi, pj
                    done = True
                    break
            if done :
                break
            max += 10

Some of this has no explanation:
Why am I moving in steps of 10?
No logic there, just happen to like ten.

How does this guarantee that the difference is minimal?
Well, I dunno. I did not even see if there are other numbers :D :D

Solution to Prob #125

The problem is stated here. My solution in python is here:

from math import sqrt

sqr = lambda n: n*n

def reverse(num) :
    rev = 0
    while num :
        rev = (rev*10) + num%10
        num /= 10
    return rev

def is_sum_of_squares(num) :
    for seed in xrange(int(sqrt(num))) :
        sum = 0
        agg = seed
        while sum<num :
            sum += sqr(agg)
            if sum == num  and agg  seed :
                return True
            agg += 1
    return False

if __name__ == '__main__' :
    sum = 0
    for i in xrange(2,100000000) :
        if i == reverse(i) :
            if is_sum_of_squares(i) :
                sum += i
    print sum

Takes way too long to complete. Quite literally had lunch by the time this completed :D

Solution to Prob #92

The problem is stated here. My solution in python is here. Takes a while to complete, though. I really need to start practicing threaded programming and/or parallel stuff in python. This one may also be a good case for parallel programming. My solution:


if __name__ == '__main__' :
    eighty9s = 0
    for i in xrange(2,10000000) :
        seed = i
        while 1 :
            if seed in (1,89) :
                break
            s_i = seed
            n_seed = 0
            while s_i :
                n = s_i % 10
                s_i /= 10
                n_seed += n*n
            seed = n_seed
        if seed == 89 :
            eighty9s += 1
    print eighty9s

Solution to Prob #46

The problem is defined here. Quite a simple one and the solution in python is :


from math import sqrt

def is_prime(num) :
    if num == 1 :
        return False
    for i in range(2, int(sqrt(num))+1) :
        if not num%i:
            return False
    return True
if __name__ == '__main__' :

    seed = 3
    primes = [2]
    while 1:
        if is_prime(seed) :
            primes.append(seed)
            seed += 2
            continue
        # composite. good.
        fail = False
        for prime in primes :
            seed_1 = seed - prime
            seed_2 = seed_1 / 2
            seed_3 = sqrt(seed_2)
            seed_4 = int(seed_3)
            if seed_4*seed_4 == seed_2 :
                fail = True
                break
        if fail :
            seed += 2
        else :
            print seed
            break

Solution to Prob #33

The problem is defined here. Another quite a tricky problem. Works, but the solution looks very ugly :( Anyway, my solution in python is :

if __name__ == '__main__' :
    pair = [1,1]
    for nr in range(10, 100) :
        nr_t = nr/10
        nr_o = nr%10
        if not nr_o :
            continue
        for dr in range(nr, 100) :
            dr_t = dr/10
            dr_o = dr%10
            ndr = 100
            nnr = 100
            common = None
            if dr_t not in (nr_t, nr_o) and dr_o in (nr_t, nr_o) :
                ndr = dr_t
                common = dr_o
            elif dr_t in (nr_t, nr_o) and dr_o not in (nr_t, nr_o) :
                ndr = dr_o
                common = dr_t
            else :
                continue
            if nr_t == common:
                nnr = nr_o
            else :
                nnr = nr_t
            if ndr and (nr*1.0)/dr == (nnr*1.0)/ndr :
                pair[0] *= nr
                pair[1] *= dr
    print pair, pair[1]/pair[0]

Solution to Prob #37

The problem is defined here. Tricky one there and it took this link to realize that 1 is not considered prime :( . Anyway, my solution in python is:


from math import sqrt, log

def is_prime(num) :
    if num == 1 :
        return False
    for i in range(2, int(sqrt(num))+1) :
        if not num%i:
            return False
    return True

def l2r_list(num) :
    retlist = []
    n = num
    while n > 9 :
        n %= pow(10, int(log(n,10)))
        retlist.append(n)
    return retlist

def r2l_list(num) :
    retlist = []
    n = num
    while n:
        n /= 10
        retlist.append(n)
    return retlist

def truncatable(num, r2l=False, l2r=False) :
    if r2l :
        l_r2l = r2l_list(num)
        for n in l_r2l :
            if not is_prime(n) :
                return False
        return True
    elif l2r :
        l_l2r = l2r_list(num)
        for n in l_l2r :
            if not is_prime(n) :
                return False
        return True
    return False

if __name__ == '__main__' :

    print is_prime(1)
    t_primes = []
    for i in range(10, 999999) :
        if is_prime(i) :
            if truncatable(i, l2r=True) and truncatable(i, r2l=True) :
            	t_primes.append(i)

    print len(t_primes), sum(t_primes)

I know what you are thinking! Many of those functions are redundant and useless. I wrote them trying to do half a dozen other things without realizing 1 is not prime. Works, nevertheless :D

Solution to Prob #56

Another easy problem, at least to solve using python. The statement of the problem is given here. My solution in python is here.

from string import atoi

def digital_sum(num) :
    return sum(map(atoi, list(str(num))))

if __name__ == '__main__' :
    max_sum = 0
    for a in range(1,100) :
        for b in range(1, 100) :
            dsum = digital_sum(pow(a, b))
            if dsum > max_sum :
                max_sum = dsum
    print max_sum

Solution to Prob #55

The problem is stated here. One of the more simpler problems to solve in python and worked quite fast too. Here is the python code that gets it right :)

def is_palindrome(num) :
    l_num = list(str(num))
    l_num.reverse()
    return num == atoi("".join(l_num))

def reverse(num) :
    s_num = str(num)
    l_num = list(str(num))
    l_num.reverse()
    return atoi("".join(l_num))

def is_lycherel(num, count=0) :
    if (count < 50) :
        n = num + reverse(num)
        if is_palindrome(n) :
            return False
        return is_lycherel(n, count+1)
    else :
        return True

if __name__ == '__main__' :
    lycherel_nums = []
    for no in range(10, 10000) :
        if(is_lycherel(no)) :
            lycherel_nums.append(no)
    print len(lycherel_nums)
Follow

Get every new post delivered to your Inbox.