Project Euler

# Problem 35.
from rogutil import *
#-------set for reference...........

def main():

        sett = set()
        for item in gen_primes():
                        if item < 1000000:
                                sett.add(item)
                        else:
                                break
        #...........................................

        log = 0
        store = set()
        limit = 0
        z = 0
        kount = 0

#------Generate primes for checking-----------------------------
        prims = gen_x(100000, gen_primes)     # prime number genny
        prim = prims[z]              # For incrementing the Prime Num
                #print(prim)
        prim = list(str(prim)) #Convert to list
#------------------------------------------------------------------
#----------Rotate the prime number---------------------------------
        while log < 1000000 :
                for i in range (len(prim)):
                        prim.append(prim[0])
                        prim.remove(prim[0])
                        m = prim
                        m = int(''.join(list(map(str, m))))
                        store.add(m)

                if store <= sett:
                        kount += 1
                        z += 1
                        prim = prims[z]
                        log = prim
                        prim = list(str(prim))
                        store = set()
                else:
                        z += 1
                        prim = prims[z]
                        log = prim
                        prim = list(str(prim))
                        store = set()

        print("Count = ",kount," Prime = ",prim)

if __name__ == '__main__':
        main()
# Problem 36
'''The decimal number, 585 = 10010010012 (binary),
is palindromic in both bases.

Find the sum of all numbers, less than one million,
 which are palindromic in base 10 and base 2.

(Please note that the palindromic number, in either
base, may not include leading zeros.)'''


import time
tt = time.time()

def main():

        sett = set()


        for num in range(1, 1000000, 1):
                BinNum = bin(num)[2:]
                RevBinNum = BinNum[::-1]
                num = str(num)
                reverse = num[::-1]

                ''' if palindrome add to set'''
                if num == reverse and BinNum == RevBinNum:
                        sett.add(int(num))
        print(sum(sett))

if __name__ == '__main__':
        main()
        print("time = ",time.time() - tt," secs")
# Problem 37.

'''The number 3797 has an interesting property. Being prime itself,
it is possible to continuously remove digits from left to right,
and remain prime at each stage: 3797, 797, 97, and 7. Similarly
we can work from right to left: 3797, 379, 37, and 3.

Find the sum of the only eleven primes that are both truncatable
from left to right and right to left.

NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes.'''

from rogutil import * #@UnusedWildImport


def main():

        z = 0
        sett = set()
        sett2 = set()
        sett3 = set()
        b = 0

        #Generate primes for checking
        primes = gen_primes()

#----Final set requires 11 ints---------
        while len(sett3) < 11:
                prim = next(primes)
                #---primes <10 will not qualify-----
                if prim <= 11:
                        continue
                prim = str(prim)
                sett = set()
                sett2 = set()
                # -----------Split up the Prime number----
                for i in range(len(prim)):
                        ForTest = (prim[i:])
                        sett.add(int(ForTest))
                for i in range(1,len(prim)):
                        MoreTest = (prim[:i])
                        sett.add(int(MoreTest))
                #-----------------------------------------
                sett = list(sett)
                #-----Check if the slices are all prime---
                #----put primes in a list (set)-----------
                for j in range(0, len(sett)):
                        if isprime(sett[j]):
                                sett2.add(sett[j])
                        else:
                                pass
                #--- both lists the same length?-------
                #--- if so put the Prime in the collection--
                if len(sett) == len(list(sett2)):
                        sett3.add(int(prim))
                        z += 1
                        prim = str(prim)
                        b += 1
                else:
                        z += 1
                        prim = str(prim)
                        b += 1

        print("Result.... ",sum(sett3))

if __name__ == '__main__':
        main()
# Problem 38.
'''Take the number 192 and multiply it by each of 1, 2, and 3:

        192 × 1 = 192
        192 × 2 = 384
        192 × 3 = 576

By concatenating each product we get the 1 to 9 pandigital,
 192384576. We will call 192384576 the concatenated
  product of 192 and (1,2,3)

The same can be achieved by starting with 9 and
multiplying by 1, 2, 3, 4, and 5, giving the
pandigital, 918273645, which is the concatenated
product of 9 and (1,2,3,4,5).

What is the largest 1 to 9 pandigital 9-digit number t
hat can be formed as the concatenated product of an
integer with (1,2, ... , n) where n > 1?'''

