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()                       

Coded triangle numbers : Problem 42 : Project Euler : JAVA Code

Coded triangle numbers : Problem 42 : Project Euler

The n^th term of the sequence of triangle numbers is given by, t_n = ½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 = t₁₀. 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?

Note that the file words.txt has been modified, an extra ',' is added at the end of the file for easy extraction of the names. Download it and then edit it to add a ',' after "YOUTH" (the last word of the file)

JAVA Code

import java.io.*;
import java.util.*;
public class CodedTriangleNumbers {
    public static void main(String[] args) throws IOException {
        String fileName = "words.txt";
        String allNames = "";
       
        FileReader fr = new FileReader(fileName);   
        BufferedReader br = new BufferedReader(fr);
        allNames=br.readLine();
        br.close();
        fr.close();
       
        NameExtractionScores nms = new NameExtractionScores();
        System.out.println("Total number of names: "+nms.namesCount(allNames));
        System.out.println("LIST of the names:");
        nms.namesExtraction(allNames);
        System.out.println("Number of triangle words:"+nms.namesTraingular());
        }
    }
class NameExtractionScores {
    public int namesCount(String allNames) {
        for (int i = 0; i < allNames.length(); i++) {
            if (allNames.charAt(i) == ',')
                nameCount++;
            }
        return nameCount;   
        }
   
    public void namesExtraction (String allNames) {
        names = new String[nameCount];
        String temp = "";
        int k = 0;
        for (int i = 0; i < allNames.length(); i++) {
            temp = "";
           
            while ( allNames.charAt(i) != ',' ) {
                if (allNames.charAt(i) != '"')
                    temp += allNames.charAt(i++);
                else   
                    i++;
                }
               
            names[k] = "";
            names[k] +=temp;
            System.out.println(names[k++]);   
            }
        }   
    public int namesTraingular() {
        for (int i = 0; i < nameCount; i++) {
            int cSum = 0;
            boolean tFlag = false;
            for (int j = 0; j < names[i].length(); j++)
                cSum += (names[i].charAt(j)-64);
            int n = 1;
            while (n <= cSum) {
                if (n*(n+1) == 2*cSum) {
                    tFlag = true;
                    break;
                    }
                n++;   
                }   
            if (tFlag == true)
                nameTraingularTotal++;   
            }
        return nameTraingularTotal;   
        }   
    private int nameTraingularTotal = 0;   
    private int nameCount = 0;
    private String[] names;
    }       

Digit factorial chains : Problem 74 : Project Euler Python Code

Digit factorial chains : Problem 74 : Project Euler Python Code

The number 145 is well known for the property that the sum of the factorial of its digits is equal to 145:

1! + 4! + 5! = 1 + 24 + 120 = 145

Perhaps less well known is 169, in that it produces the longest chain of numbers that link back to 169; it turns out that there are only three such loops that exist:

169 → 363601 → 1454 → 169
871 → 45361 → 871
872 → 45362 → 872

It is not difficult to prove that EVERY starting number will eventually get stuck in a loop. For example,

69 → 363600 → 1454 → 169 → 363601 (→ 1454)
78 → 45360 → 871 → 45361 (→ 871)
540 → 145 (→ 145)

Starting with 69 produces a chain of five non-repeating terms, but the longest non-repeating chain with a starting number below one million is sixty terms.
How many chains, with a starting number below one million, contain exactly sixty non-repeating terms?

Python Code 

 

def digitFactorialChains():
    def fact(digit):
        l=1
        for i in range(digit):
            l=l*digit
            digit=digit-1
        return l
    number = 1
    digitfactsum = 0
    counter = 0
    while number < 10**6:
            chain = ()
            chain = chain + (number,)
        strnumber = str(number) 
        length = 1
            while True:
                digitfactsum = 0
            for i in range(len(strnumber)):
                    digitfactsum = digitfactsum + fact(int(strnumber[i]))
                if digitfactsum in chain:
                    break
                else:
                    chain = chain + (digitfactsum,)  
                    length = length + 1
                    strnumber = str(digitfactsum)
        """print chain,length  prints the sequnce with length"""         
        if length == 60:
                 counter = counter + 1  
             """You wont get bored if you print the loop iteration!"""  
             print number       
             number = number + 1
    print "chains, with a starting number below one million, contain exactly sixty non-repeating terms:",counter
digitFactorialChains() 

 

Bouncy numbers : Problem 112 : Project Euler : Python Code

Bouncy numbers : Problem 112 : Project Euler

Working from left-to-right if no digit is exceeded by the digit to its left it is called an increasing number; for example, 134468.

