Square root digital expansion : Problem 80 : Project Euler : Pyhton Code

Square root digital expansion : Problem 80 : Project Euler

It is well known that if the square root of a natural number is not an integer, then it is irrational. The decimal expansion of such square roots is infinite without any repeating pattern at all. The square root of two is 1.41421356237309504880..., and the digital sum of the first one hundred decimal digits is 475. For the first one hundred natural numbers, find the total of the digital sums of the first one hundred decimal digits for all the irrational square roots.

One of the easy way to solve the problem is to use High Precision Python library for Floating point Numbers

>>> from bigfloat import *
>>> sqrt(2, precision(100))  # compute sqrt(2) with 100 bits of precision
BigFloat.exact('1.4142135623730950488016887242092', precision=100)

Nonetheless you have to download the bigfloat package. This method does not give the flavor of maths!
I have rather used the decimal module which provides support for decimal floating point arithmetic and have used Newton - Raphson method to calculate the square root correct to 10**(110) places!

import math

from decimal import *

def sqRootDigitalExpansion():

    def f(x,n):

        getcontext().prec = 130

        return Decimal(x**2-n)

    def fderivative(x):

        getcontext().prec = 130

        return Decimal(2*x)

    n = 1

    totalSum = 0

    while n < 100:    

        if n == 1 or n == 4 or n == 9 or n == 16 or n == 25 or n == 36 or n == 49 or n == 64 or n == 81:

            n = n + 1

            continue

        a = 1

        b = -1

        xn = 0

        error = 0.0;

        x0=a

        while True:

           getcontext().prec = 130   

           (xn)=(x0)-((f(x0,n)/fderivative(x0)))

           (error)=(math.fabs(xn-x0))

           x0=xn

           if error < 10**(-110):

               break

        mylist = str(xn).split(".")

        sumR = 0

        for i in range(len(mylist[0])):   

            sumR = sumR + int(mylist[0][i])

        for i in range (0,100-len(mylist[0])):

            sumR = sumR + int(mylist[1][i])

        print ("Digital Sum of the root (100 digits) ",sumR," for the number ",n)

        totalSum = totalSum + sumR

        n = n + 1

    print(totalSum)

sqRootDigitalExpansion()

Largest exponential : Problem 99 : Project Euler

Largest exponential : Problem 99 : Project Euler

Comparing two numbers written in index form like 2¹¹ and 3⁷ is not difficult, as any calculator would confirm that 2¹¹ = 2048 < 3⁷ = 2187.
However, confirming that 632382⁵¹⁸⁰⁶¹ > 519432⁵²⁵⁸⁰⁶ would be much more difficult, as both numbers contain over three million digits.
Using base_exp.txt (right click and 'Save Link/Target As...'), a 22K text file containing one thousand lines with a base/exponent pair on each line, determine which line number has the greatest numerical value.

NOTE: The first two lines in the file represent the numbers in the example given above.

This is on of the easiest problem of Project Euler! Instead of calculating a^x and b^y actually to determine which one is greater, use the fact from analysis that log x is an increasing function. therefore if  a^x > b^y => x*log a > y*log b

Python Code

import math

def largestExponential():

    maxBE = 0.0

    maxLineNumber = 0

    lineNumber = 1

    val = 0.0

    f = open('base_exp.txt','r')

    for line in f:

        t = line[0:len(line)-1]

        mylist = t.split(",")

        val = float(mylist[1])*math.log(float(mylist[0]))

        if maxBE <= val:

            maxBE = val

            maxLineNumber = lineNumber

        lineNumber = lineNumber + 1   

    print("Maximum value at line Number",maxLineNumber)

largestExponential() 

Reciprocal cycles : Problem 26 : Project Euler : Python Code

Reciprocal cycles : Problem 26 : Project Euler

A unit fraction contains 1 in the numerator. The decimal representation of the unit fractions with denominators 2 to 10 are given:

