iHardCode

The problem is to find the smallest number n such that n, 2n, 3n, 4n, 5n, and 6n all contain the same digits. For those who know the 1/7 rule, that's wise of you. For the rest of us, brute force comes to rescue. Python can do it in a few lines:

n = 1
while not all( set(str(i*n))==set(str(n)) for i in [2,3,4,5,6] ):
      n+= 1	
print n

 The funny thing is if I change the all function slightly to:

     all( [ set(str(i*n))==set(str(n)) for i in [2,3,4,5,6] ] )

 the runtime increases by 4 times to 5 seconds. I am guessing all() is smart enough to employ short-circuit, but don't take my words for it.

Live and learn.

This is by far one of the least elegant solutions to Problem 50 as posted on the Solutions Forum. It ran for about 400ms including Prime Sieve and Sift-Test, which is not too bad. The recursion is probably not necessary, but it works.

The problem asks:

Which prime, below one-million, can be written as the sum of the most consecutive primes?

The primeset collection is created for fast look up. Another way to do that is to have a Binary Search function. This is the solution in Python:

# find the longest prime chain
def genprime(n):  # adopted from http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/366178
    if n==2: return [2]
    elif n<2: return []
    s=range(3,n+1,2)
    mroot = n ** 0.5
    half=(n+1)/2-1
    i=0
    m=3
    while m <= mroot:
        if s[i]:
            j=(m*m-3)/2
            s[j]=0
            while j<half:
                s[j]=0
                j+=m
        i=i+1
        m=2*i+3
    return [2]+[x for x in s if x]
    
import time
ts = time.clock()
primes = genprime(10**6)
primeset = set(primes)
initsum = 0
for i in xrange(len(primes)):
    if initsum > 10**6:
        initsum -= primes[i-1]
        primes = primes[:i-1]
        break
    else:
        initsum+= primes[i]
    
def recursiveCount(cursum, curlen, ub):
    if cursum <= 2:    return 1
    global primeset, primes
    cur, lb, hasPrimeSum, oldub = cursum, 0, 0, ub
    for i in xrange(curlen):
        hasPrimeSum = cur in primeset
        if hasPrimeSum:
            break
        elif ub<len(primes)-1:
            cur += (-primes[lb] + primes[ub+1])
            lb, ub = lb+1, ub+1
    if hasPrimeSum:
        return cur
    else:
        return recursiveCount(cursum-primes[oldub], curlen+1, oldub-1)
        
print recursiveCount(initsum, 1, len(primes)-1), " took %s seconds" % (time.clock() - ts) 

In the era of software development where programmers don't really program anymore, there are still hang out spots on the web where you can pick up your old memories. I've been spending time solving riddles on ProjectEuler.net. It's been rediculously addictive. I am also taking this opportunity to learn Python, which is a modern dynamic language. Just to demostrate how slick it is, here's the code that reads in a list of words from a text file and counts the number of triangular words in it (Problem 42) :

 f = open("p42.txt").read().split(",")
words = [str.upper(str.strip( w.replace('"', ''))) for w in f]
val = [ sum( [ord(c)-64 for c in w]) for w in words]
trinums = [ (.5*n**2+.5*n) for n in xrange(1, max(val))]
print len( [ n for n in val if n in trinums])

 And this is the code that counts the product of the 10th, 100th, 1,000th, 10,000th, 100,000th, and 1,000,000th digits of an irrational decimal fraction (Problem 40.) Guess how long it is:

res = "".join([str(i) for i in xrange(10**6+1)])
print reduce(lambda x,y: x*y, [ int(res[10**i]) for i in xrange(1, 7)]) 

 Just looking at it gives me a boner.