Similarly if no digit is exceeded by the digit to its right it is called a decreasing number; for example, 66420.

We shall call a positive integer that is neither increasing nor decreasing a "bouncy" number; for example, 155349.

Clearly there cannot be any bouncy numbers below one-hundred, but just over half of the numbers below one-thousand (525) are bouncy. In fact, the least number for which the proportion of bouncy numbers first reaches 50% is 538.
Surprisingly, bouncy numbers become more and more common and by the time we reach 21780 the proportion of bouncy numbers is equal to 90%.
Find the least number for which the proportion of bouncy numbers is exactly 99%.

Python Code

def bouncyNumbers():
    def increasing(numb):
        iflag = True
        strNumb = str(numb)
        for i in range(len(strNumb)-1):
            if int(strNumb[i]) > int(strNumb[i+1]):
                iflag = False
                break
        return iflag
    def decreasing(numb):
        dflag = True
        strNumb = str(numb)
        for i in range(len(strNumb)-1):
            if int(strNumb[i]) < int(strNumb[i+1]):
                dflag = False
                break
        return dflag
    bouncyCount = 0
    percentagebCount = 0.0
    n = 99
    while int(percentagebCount) != 99:   
        n = n + 1
        if increasing(n) == False and decreasing(n) == False:
            bouncyCount = bouncyCount + 1
        percentagebCount = (bouncyCount*100.0)/n
        print percentagebCount,n
    print "least number for which the proportion of bouncy numbers is exactly 99% is :",n   
bouncyNumbers()               

Names scores : Problem 22 : Project Euler JAVA Code

Names scores : Problem 22 : Project Euler

Using names.txt (right click and 'Save Link/Target As...'), a 46K text file containing over five-thousand first names, begin by sorting it into alphabetical order. Then working out the alphabetical value for each name, multiply this value by its alphabetical position in the list to obtain a name score.

For example, when the list is sorted into alphabetical order, COLIN, which is worth 3 + 15 + 12 + 9 + 14 = 53, is the 938th name in the list. So, COLIN would obtain a score of 938 × 53 = 49714.

What is the total of all the name scores in the file?

 JAVA CODE

import java.io.*;
import java.util.*;
public class NamesScore {
    public static void main(String[] args) throws IOException {
        String fileName = "names.txt";
        String allNames = "";
       
        FileReader fr = new FileReader(fileName);   
        BufferedReader br = new BufferedReader(fr);
        allNames=br.readLine();
        br.close();
        fr.close();
       
        NameExtractionScores nms = new NameExtractionScores();
        System.out.println("Total number of names: "+nms.namesCount(allNames));
        System.out.println("LIST of the names (unsorted):");
        nms.namesExtraction(allNames);
        System.out.println("Score is: "+nms.namesScore());
        }
    }
class NameExtractionScores {
    public int namesCount(String allNames) {
        for (int i = 0; i < allNames.length(); i++) {
            if (allNames.charAt(i) == ',')
                nameCount++;
            }
        return nameCount;   
        }
   
    public void namesExtraction (String allNames) {
        names = new String[nameCount];
        String temp = "";
        int k = 0;
        for (int i = 0; i < allNames.length(); i++) {
            temp = "";
           
            while ( allNames.charAt(i) != ',' ) {
                if (allNames.charAt(i) != '"')
                    temp += allNames.charAt(i++);
                else   
                    i++;
                }
               
            names[k] = "";
            names[k] +=temp;
            System.out.println(names[k++]);   
            }
        }   
    public int namesScore() {
        Arrays.sort(names);
        for (int i = 0; i < nameCount; i++) {
            int pSum = 0;
            System.out.println(names[i]);   
            for (int j = 0; j < names[i].length(); j++)
                pSum += (names[i].charAt(j)-64);
            nameScoreTotal += (pSum*(i+1));   
            }
        return nameScoreTotal;   
        }    
    private int nameScoreTotal = 0;   
    private int nameCount = 0;
    private String[] names;
    }       

Square digit chains : Problem 92 : Project Euler

Square digit chains : Problem 92 : Project Euler

A number chain is created by continuously adding the square of the digits in a number to form a new number until it has been seen before.
For example,

44 → 32 → 13 → 10 → 1 → 1
85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89

Therefore any chain that arrives at 1 or 89 will become stuck in an endless loop. What is most amazing is that EVERY starting number will eventually arrive at 1 or 89.
How many starting numbers below ten million will arrive at 89?

Python Code

