Project Euler

# Problem 46.
'''It was proposed by Christian Goldbach that every
odd composite number can be written as the
 sum of a prime and twice a square.

9 = 7 + 2×1^2
15 = 7 + 2×2^2
21 = 3 + 2×3^2
25 = 7 + 2×3^2
27 = 19 + 2×2^2
33 = 31 + 2×1^2

It turns out that the conjecture was false.

What is the smallest odd composite that cannot
 be written as the sum of a prime and twice a square?'''

from rogutil import *

lst = []

for i in range(3, 3000, 1):
        if not iseven(i) and not isprime(i):
                lst.append(i)
                print(lst)
print("Done!")
# Problem 47.
'''The first two consecutive numbers to have two distinct prime factors are:

14 = 2 × 7
15 = 3 × 5

The first three consecutive numbers to have three distinct prime factors are:

644 = 2² × 7 × 23
645 = 3 × 5 × 43
646 = 2 × 17 × 19.

Find the first four consecutive integers to have four distinct primes factors.
 What is the first of these numbers?'''

from math import sqrt
import math
import sys
sys.path.append("../")
from rogutil import *
import time
tt = time.time()
def main():
        pass
        chk = 0
        FourFours = [4,4,4,4]
        sett = set()
        lenSett = [0,0,0,0]
        z = 0
        trinum = 200
        prims = gen_x(7000, gen_primes)     # prime number genny
        prim = prims[z]    # For incrementing the Prime Number
        half = (trinum / prim) +1

#-------------------------------------------
        print("starting")
        while trinum < 150000:
                if trinum % prim == 0:
                        half = (trinum/prim) + 1
                        sett.add(prim)
                        z += 1
                        prim = prims[z]
                else:
                        z += 1
                        prim = prims[z]

                if prim > half:
                        z = 0
                        prim = prims[z]
                        trinum += 1
                        chk = trinum

                        lenSett.append(len(sett))
                        del lenSett[0]   #--keep a constant len of 4-----
                        sett = set()
                if lenSett == FourFours:
                        print("yes", lenSett, chk-4)
                        print("time: ", time.time() - tt)
                        exit()
                continue

        print(lenSett, sett)






if __name__ == '__main__':
        main()
        print(time.time() - tt," secs")
#Problem48
'''The series, 1^1 + 2^2 + 3^3 + ... + 10^10 = 10405071317.

Find the last ten digits of the series,
1^1 + 2^2 + 3^3 + ... + 1000^1000.'''


total = 0
j = 1
for i in range(1,1001):
        c = i**j
        total += c
        j += 1

total = str(total)

print(total[-10:])
# Problem 49.
'''The arithmetic sequence, 1487, 4817, 8147, in which each
of the terms increases by 3330, is unusual in two ways:
(i) each of the three terms are prime, and, (ii) each of the
4-digit numbers are permutations of one another.

There are no arithmetic sequences made up of three 1-, 2-, or 3-digit primes,
 exhibiting this property, but there is one other 4-digit increasing sequence.

What 12-digit number do you form by concatenating the three terms
in this sequence?'''

#!/usr/bin/env python
import sys
sys.path.append("../")
from rogutil import *
from itertools import product
from itertools import permutations
import math
temp_list = []
perm_lst = []
diff_list = []

def main():
        pass


#------------------------------------------------------------------------
        def permutate(seq):
                """permutate a sequence and return a list of
                the permutations"""
                if not seq:
                        return [seq] # is an empty sequence
                else:
                        temp = []
                        for k in range(len(seq)):
                                part = seq[:k] + seq[k+1:]
                                for m in permutate(part):
                                        temp.append(seq[k:k+1] + m)
                        return temp



#--main--------------------------------------------------------------------

        temp_list = []
   #---put the number in a list (temp_list)---
        for i in range(9999,1000,-1):
                temp_list.append(str(i))

#---------------------------------------------

        #--now permutate it----------------------
                for j in range(0,len(temp_list)):
                        m = str(temp_list[j])
                        k = permutate(m)
                        temp_list = []

#----------------------------------------------

#---check for primes in the permutation---
                k_prime_list = set()
                for i in range(0,24):
                        tmp = k[i]
                        if isprime(tmp):
                                k_prime_list.add(tmp)
                k_prime_list = list(k_prime_list)
                k_prime_list = sorted(k_prime_list)
                if len(k_prime_list) == 0:
                        continue
