#!/usr/bin/python# -*- coding: iso-8859-15 -*-import math,sys,time,operator# Simple primality check (slow)# Basic optimization in place: only check up to sqrt(n)def isprime_basic(n): if n == 1: # Special case return False for i in xrange(2,int((n**0.5)+1)): if n%i==0: return False return True# Build a list of small primes to speed up primality checkssmallprimes=[]for n in xrange(2,600): if isprime_basic(n): smallprimes.append(n)# Store largest checked primelastprime=smallprimes[-1]# Optimize primality checks - checks for small factors first# Also optimizes out redundant factors (only up to sqrt(n)# and only if it hasn't been checked before)def isprime(n): if n&1 == 0 and n > 2: #Cheap test for evenness return False if n == 1: # Special case return False for i in smallprimes: # Check small primes if n > i and n % i == 0: # factor test return False elif n == i: # equal (prime) test return True # Note that n < i Should Never Happen (TM). # Bring on The Slowness! for i in xrange(lastprime,int((n**0.5)+1),2): if n%i==0: return False return True# This is faster than looping over numbers checking with isprime(),# since it builds a list and uses that as factor checks.def primesmax(maxn): primes = [2] # Start with 2 for i in xrange(3, maxn, 2): # Run through all ints, skip evens for p in primes: # Check all previous primes if i % p == 0 or p * p > i: # factor test break if i % p != 0: primes.append(i) return primes# Number of primes versiondef primesnum(nprimes): primes = [2] # Start with 2 for i in xrange(3, sys.maxint, 2): # Run through all ints, skip evens for p in primes: # Check all previous primes if i % p == 0 or p * p > i: # factor test break if i % p != 0: primes.append(i) if len(primes) == nprimes: return primes # Yes, python supports longints, but not xrange, and we want to keep this clean # Anything needing this many primes would violate the 1-min rule anyway # Use a counter and a while loop to prevent this if needed print "Cannot calculate %d primes: maximum int reached"%nprimes sys.exit(1)# This is basically a looping version of isprime() above# When it finds a factor, it divides n by it and restarts.# Note that this starts with low factors, so the factor list# is sorted.def factor(n): factors=[] while True: # Restart checks once we find a factor # Beware those coming from other languages: this is a forelse loop! # Quick reminder: else clause runs when loop completes with no break for i in smallprimes: # Check for small primes as factors if n == i: # n is now prime (and has to be the largest factor) factors.append(i) return factors if n % i == 0: # i is a smaller factor of n, divide by it n = n / i factors.append(i) break else: break # Gone through all small primes, time for some larger ones while True: # Same deal here, repeat until we find the largest factor for i in xrange(lastprime,int((n**0.5)+1)): # Check all factors smaller than n if n % i == 0: # Factor, divide through n = n / i factors.append(i) break else: # no factors left, n has to be prime (and the largest factor) factors.append(n) return factors# Factor the number, then return all composite factorsdef compfactors(n): f=factor(n) # Factor the number ft=[False]*len(f) # Prepare binary counter fl=set([1]) # Make a set of composite factors - this ensures no dupes # We're basically implementing a binary counter here # ft is an array of "bits" (booleans), which tell us which factors to multiply while True: for i in xrange(len(f)): # This is basically counter++ if ft[i]: ft[i] = False continue else: ft[i] = True break else: break p=1 # Now multiply all active factors for i in xrange(len(f)): if ft[i]: p *= f[i] fl.add(p) # And add this composite factor to the set return fldef num2words(n): def tens_ones(n): w_onesteens = [ "zero","one","two","three","four","five","six","seven","eight","nine", "ten","eleven","twelve","thirteen","fourteen","fifteen","sixteen","seventeen","eighteen","nineteen" ] w_tens = [ None,None,"twenty","thirty","forty","fifty","sixty","seventy","eighty","ninety", ] if n > 99: raise ValueError("wtf") if n < 20: return w_onesteens[n] if n%10==0: return w_tens[n/10] return w_tens[n/10]+"-"+w_onesteens[n%10] def hundreds(n): if n > 999: raise ValueError("wtf") if n < 100: return tens_ones(n) if n%100 == 0: return tens_ones(n/100)+" hundred" return tens_ones(n/100)+" hundred and "+tens_ones(n%100) def thousands(n): if n > 999999: raise ValueError("wtf") if n < 1000: return hundreds(n) if n%1000==0: return hundreds(n/1000)+" thousand" return hundreds(n/1000)+" thousand "+hundreds(n%1000) return thousands(n)def stopwatch(f): start=time.clock() print "=======================================================" print "Starting problem %s"%f.__name__ f() stop=time.clock() print "Problem %s complete in %.3f seconds"%(f.__name__,stop-start)# ============================== problems ==============================# Not much to see here. This is easy.def sum35(): sum=0 for i in xrange(1000): if i % 3 == 0 or 1 % 5 == 0: sum += i print sum# Again, straightforward. I could do without the storage of the entire# sequence, but I'm lazy. It's short anyway.def fibevensum(): fibo=[1,2] while True: n=fibo[-1]+fibo[-2] if n >= 1000000: break fibo.append(n) sum=0 for i in fibo: if i&1==0: sum += i print sum# See factor() abovedef largefactor(): print factor(317584931803)[-1]# Brute force. Relatively slow due to the string conversions, but OK for our purposes here.def palindrome(): lg=0 for i in xrange(100,1000): for j in xrange(100,1000): prod=i*j if prod > lg and str(prod)==str(prod)[-1::-1]: lg = prod print lg# Find factors of 2-20, merge and multiplydef smalldiv(): fc = {} # fc is a dictionary whey key,value means key**value (factor, number of occurrences) for i in xrange(2,20): # Find factors of 2-20 fact = factor(i) fc2 = {} for f in fact: # For each factor, accumulate into dictionary fc2 cur = fc2.get(f,0) fc2[f] = cur + 1 for k,v in fc2.items(): # Then take max(fc_n,fc2_n) for each key in fc,fc2 and set cur = fc.get(k,0) fc[k] = max(cur,v) prod = 1 for k,v in fc.items(): # multiply together all factors (value is the number of times, that is, the exponent) prod *= k**v print prod# Nothing of interest here. Just do it and calculate.def sumsqsqsum(): msum = sum(range(1,101)) msumsq = sum(map(lambda x: x**2,range(1,101))) print msum**2 - msumsq# See primesnum() above.def prime10001(): print primesnum(10001)[-1]# This is an easy algorithm# Just run through all sequences of 5 digits and find the largest onedef prod5(): # There is absolutely zero reason to use an int here - we're # basically treating this as a string in this sort of problem nt="7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450" gt=0 for s in xrange(len(nt)-4): # go through all start points (note that the last one needs the last 5 digits, hence -4) prod=1 for n in xrange(s,s+5): # run through 5 consecutive digits prod *= int(nt[n]) # multiply them together gt = max(prod,gt) # find largest print gt# Brute force here, with some obvious stuff:# - no need to calculate a, since it's always 1000-b-c# - b < 1000-c always, so keep that in mind and don't waste time# - b < c always toodef pythtrip(): for c in xrange(2,1000): bmax=min(c,1000-c) for b in xrange(1,bmax): a=1000-b-c if a < b and a*a+b*b==c*c: print a*b*c return# Nothing interesting here - see primesmax above.def megaprimes(): print sum(primesmax(1000000))# Just run through everything.# Of course, left = right and up = down and there are only two diagonals, since# multiplication is commutative. 4 runs total.def gridproduct(): grid = [ [ 8, 2,22,97,38,15, 0,40, 0,75, 4, 5, 7,78,52,12,50,77,91, 8], [49,49,99,40,17,81,18,57,60,87,17,40,98,43,69,48, 4,56,62, 0], [81,49,31,73,55,79,14,29,93,71,40,67,53,88,30, 3,49,13,36,65], [52,70,95,23, 4,60,11,42,69,24,68,56, 1,32,56,71,37, 2,36,91], [22,31,16,71,51,67,63,89,41,92,36,54,22,40,40,28,66,33,13,80], [24,47,32,60,99, 3,45, 2,44,75,33,53,78,36,84,20,35,17,12,50], [32,98,81,28,64,23,67,10,26,38,40,67,59,54,70,66,18,38,64,70], [67,26,20,68, 2,62,12,20,95,63,94,39,63, 8,40,91,66,49,94,21], [24,55,58, 5,66,73,99,26,97,17,78,78,96,83,14,88,34,89,63,72], [21,36,23, 9,75, 0,76,44,20,45,35,14, 0,61,33,97,34,31,33,95], [78,17,53,28,22,75,31,67,15,94, 3,80, 4,62,16,14, 9,53,56,92], [16,39, 5,42,96,35,31,47,55,58,88,24, 0,17,54,24,36,29,85,57], [86,56, 0,48,35,71,89, 7, 5,44,44,37,44,60,21,58,51,54,17,58], [19,80,81,68, 5,94,47,69,28,73,92,13,86,52,17,77, 4,89,55,40], [04,52, 8,83,97,35,99,16, 7,97,57,32,16,26,26,79,33,27,98,66], [88,36,68,87,57,62,20,72, 3,46,33,67,46,55,12,32,63,93,53,69], [ 4,42,16,73,38,25,39,11,24,94,72,18, 8,46,29,32,40,62,76,36], [20,69,36,41,72,30,23,88,34,62,99,69,82,67,59,85,74, 4,36,16], [20,73,35,29,78,31,90, 1,74,31,49,71,48,86,81,16,23,57, 5,54], [ 1,70,54,71,83,51,54,69,16,92,33,48,61,43,52, 1,89,19,67,48], ] gp=0 # Rows for row in grid: #loop through rows for start in xrange(len(row)-3): #Loop through start items in row p=reduce(operator.mul,row[start:start+4]) # calculate product gp=max(gp,p) # Columns - just transpose the grid and do the same for col in zip(*grid): #loop through columns for start in xrange(len(col)-3): #Loop through start items in column p=reduce(operator.mul,col[start:start+4]) # calculate product gp=max(gp,p) # Slope=-1 diagonals for y in xrange(len(grid)-3): #Loop through start y coordinates for x in xrange(len(grid[y])-3): #Loop through start x coordinates p=grid[y][x] * grid[y+1][x+1] * grid[y+2][x+2] * grid[y+3][x+3] # calculate product gp=max(gp,p) # Slope=1 diagonals for y in xrange(len(grid)-3): #Loop through start y coordinates for x in xrange(len(grid[y])-3): #Loop through start x coordinates p=grid[y+3][x] * grid[y+2][x+1] * grid[y+1][x+2] * grid[y][x+3] # calculate product gp=max(gp,p) print gp# There's probably a better way of doing this.# For now, just test all triangle numbers and count factorsdef trianglenums(): # The formula for triangle numbers is: # tn(n) = n(n+1)/2 n=1 while True: tn=n*(n+1)/2 f=compfactors(tn) if len(f) > 500: print tn return n += 1# Python handles large numbers easily, so this is trivialdef sumdigs(): nums= [ 37107287533902102798797998220837590246510135740250, 46376937677490009712648124896970078050417018260538, 74324986199524741059474233309513058123726617309629, 91942213363574161572522430563301811072406154908250, 23067588207539346171171980310421047513778063246676, 89261670696623633820136378418383684178734361726757, 28112879812849979408065481931592621691275889832738, 44274228917432520321923589422876796487670272189318, 47451445736001306439091167216856844588711603153276, 70386486105843025439939619828917593665686757934951, 62176457141856560629502157223196586755079324193331, 64906352462741904929101432445813822663347944758178, 92575867718337217661963751590579239728245598838407, 58203565325359399008402633568948830189458628227828, 80181199384826282014278194139940567587151170094390, 35398664372827112653829987240784473053190104293586, 86515506006295864861532075273371959191420517255829, 71693888707715466499115593487603532921714970056938, 54370070576826684624621495650076471787294438377604, 53282654108756828443191190634694037855217779295145, 36123272525000296071075082563815656710885258350721, 45876576172410976447339110607218265236877223636045, 17423706905851860660448207621209813287860733969412, 81142660418086830619328460811191061556940512689692, 51934325451728388641918047049293215058642563049483, 62467221648435076201727918039944693004732956340691, 15732444386908125794514089057706229429197107928209, 55037687525678773091862540744969844508330393682126, 18336384825330154686196124348767681297534375946515, 80386287592878490201521685554828717201219257766954, 78182833757993103614740356856449095527097864797581, 16726320100436897842553539920931837441497806860984, 48403098129077791799088218795327364475675590848030, 87086987551392711854517078544161852424320693150332, 59959406895756536782107074926966537676326235447210, 69793950679652694742597709739166693763042633987085, 41052684708299085211399427365734116182760315001271, 65378607361501080857009149939512557028198746004375, 35829035317434717326932123578154982629742552737307, 94953759765105305946966067683156574377167401875275, 88902802571733229619176668713819931811048770190271, 25267680276078003013678680992525463401061632866526, 36270218540497705585629946580636237993140746255962, 24074486908231174977792365466257246923322810917141, 91430288197103288597806669760892938638285025333403, 34413065578016127815921815005561868836468420090470, 23053081172816430487623791969842487255036638784583, 11487696932154902810424020138335124462181441773470, 63783299490636259666498587618221225225512486764533, 67720186971698544312419572409913959008952310058822, 95548255300263520781532296796249481641953868218774, 76085327132285723110424803456124867697064507995236, 37774242535411291684276865538926205024910326572967, 23701913275725675285653248258265463092207058596522, 29798860272258331913126375147341994889534765745501, 18495701454879288984856827726077713721403798879715, 38298203783031473527721580348144513491373226651381, 34829543829199918180278916522431027392251122869539, 40957953066405232632538044100059654939159879593635, 29746152185502371307642255121183693803580388584903, 41698116222072977186158236678424689157993532961922, 62467957194401269043877107275048102390895523597457, 23189706772547915061505504953922979530901129967519, 86188088225875314529584099251203829009407770775672, 11306739708304724483816533873502340845647058077308, 82959174767140363198008187129011875491310547126581, 97623331044818386269515456334926366572897563400500, 42846280183517070527831839425882145521227251250327, 55121603546981200581762165212827652751691296897789, 32238195734329339946437501907836945765883352399886, 75506164965184775180738168837861091527357929701337, 62177842752192623401942399639168044983993173312731, 32924185707147349566916674687634660915035914677504, 99518671430235219628894890102423325116913619626622, 73267460800591547471830798392868535206946944540724, 76841822524674417161514036427982273348055556214818, 97142617910342598647204516893989422179826088076852, 87783646182799346313767754307809363333018982642090, 10848802521674670883215120185883543223812876952786, 71329612474782464538636993009049310363619763878039, 62184073572399794223406235393808339651327408011116, 66627891981488087797941876876144230030984490851411, 60661826293682836764744779239180335110989069790714, 85786944089552990653640447425576083659976645795096, 66024396409905389607120198219976047599490197230297, 64913982680032973156037120041377903785566085089252, 16730939319872750275468906903707539413042652315011, 94809377245048795150954100921645863754710598436791, 78639167021187492431995700641917969777599028300699, 15368713711936614952811305876380278410754449733078, 40789923115535562561142322423255033685442488917353, 44889911501440648020369068063960672322193204149535, 41503128880339536053299340368006977710650566631954, 81234880673210146739058568557934581403627822703280, 82616570773948327592232845941706525094512325230608, 22918802058777319719839450180888072429661980811197, 77158542502016545090413245809786882778948721859617, 72107838435069186155435662884062257473692284509516, 20849603980134001723930671666823555245252804609722, 53503534226472524250874054075591789781264330331690, ] print str(sum(nums))[:10]# Use a cache to save a lot of time# This could be optimized further, since we don't save all nums# in the sequence to the cache, only the first (current)def longcollatz(): longest=0 longnum=0 cache={} for i in xrange(1,1000000): n=i cnt = 1 while n != 1: if n in cache: cnt += cache[n] - 1 break if n&1==0: n=n/2 else: n=3*n+1 cnt += 1 cache[i]=cnt if cnt > longest: longest=cnt longnum=i print longnum# Recursive brute force implementation, with caching - very fastdef routes(): # Stores number of routes from tuple (x,y) subcache = {} # Calculate subroutes for a mx by my grid, starting from position x,y def subroutes(mx,my,x,y): if (x,y) in subcache: # Check cache return subcache[(x,y)] if x == mx: # if x = max, there is only one way to go sr=1 elif y == my: # same for y sr=1 else: # otherwise calculate subroutes advancing in both directions sr=subroutes(mx,my,x+1,y)+subroutes(mx,my,x,y+1) # cache the result subcache[(x,y)]=sr return sr print subroutes(20,20,0,0)# Yay easy python longints. Nothing to see here.def sumpow2(): # One liner! w00t! print sum(map(int,str(2**1000)))def numletters(): sum=0 for i in range(1,1001): n=num2words(i) l = len(n.replace(" ","").replace("-","")) sum += l print sumprint "======================================================="print "Starting problems..."start=time.clock()stopwatch(sum35)stopwatch(fibevensum)stopwatch(largefactor)stopwatch(palindrome)stopwatch(smalldiv)stopwatch(sumsqsqsum)stopwatch(prime10001)stopwatch(prod5)stopwatch(pythtrip)stopwatch(megaprimes)stopwatch(gridproduct)stopwatch(trianglenums)stopwatch(sumdigs)stopwatch(longcollatz)stopwatch(routes)stopwatch(sumpow2)stopwatch(numletters)print "======================================================="print "All problems complete. Total time %.3f seconds"%(time.clock()-start)print "======================================================="