def squareDigitChains():
    squareDigitCount = 0
    for i in range(1,10000000):
        strnumber = ""
        strnumber = str(i)
        sqnumber = 0
        temp = strnumber
        while True:
            sqnumber = 0
            for j in range(len(strnumber)):
                sqnumber = sqnumber + int(strnumber[j])**2
            strnumber = str(sqnumber)   
            if sqnumber == 1 or sqnumber == 89:
                break
        if sqnumber == 89:
            print temp
            squareDigitCount = squareDigitCount + 1
    print "Required Counter is:",squareDigitCount               
squareDigitChains()

Digit fifth powers :Problem 30 : Project Euler

Digit fifth powers :Problem 30 : Project Euler

Surprisingly there are only three numbers that can be written as the sum of fourth powers of their digits:

1634 = 1⁴ + 6⁴ + 3⁴ + 4⁴
8208 = 8⁴ + 2⁴ + 0⁴ + 8⁴
9474 = 9⁴ + 4⁴ + 7⁴ + 4⁴

As 1 = 1⁴ is not a sum it is not included.

The sum of these numbers is 1634 + 8208 + 9474 = 19316.
Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.

To get hold of the upper limit see

Digit factorials : Problem 34 : Project Euler

Python Code

 def digitFifthPowers():
    number = 10
    sumNumbers = 0
    digitfifthsum = 0
    while number < 7*9**5+1:
        strnumber = str(number)  
        digitfifthsum = 0
        for i in range(len(strnumber)):
            digitfifthsum = digitfifthsum + int(strnumber[i])**5
            if digitfifthsum > number:
                break
        if digitfifthsum == number:
            sumNumbers = sumNumbers + number
            print number,"Sum of the digits raised 5 is equal to the number itself"
        number = number + 1
    print "Required Sum is",sumNumbers          
digitFifthPowers()      

Digit factorials : Problem 34 : Project Euler

Digit factorials : Problem 34 Project Euler

145 is a curious number, as 1! + 4! + 5! = 1 + 24 + 120 = 145.
Find the sum of all numbers which are equal to the sum of the factorial of their digits.

Note: as 1! = 1 and 2! = 2 are not sums they are not included.

To find the upper limit for this problem observe that for a n-digit number the maximum possible  Digit Factorial Sum is 9!*n

For n = 7, Max. Digit Factorial Sum is 9!*7 =2,540,160 which is a 7 digit number

For n = 8, Max. Digit Factorial Sum is 9!*8 =2,903,040 which is a 7 digit number. Hence a the Digit Factorial Sum can never be equal to a 8 digit number! 

Python Code

def digitFactorials():
    def fact(digit):
        l=1
        for i in range(digit):
            l=l*digit
            digit=digit-1
        return l
    number = 10
    sumNumbers = 0
    digitfactsum = 0
    while number < 2540161:
        strnumber = str(number)   
        digitfactsum = 0
        for i in range(len(strnumber)):
            digitfactsum = digitfactsum + fact(int(strnumber[i]))
            if digitfactsum > number:
                break
        if digitfactsum == number:
            sumNumbers = sumNumbers + number
            print number,"Sum of the digits factorials is equal to the number itself"
        number = number + 1
    print "Required Sum is",sumNumbers           
digitFactorials()       

Distinct powers : Problem 29 : Project Euler : Python Code

Distinct powers : Problem 29 : Project Euler

Consider all integer combinations of a^b for 2 ≤ a ≤ 5 and 2 ≤ b ≤ 5:

2²=4, 2³=8, 2⁴=16, 2⁵=32
3²=9, 3³=27, 3⁴=81, 3⁵=243
4²=16, 4³=64, 4⁴=256, 4⁵=1024
5²=25, 5³=125, 5⁴=625, 5⁵=3125

If they are then placed in numerical order, with any repeats removed, we get the following sequence of 15 distinct terms:

4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125

How many distinct terms are in the sequence generated by a^b for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100

 Python Code

def distinctPowers():
    powerList = ()
    for a in range(2,101):
        for b in range(2,101):
            temp = a**b;
            if temp  in powerList:
                continue
            else:
                powerList = powerList + (temp,)
    print len(powerList)               
distinctPowers()       

Number letter counts : Problem 17 : JAVA CODE

Number letter counts : Problem 17 : Project Euler

 

If the numbers 1 to 5 are written out in words: one, two, three, four, five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.
If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used?

NOTE: Do not count spaces or hyphens. For example, 342 (three hundred and forty-two) contains 23 letters and 115 (one hundred and fifteen) contains 20 letters. The use of "and" when writing out numbers is in compliance with British usage.

JAVA CODE