#---------------------------------------------

#--we now need a selection of 3 primes-----

                if len(k_prime_list) >= 3:
                   for p in permutations(k_prime_list, 3):
                           if p[0] < p[-1]:
                                   i = p[0]
                                   j = p[1]
                                   k = p[2]

                           diff = abs(int(i) - int(j))
                           diff1 = abs(int(j) - int(k))
                           if diff == diff1:

                                   print('wait!!!!')
                                   print(i, j, k)
                                   exit()

                           else:
                                   continue


        print("done ")




if __name__ == '__main__':
        main()
#Problem50
'''The prime 41, can be written as the sum of
six consecutive primes: 41 = 2 + 3 + 5 + 7 + 11 + 13

This is the longest sum of consecutive primes that
adds to a prime below one-hundred.

The longest sum of consecutive primes below one-thousand
that adds to a prime, contains 21 terms, and is equal to 953.

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





from rogutil import *

total = 0
count = 0
z = 80
prims = gen_x(70000, gen_primes)     # prime number genny
prim = prims[z]# For incrementing primes

lst = set()
for aa in range(100):
        for i in range(aa,600):
                count+= 1
                prim = prims[z]
                total += prim
                z += 1
                if isprime(total) and total < 1000000:
                        lst.add(total)


print(max(lst))
# Problem 51
# Brute force, mathematical solution is beyond me!
'''By replacing the 1st digit of the 2-digit number *3, it turns out that six of the
nine possible values:
13, 23, 43, 53, 73, and 83, are all prime.

By replacing the 3rd and 4th digits of 56**3 with the same digit, this 5-digit number is the
 first example having seven primes among the ten generated numbers, yielding the family: 56003, 56113,
 56333, 56443, 56663, 56773, and 56993. Consequently 56003, being the first member of this family, is
 the smallest prime with this property.

Find the smallest prime which, by replacing part of the number (not necessarily adjacent digits)
with the same digit, is part of an eight prime value family.
'''
import itertools
import time

num = 100000
num = str(num)
indices = []
lst = []
index1 = 0
index2 = 0
temp_store = []
count = 0

# primes.txt, primes from 100000 to 99999
prime_list = set([int(x.strip()) for x in open("primes.txt").readlines()])

# list of required indices required by list 'combo'
for i in range(0, len(num)):
        indices.append(i)
print(indices)

# num to list of strings
list_num = list(str(num))

# combinations of indices
combo = list(itertools.combinations(list(indices), 3))
print('combo ', combo)

t = time.time()

# modify candidates
while count < 8:
        for x in combo:
                for y in range(0, 10):
                        y = str(y)
                        list_num[x[0]] = y
                        list_num[x[1]] = y
                        list_num[x[2]] = y
                        # flatten from strings to int
                        list_num = int("".join(list_num))
                        lst.append(list_num)
                        # reconstitute num for modifying
                        list_num = list(str(num))
                # check if quantity of primes == 8
                for x in lst:
                        if x in prime_list:
                                count += 1

                                if count == 8:
                                        print(lst[1])
                                        print(time.time() - t)
                                        exit()
                lst = []
                #print(count)
                count = 0
        num = int(num)
        num += 1
        num = str(num)
# problem 52
'''

It can be seen that the number, 125874, and its double, 251748,
contain exactly the same digits, but in a different order.

Find the smallest positive integer, x,
such that 2x, 3x, 4x, 5x, and 6x, contain the same digits.
'''

def main():
    for x in range(1, 10000000):
        ans = x
        items = [sorted(list(str(x * i))) for i in range(2, 7)]
        double, triple, quad, penta, hexa = items
        x = sorted(list(str(x)))

        if x == double == triple == quad \
             == penta == hexa:
            print(ans)
            break
    exit()

if __name__ == '__main__':
    main()
# Problem 53

import sys
import math
sys.path.append("../")


def main():

    f = math.factorial
    n = 9
    r = 2
    acc = 0

    def nCr(n, r):
        f = math.factorial
        return f(n) / f(r) / f(n - r)

    for x in range(100, 1, -1):
        for y in range(1, 99):
            if x >= y:
                ans = nCr(x, y)
                if ans > 1000000:
                    acc += 1

    print(acc)



if __name__ == '__main__':
    main()

Comments | Gallery