'''Note... using four I could only achieve a seven figure
number which began with 9. This left two as a product.'''



import time
tt = time.time()


the_set = set()
result = ""

for i in range(9876, 1, -1):
        the_set = set()
        j = 1
        product = i * j
        k = 2
        product2 = i * k
        result = str(product) + str(product2)
        if "0" in result:
                continue
        for y in result:
                the_set.add(y)
        if len(the_set) == 9:
                print(the_set, result)
                break

print(time.time() - tt)
# Problem 39.
#---------------------------------------------------
#!/usr/bin/env python
import sys
sys.path.append("../")
from rogutil import *
#import pdb; pdb.set_trace()

'''If p is the perimeter of a right angle triangle with
integral length sides,
 {a,b,c}, there are exactly three solutions for p = 120.

{20,48,52}, {24,45,51}, {30,40,50}

For which value of p = 1000, is the number of solutions
maximised?'''


def main():
        pass
        lst = []
        #--using hyp = sqrt of a^2 + b^2 ----------------
        # -- then letting thru integers < 1000-----------
        for i in range(1,501,1):
                for j in range(1,501,1):
                        k =  math.sqrt(i ** 2 + j ** 2)
                        if k == int(k):
                                l =(i + j + k)
                                if l <= 1000:
                                        lst.append(l)

        #---sorting the results--------------------------
        d = {}
        for i in set(lst):
                d[i] = lst.count(i)



        #--pull the highest value out----------------------
        print(max(d, key = d.get))





if __name__ == '__main__':
        #pdb.runcall(main)
        main()
# Problem 40.

'''An irrational decimal fraction is created by concatenating the
positive integers:

0.123456789101112131415161718192021...

It can be seen that the 12th digit of the fractional part is 1.

If dn represents the nth digit of the fractional part, find the
value of the following expression.

d1 × d10 × d100 × d1000 × d10000 × d100000 × d1000000'''


'''Looking for the millionth-1 integer therefore the string does
not need to be that length when the numbers are split up.'''

str1 = ""
for i in range(1,200000,1):
        str1 += str(i)


print(int(str1[0]) * int(str1[9]) * int(str1[99]) * int(str1[999]) * \
          int(str1[9999]) * int(str1[99999]) * int(str1[999999]))
# Problem 41.
from rogutil import *

def main():
#---Permutation function------------------------------
        def all_perms(str):
                if len(str) <= 1:
                           yield str
                else:
                        for perm in all_perms(str[1:]):
                                for i in range(len(perm) + 1):
                                        yield perm[:i] + str[0:1] + perm[i:]

#-------------------------------------------------------
        lst = []
        lst2 = []
        j = 10
#---start at 123456789 and work down--------------------
#----stop as soon as list lst2 is populated-------------
        while len(lst2) == 0:
                for i in range(1,j):
                        lst.append(i)

                for p in all_perms(lst):
                        k = int(''.join(list(map(str, p))))
                        if isprime(k):
                                lst2.append(k)

                lst = []
                j -= 1

        print(max(lst2))
        print("done")

if __name__ == '__main__':
        main()
# Problem 42
'''The nth term of the sequence of triangle numbers is given by,
tn = ½n(n+1); so the first ten triangle numbers are:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

By converting each letter in a word to a number
corresponding to its alphabetical position and adding
 these values we form a word value. For example, the word
 value for SKY is 19 + 11 + 25 = 55 = t10. If the word value
  is a triangle number then we shall call the word a triangle word.

Using words.txt (right click and 'Save Link/Target As...'),
 a 16K text file containing nearly two-thousand common
 English words, how many are triangle words?'''



from rogutil import *
from string import ascii_lowercase

f = open("words.txt", "r").read()
names = ([x[1:][:-1].lower() for x in f.split(",")])
sett = set()
#---triangle number set for reference---------------
trinum = TriangleNum()
for i in range(100):
        sett.add(trinum.next())