1/2	=	0.5
1/3	=	0.(3)
1/4	=	0.25
1/5	=	0.2
1/6	=	0.1(6)
1/7	=	0.(142857)
1/8	=	0.125
1/9	=	0.(1)
1/10	=	0.1

Where 0.1(6) means 0.166666..., and has a 1-digit recurring cycle. It can be seen that ¹/₇ has a 6-digit recurring cycle.
Find the value of d < 1000 for which ¹/_d contains the longest recurring cycle in its decimal fraction part.

Answer:

Max Length= 985  for Decimal Expansion of 1/ 983 = .001017293997965412004069175991861648016276703967446592065106815869
786368260427263479145473041709053916581892166836215666327568667344
862665310274669379450661241098677517802644964394710071210579857578
840284842319430315361139369277721261444557477110885045778229908443
540183112919633774160732451678535096642929806714140386571719226856
561546286876907426246185147507629704984740590030518819938962360122
075279755849440488301119023397761953204476093591047812817904374364
191251271617497456765005086469989827060020345879959308240081383519
837232960325534079348931841302136317395727365208545269582909460834
181078331637843336724313326551373346897253306205493387589013224821
973550356052899287894201424211597151576805696846388606307222787385
554425228891149542217700915564598168870803662258392675483214649033
570701932858596134282807731434384537131230925737538148524923702950
152594099694811800610376398779247202441505595116988809766022380467
955239064089521871820956256358087487283825025432349949135300

 To solve this problem we have to perform the paper-pencil method of division instead of using inbuilt method of (float) division. Since the divisor if maximum of 3 digits (999) makes the case more easier. Only thing to make note of when to stop the division process, which is best understood upon dividing few examples manually. Try with 1/3, 1/7, 1/8 1/133..... In short a pattern will reappear iff in the process of division by n, let diviList be the collection of of the dividend till the mth step, at the (m+1)th step if the dividend is in diviList, you are done, break!     

Python Code

def reciprocalCycles():
    maxLength = 0
    maxN = 0
    n = 2
    while n < 1000:
        dividend = 1
        divisor = n
        quotient = "."
        diviList = ()
        diviList = diviList + (dividend,)
        while True:
            if dividend < divisor:
                dividend = dividend*10
                if dividend < divisor:
                    dividend = dividend*10
                    quotient = quotient + "0"
                    if dividend < divisor:
                        dividend = dividend*10
                        quotient = quotient + "0"
            if dividend not in diviList:
                diviList = diviList + (dividend,)
            else:
                break
            temp = dividend                   
            dividend = (dividend - (dividend/divisor)*divisor)
            quotient = quotient+str(temp/divisor)   
        if maxLength <= len(quotient):
            maxLength = len(quotient)
            maxN = n   
            q = quotient
        n = n + 1
    print "Max Length=",maxLength," for Decimal Expansion of 1/",maxN,"=",q   
reciprocalCycles()                              

Non-abundant sums : Problem 23 : Project Euler : Python Code

Non-abundant sums : Problem 23 : Project Euler

A perfect number is a number for which the sum of its proper divisors is exactly equal to the number. For example, the sum of the proper divisors of 28 would be 1 + 2 + 4 + 7 + 14 = 28, which means that 28 is a perfect number.
A number n is called deficient if the sum of its proper divisors is less than n and it is called abundant if this sum exceeds n.
As 12 is the smallest abundant number, 1 + 2 + 3 + 4 + 6 = 16, the smallest number that can be written as the sum of two abundant numbers is 24. By mathematical analysis, it can be shown that all integers greater than 28123 can be written as the sum of two abundant numbers. However, this upper limit cannot be reduced any further by analysis even though it is known that the greatest number that cannot be expressed as the sum of two abundant numbers is less than this limit.
Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.

Python Code:

def nonAbundantSums():
    def sumOfDivisors(numb):
        sumD = 0
        if numb == 1:
            return 0
        for d in range(numb/2):
            d = d+1
            if numb%d ==0:
                sumD = sumD + d
        return sumD   
       
    limit = 28123       
    sumNonAbn = 0
    tot = 0
    AbnList = ()
    n = 12
    """ Find all the abundant Numbers"""
    while n <= limit:
        if n < sumOfDivisors(n):
            AbnList = AbnList + (n,)
            tot = tot + 1
        """print n"""   
        n = n+1
    """ A List to mark all the numbers less than limit which can be written as sum of abundant numbers"""
    UniqueAbnList = [0 for i in range(limit+1)]
        
   
    for i in range(tot):
        """ Since the list of abundant numbers is increasing once the limit crosses 15000, the sum will be always > limit """
        if AbnList[i] > 15000:
            break
        for j in range(i,tot):
            if (AbnList[i]+AbnList[j]) <= limit:
                """ Mark the numbers """
                UniqueAbnList[AbnList[i]+AbnList[j]] = 1
            j = j + 1   
        i = i + 1       
    k = 0               
    for i in UniqueAbnList:
        if UniqueAbnList[k] == 0:
            """ Add the unmarked numbers """
            sumNonAbn = sumNonAbn +k
            print k,"Cannot be written as Sum of two Abundant Numbers"
        k = k + 1   
    print sumNonAbn       
nonAbundantSums()                       

Permuted multiples :Problem 52 : Project Euler : Python Code

Permuted multiples :Problem 52 : Project Euler

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.

Python Code

def permutedMultiples():
    x = 1
    while True:
        n1 = str(2*x)
        n2 = str(3*x)
        n3 = str(4*x)
        n4 = str(5*x)
        n5 = str(6*x)
        if len(n1) != len(n2) != len(n3) != len(n4) != len(n5):
            x = x + 1
            continue
        l1 = [0 for i in range(len(n1)) ]
        l2 = [0 for i in range(len(n2)) ]
        l3 = [0 for i in range(len(n3)) ]
        l4 = [0 for i in range(len(n4)) ]
        l5 = [0 for i in range(len(n5)) ]
        for i in range (len(n1)):
            l1[i] = n1[i]
            l2[i] = n2[i]
            l3[i] = n3[i]
            l4[i] = n4[i]
            l5[i] = n5[i]
        l1.sort()
        l2.sort()
        l3.sort()
        l4.sort()
        l5.sort()
        if l1 == l2 == l3 == l4 == l5:
            break
        print "Loop variable",x   
        x = x +1
    print "x= :",x
    print "2x=:",n1
    print "3x=:",n2
    print "4x=:",n3
    print "5x=:",n4
    print "6x=:",n5   
permutedMultiples()           

Pandigital products : Problem 32 : Project Euler : Python Code

Pandigital products : Problem 32 : Project Euler

We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once; for example, the 5-digit number, 15234, is 1 through 5 pandigital.
The product 7254 is unusual, as the identity, 39 × 186 = 7254, containing multiplicand, multiplier, and product is 1 through 9 pandigital.
Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.

HINT: Some products can be obtained in more than one way so be sure to only include it once in your sum.

 

 

First note that if m X n = P, by concatenating m,n and P it will be a 9-digit pandigital number if both in m & n none of the digits are repeated. I have use the function checkOneDigit(numb) to check whether in m or n frequncy of any digit is greater than 1. checkPandigital(numb) simply checks whether a number is n-digit pandigital or not. Next task is to determine the upper limit of m and n. Observe that if m or n is a 5-digit number, after concatenation it will never form a 9-digit pandigital number. Since P will be of atleast 5-digits. So after concatenation the number will consist of 11 digits (even if m is of 1 digit number) Ex. 12345 X m = abcde, after concatenation it results in 12345mabcde, (at-least 11 digits) by Pigeon Hole Principle at least on of the digits 1,2,3,....,9 has to be repeated. Hence Max(m,n) <= 4999, within this range m and n are filtered using checkOneDigit(numb)

