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