import java.util.*;
public class NumberLetterCount {
    public static void main(String[] args) {
        ToWords numbObject = new ToWords();
        for(int i = 1; i <=1000; i++) {
            numbObject.toWord(i);
            }
        System.out.println("Letters used:"+numbObject.totalLetterCount());   
        }
    }
class ToWords {
    public void toWord(int numb) {
        this.number = numb;
        this.word = "";
        String temp = "";
        temp +=number;
        switch(temp.length()) {
            case 1:
                word = oneTwoDigit[number-1];
                           
            break;
           
            case 2:
                if ( number <= 20)
                    word = oneTwoDigit[number-1];
                   
                else {
                    if ( (temp.charAt(1)-48) == 0 )
                         word += tens[(temp.charAt(0)-48)-1];
                       
                    else    
                         word += tens[(temp.charAt(0)-48)-1]+ " "+oneTwoDigit[(temp.charAt(1)-48)-1];
                       
                    }
            break;
           
            case 3:
                if ( (temp.charAt(1)-48) == 0 && (temp.charAt(2)-48) == 0)
                    word += hundreds[(temp.charAt(0)-48)-1];
                   
                else if ( (temp.charAt(2)-48) == 0 )    
                    word += hundreds[(temp.charAt(0)-48)-1]+" and "+tens[(temp.charAt(1)-48)-1];
                   
                else {
                    if ( (temp.charAt(1)-48) == 0 )
                        word += hundreds[(temp.charAt(0)-48)-1]+" and "+oneTwoDigit[(temp.charAt(2)-48)-1];
                       
                    else   
                        if ( (temp.charAt(1)-48) == 1 )
                             word += hundreds[(temp.charAt(0)-48)-1]+" and "+oneTwoDigit[(temp.charAt(2)-48)-1+10];
                        else   
                            word += hundreds[(temp.charAt(0)-48)-1]+" and "+tens[(temp.charAt(1)-48)-1]+"-"+oneTwoDigit[(temp.charAt(2)-48)-1];   
                       
                    }
            break;
           
            case 4:
                word = "One Thousand";
               
            break;
            }   
        System.out.println(number+" in words: "+word);
        lettersCount(word);   
        }   
    private void lettersCount(String word) {   
        for( int i = 0; i < word.length(); i++ )
            if (word.charAt(i) == ' ' || word.charAt(i) == '-')
                continue;
            else
                letterCount +=1;   
        }
    public int totalLetterCount() {
        return letterCount;
        }   
    private String[] oneTwoDigit =  {"One","Two","Three","Four","Five","Six","Seven",
                    "Eight","Nine","Ten","Eleven","Twelve",
                    "Thirteen","Fourteen","Fifteen","Sixteen",
                    "Seventeen","Eighteen","Nineteen","Twenty"};   
                   
    private String[] tens =     {"Ten","Twenty","Thirty","Forty","Fifty","Sixty",
                     "Seventy","Eighty","Ninety"};
               
    private String[] hundreds =     {"One Hundred","Two Hundred","Three Hundred","Four Hundred","Five Hundred",
                         "Six Hundred","Seven Hundred","Eight Hundred","Nine Hundred"};               
    private int number;
    private int letterCount = 0;
    private String word;   
    }           

Goldbach's other conjecture : Problem 46 Pyhton Code

Goldbach's other conjecture : 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²
15 = 7 + 2×2²
21 = 3 + 2×3²
25 = 7 + 2×3²
27 = 19 + 2×2²
33 = 31 + 2×1²

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?

Problem Source :  Euler Project

Python Code

import math
def goldbachConjecture():
    found = False
    def checkPrime(numb):
        prime = True
        if numb == 1:
            return False
        for i in range(int(math.sqrt(numb))):
            i = i+2
            if numb%i == 0:
                prime = False
                break
        if numb == 2:
            return True
        else:           
            return prime
    def nextOddCompositeNumber(numb):
        numb = numb+1
        while checkPrime(numb) == True or numb %2 == 0:
            numb = numb+1
        return numb;           
    numb = 9    
    while found == False:
        k = 1
        goldtrue = False
        while numb-2*k**2 > 0 :
            if checkPrime(numb-2*k**2) == True:
                goldtrue = True
                break
            k = k+1   
        if goldtrue == True:
            found = False
            numb = nextOddCompositeNumber(numb)
        else:
            found = True
            print "smallest odd composite that cannot be written as the sum of a prime and twice a square",numb
goldbachConjecture()           

Insertion Sort : Python Code & Linked List implementation

Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. Each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.
Sorting is typically done in-place, by iterating up the array, growing the sorted list behind it. At each array-position, it checks the value there against the largest value in the sorted list (which happens to be next to it, in the previous array-position checked). If larger, it leaves the element in place and moves to the next. If smaller, it finds the correct position within the sorted list, shifts all the larger values up to make a space, and inserts into that correct position.