Python Code 

  

def pandigitalProducts():

    def checkPandigital(numb):
        flag = True
        strNumber = str(numb)
        length = len(strNumber)
        if '0' in strNumber:
            return False
        nList = [0 for i in range (length)]
        for i in range (length):
            nList[i] = int(strNumber[i])
            if int(strNumber[i]) > length:
                flag = False
        if 0  in nList:
            return False       
        if flag == False:
            return False
        else:
            for i in range (length):
                if nList.count(int(strNumber[i])) > 1 :
                    flag = False
                    break
            return flag
          
    def checkOneDigit(numb):
        flag = True
        strNumber = str(numb)
        length = len(strNumber)
        if '0' in strNumber:
            return False
        nList = [0 for i in range (length)]
        for i in range (length):
            nList[i] = int(strNumber[i])
        for i in range (length):
            if nList.count(int(strNumber[i])) > 1 :
                    flag = False
                    break
        return flag
              
    sumPandigital = 0
    upperLimit = 9999
    n = 1
    pandigitalList = ()
    """ pandigitalList contains the all possible values of m and n """
    while n <= upperLimit:
        if checkOneDigit(n) == True:
            pandigitalList = pandigitalList + (n,)
        n = n+1  
    """print pandigitalList    """
    panProduct = ()
    sumP = 0  
    for d in pandigitalList:
        m = d
        for x in pandigitalList:
            product = 1
            n = x
            product = m*n
            strNumb = ""
            strNumb = strNumb + (str(m)+str(n)+str(product))
            if len(strNumb) == 9:
                if checkPandigital(int(strNumb)) == True:
                    if product not in panProduct:
                        panProduct = panProduct + (product,)
                        sumP = sumP + product
                        print m,"X",n,"=",product,"Partial Sum--------------",sumP  
    print "Required Sum is:",sumP  
pandigitalProducts()        

Pandigital prime : Problem 41 : Project Euler : Python Code

Pandigital prime : Problem 41 : Project Euler

We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once. For example, 2143 is a 4-digit pandigital and is also prime.
What is the largest n-digit pandigital prime that exists?

 Given that 2143 is a 4-digit pandigital prime. A 5-digit or 6-digit pandigital number cannot be prime because sum of there digits is
1+2+3+4+5 = 15 which is divisible by 3 and also
1+2+3+4+5+6 = 21 which is also divisible by 3 hence the numbers will be divisible by 3 and cannot be prime so we can set the lower limit to be 654321 and upper limit to be 7654321, since a 8-digit or 9-digit pandigital number cannot be a prime by similar arguments.

Python Code

def PandigitalPrime():
    upperLimit = 7654321
    def checkPrime(numb):
        prime = True
        if numb == 1:
            return False
        else:   
            for i in range(int(numb/2)):
                i = i+2
                if numb%i == 0:
                    prime = False
                    break
            if numb == 2:
                return True
            else:           
                return prime
               
    def checkPandigital(numb):
        flag = True
        strNumber = str(numb)
        length = len(strNumber)
        nList = [0 for i in range (length)]
        for i in range (length):
            nList[i] = int(strNumber[i])
            if int(strNumber[i]) > length:
                flag = False
        if 0  in nList:
            return False        
        if flag == False:
            return False
        else:
            for i in range (length):
                if nList.count(int(strNumber[i])) > 1 :
                    flag = False
                    break
            return flag                        
                   
    n =  654321
    largestPandigitalPrime = 0
    while n <= upperLimit:
        if checkPandigital(n) == False:
            n = n + 2
            continue
        if checkPrime(n) == True:
            largestPandigitalPrime = n
            print len(str(n)),"th digit pandigital prime:",n
        n = n + 2
    print "largest Pandigital Prime is:",largestPandigitalPrime   
PandigitalPrime()