kount = 0
total = 0
#----loop thru the names list--------------------------
for word in names:
        for letter in list(word):
                total += list(ascii_lowercase).index(letter) + 1
        if total in sett:
                kount += 1
                total = 0
        else:
                total = 0

print(kount)
# Project 43.
'''The number, 1406357289, is a 0 to 9 pandigital number because it is made up
 of each of the digits 0 to 9 in some order, but it also has a rather
 interesting sub-string divisibility property.

Let d1 be the 1st digit, d2 be the 2nd digit, and so on. In this way,
 we note the following:

        d2d3d4=406 is divisible by 2
        d3d4d5=063 is divisible by 3
        d4d5d6=635 is divisible by 5
        d5d6d7=357 is divisible by 7
        d6d7d8=572 is divisible by 11
        d7d8d9=728 is divisible by 13
        d8d9d10=289 is divisible by 17

Find the sum of all 0 to 9 pandigital numbers
 with this property.'''


from rogutil import *
from time import sleep
import time
tt = time.time()
#----permutation generator-------------------------
def main():
        def all_perms(str):
                if len(str) <= 1:
                           yield str
                else:
                        for perm in all_perms(str[1:]):
                                for i in range(len(perm) + 1):
                                        yield perm[:i] + str[0:1] + perm[i:]

#---------------------------------------------------
        kount = 0
        lst = []
        m = []
        p = [1,4,0,6,3,5,7,2,8,9]



        for num in all_perms(p):
                if num[0] == 0:
                        continue

                if (join(num[7:10]) % 17 == 0) and\
                   join(num[6:9]) % 13  == 0 and\
                   join(num[5:8]) % 11 == 0 and\
                   join(num[4:7]) % 7 == 0 and\
                   join(num[3:6]) % 5 == 0 and\
                   join(num[2:5]) % 3 == 0 and\
                   join(num[1:4]) % 2 == 0:


                           kount += join(num)


        print(kount)

        print(time.time() - tt, " secs")
if __name__ == '__main__':
        main()
# Problem 44.
#----------------------------------------------------
#!/usr/bin/env python
'''Find the smallest pair of pentagonal numbers whose
 sum and difference is pentagonal.'''

import sys
sys.path.append("../")
from rogutil import *
import time
tt = time.time()

def main():
        lst = []
        #.....generate a list of pent. numbers------
        for i in range(1, 3003, 1):
                pent = (i * ((3 * i) - 1)) / 2
                lst.append(pent)
        #---convert to set for speed of reference---
        lst2 = set(lst)
        #--------------------------------------------
        for i in range(0, 3000, 1):
                for j in range(1, 3000, 1):
                        sum1 = lst[j] + lst[i]
                        if sum1 in lst2:
                                sum2 = lst[j] - lst[i]
                                if sum2 in lst2:
                                        print(lst[j] - lst[i],i,j)
                                        print(time.time() - tt," secs.")





if __name__ == '__main__':
        main()
# Problem 45.

'''Triangle, pentagonal, and hexagonal numbers are
 generated by the following formulae:
Triangle           Tn=n(n+1)/2           1, 3, 6, 10, 15, ...
Pentagonal           Pn=n(3n-1)/2        1, 5, 12, 22, 35, ...
Hexagonal           Hn=n(2n-1)           1, 6, 15, 28, 45, ...

It can be verified that T285 = P165 = H143 = 40755.

Find the next triangle number that is also
pentagonal and hexagonal.'''

import time
tt = time.time()

tri_lst = []
pent_set = set()
hex_set = set()

#--Two sets for reference----------
for j in range(2, 100000, 1):
        pent = (j * (3 * j - 1)) / 2
        pent_set.add(pent)

for k in range(2, 100000, 1):
        hex = (k * (2 * k - 1))
        hex_set.add(hex)
#----------------------------------

for i in range(287,300000,1):
        tri = (i * (i + 1)) / 2
        if tri in pent_set and tri in hex_set:
                print(tri)
                print(time.time() - tt," secs")

print("Done")

Comments | Gallery