Python Code

import random
def InsertionSort():
    N = input("Enter the number of elements in the list:")
    unsortedList = [0 for i in range(N)]
    for i in range(N):
        """ user input can be taken here"""
        unsortedList[i] = int(random.random()*N)
        i = i + 1
    print 'Unsorted list is:',unsortedList
    i = 0
    sortedList = [0 for i in range(N)]
    sortedList[0] = unsortedList[0]
    """ counter holds the number of elements inserted in the sorted list"""
    counter = 1
    for i in range (N-1):
        i = i + 1
        temp = counter
        while unsortedList[i] < sortedList[counter-1] and counter > 0:
            sortedList[counter] = sortedList[counter-1]
            counter = counter - 1
        sortedList[counter] = unsortedList[i]
        temp = temp+1
        counter = temp
    print 'Sorted list is:',sortedList           
InsertionSort()   

Binary Tree Traversal : C Code

 

Binary Tree Traversals inorder,preorder and postorder.  

#include<stdlib.h>
#include<stdio.h>
struct binaryTree {
   int key;
   struct binaryTree *right, *left;
};

typedef struct binaryTree node;

void insert(node **tree, int val);
void preorderTraversal(node *root);
void inorderTraversal(node *root);
void postorderTraversal(node *root);

int main() {
   node *root;
   int i,val,search;
   root = NULL;
   while(1) {
      printf("\n Enter the value (-1 to exit):");
      scanf("%d",&val);   
      if( val == -1)
          break;
      insert(&root, val);
   }
   printf("\n Pre-order Traversal:");
   preorderTraversal(root);
   printf("\n");
   printf("\n Inorder Traversal:");
   inorderTraversal(root);
   printf("\n");
   printf("\n Postorder Traversal:");
   postorderTraversal(root);
   printf("\n");
   return 0;
}
void postorderTraversal(node *root) {
    if (root != NULL) {
            postorderTraversal(root->left);
            postorderTraversal(root->right);
              printf("%d ",root->key);
                }
    }
void inorderTraversal(node *root) {
    if (root != NULL) {
            inorderTraversal(root->left);
              printf("%d ",root->key);
                inorderTraversal(root->right);
               }
    }
void preorderTraversal(node *root) {
    if (root != NULL)
        printf("%d ",root->key);
    if (root->left != NULL)
        preorderTraversal(root->left);   
    if (root->right != NULL)
        preorderTraversal(root->right);       
    }
void insert(node **tree, int val) {
   if((*tree) == NULL) {
      *tree = (node *)malloc(sizeof(node));
      (*tree)->key = val;
      (*tree)->right=(*tree)->left=NULL;
      return;
   }
   if(val < (*tree)->key)
      insert(&(*tree)->left, val);
   else if(val > (*tree)->key)
      insert(&(*tree)->right, val);
    }

Binary Search Tree (BST) : Finding Leaves : C Code

 Binary Search Tree (BST) : Finding Leaves : C Code

The following C code prints all the leaves nodes of a Binary Search Tree. A leaf-node is a node which has not left or right child. The code first scans the root node and looks whether it has a left and right child or not. If the condition is satisfied, it  is a leave node or else we recursively examine the left and right child.

#include<stdlib.h>
#include<stdio.h>
struct binaryTree {
   int key;
   struct binaryTree *right, *left;
};

typedef struct binaryTree node;

void insert(node **tree, int val);
void printLeaves(node *root);

int main() {
   node *root;
   int i,val,search;
   root = NULL;
   while(1) {
      printf("\n Enter the value (-1 to exit):");
      scanf("%d",&val);   
      if( val == -1)
          break;
      insert(&root, val);
   }
  
   printLeaves(root);
   printf("\n");
   
   return 0;
}
void printLeaves(node *root) {
    if (root->right == NULL && root->left == NULL) {
        printf("\n Leaf Node: %d",root->key);
        return;
        }
    if(root->right != NULL)    
        printLeaves(root->right);
    if(root->left != NULL)   
    printLeaves(root->left);
    }
void insert(node **tree, int val) {
   if((*tree) == NULL) {
      *tree = (node *)malloc(sizeof(node));
      (*tree)->key = val;
      (*tree)->right=(*tree)->left=NULL;
      return;
   }
   if(val < (*tree)->key)
      insert(&(*tree)->left, val);
   else if(val > (*tree)->key)
      insert(&(*tree)->right, val);
    }