Python,C,C++ and JAVA programs for CBSE, ISC, B.Tech and I.T Computer Science and MCA students

The Programming Project: 2014

Saturday, November 22, 2014

ISC Computer Science Practical 2011 Number to Words

 ISC Computer Science Practical 2011

Write a program to input a natural number less than 1000 and display it in words.
Test your program on the sample data and some random data.
Sample input and output of the program.Input: 29
Output: TWENTY NINE
Input: 17001
Output: OUT OF RANGE
Input: 119
Output: ONE HUNDRED AND NINETEEN
Input: 500
Output: FIVE HUNDRED 


import java.util.*;
public class NumberWords {
    public static void main(String[] args) {
        ToWords numbObject = new ToWords();
        Scanner in = new Scanner(System.in);
        while (true) {
            System.out.println("Input:");
            int i = in.nextInt();
            if (i >= 1000) {
                System.out.println("Output: OUT OF RANGE");
                continue;
                }
            numbObject.toWord(i);
            System.out.println("Want to input another number? Y/N:");
            String c = in.next();
            if(c.equals("y") || c.equals("Y"))
                continue;
            else
                break;   
            }
        in.close();  
        }
    }
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);
        }  
    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 String word;  
    }  

Friday, November 21, 2014

ISC COMPUTER SCIENCE PRACTICALS 2009 BOUNDARY ELEMENTS

Write a program to declare a matrix A[ ][ ] of order (m*n) where 'm' is the number of rows and
n is the number of columns such that both m and n must be greater than 2 and less than 20.
Allow the user to input positive integers into this matrix. Perform the following tasks on the
matrix:
(a) Sort the elements of the outer row and column elements in ascending order using any
standard sorting technique.
(b) Calculate the sum of the outer row and column elements.
(c) Output the original matrix, rearranged matrix, and only the boundary elements of the
rearranged array with their sum.
Test your program for the following data and some random data.
1. Example :
INPUT : M=3, N=3
1 7 4
8 2 5
6 3 9
OUTPUT :
ORIGINAL MATRIX :
1 7 4
8 2 5
6 3 9
REARRANGED MATRIX :
1 3 4
9 2 5
8 7 6
BOUNDARY ELEMENTS :
1 3 9
8   4
5 7 6
SUM OF OUTER ROW AND OUTER COLUMN = 43

    ISC COMPUTER SCIENCE PRACTICALS 2009 

import java.util.*;
public class OuterRowColumn {
    public static void main(String[] args) {
        int M,N;
        Scanner in = new Scanner(System.in);
        System.out.println("INPUT THE VALUE OF ROW:");
        M = in.nextInt();
        System.out.println("INPUT THE VALUE OF COLUMN:");
        N = in.nextInt();
        while( M > 20 || M < 2 || N > 20 || N < 2) {
            System.out.println("OUT OF RANGE, INPUT AGAIN:");
            M = in.nextInt();
            N = in.nextInt();
            }
        Matrix m = new Matrix(M,N);   
        m.inputMatrix();
        System.out.println("OUTPUT:");
        m.outputMatrix();
        System.out.println();
        m.rearrangedMatrix();
        m.outputMatrix();
        System.out.println();
        m.boundaryElements();
        in.close();
        }
    }   
class Matrix {
    Matrix(int M,int N) {
        row = M;
        col = N;
        Mat = new int[M][N];
        outerRowColSum = 0;
        boundary = new int[2*col+2*(row-2)];
        }
    public void outputMatrix() {
        for(int i = 0; i < row; i++) {
            for(int j = 0; j < col; j++) {
                System.out.print(Mat[i][j]+" ");
                }
            System.out.println();
            }
        }   
    public void rearrangedMatrix() {
        System.out.println("REARRANGED MATRIX :");
        int k = 0;
        for(int i = 0; i < row; i++)
            for(int j = 0; j < col; j++)
                if(i == 0 || j == 0 || i == row-1 || j == col-1)
                    boundary[k++] = Mat[i][j];
        Arrays.sort(boundary);    // sorting the boundary elements
        k = 0;       
        int i=0,j=0;
        // inserting the sorted boundary elements clockwise
        for ( i = 0; i < col; i++)
            Mat[j][i] = boundary[k++];
        for ( i = 1; i < row; i++)
            Mat[i][col-1] = boundary[k++];    
        for ( i = col-2; i >= 0; i--)
            Mat[row-1][i] = boundary[k++];   
        for ( i = row-2; i >= 1; i--)
            Mat[i][0] = boundary[k++];   
        }   
    public void boundaryElements() {
        System.out.println("BOUNDARY ELEMENTS :");
        int k = 0;
        for(int i = 0; i < row; i++) {
            for(int j = 0; j < col; j++) {
                if(i == 0 || j == 0 || i == row-1 || j == col-1) { // extracting the boundary elements
                    System.out.print(Mat[i][j]+" ");
                    boundary[k++] = Mat[i][j];
                    outerRowColSum += Mat[i][j];
                    }   
                else
                    System.out.print(" "+" ");       
                }
            System.out.println();
            }   
        System.out.println("SUM OF OUTER ROW AND OUTER COLUMN = "+outerRowColSum);   
        }   
    public void inputMatrix() {
        Scanner in = new Scanner(System.in);
        for(int i = 0; i < row; i++) {
            for(int j = 0; j < col; j++) {
                System.out.println("Input the element:");
                Mat[i][j] = in.nextInt();
                }
            }
        }   
    private int[] boundary;   
    private int row;   
    private int col;
    private int[][] Mat;
    private int outerRowColSum;
    }       

Tuesday, November 18, 2014

ISC COMPUTER SCIENCE PRACTICAL 2009 DAY NUMBER

Design a program to accept a day number (between 1 and 366), year (in 4 digits) from the user
to generate and display the corresponding date. Also accept 'N' (1<=N<=100) from the user to
compute and display the future date corresponding to 'N' days after the generated date.
Display error message if the value of the day number, year and N are not within the limit or
not according to the condition specified. Test your program for the following data and some
random data.

Example:

INPUT : DAY NUMBER : 233 YEAR : 2008 DATE AFTER(N) : 17
OUTPUT: 20TH AUGUST 2008 DATE AFTER 17 DAYS : 6TH SEPTEMBER 2008
INPUT : DAY NUMBER : 360 YEAR : 2008 DATE AFTER(N) : 45
OUTPUT: 25TH DECEMBER 2008 DATE AFTER 45 DAYS : 8TH FEBRUARY 2009

ISC Computer Science Practical 2009 Java Code

import java.util.*;
public class DayNumber {
    public static void main(String[] args) {
        int dayNumber,year;
        int dayAfter;
        boolean flag;
        Scanner in = new Scanner(System.in);
        DaysCalculation date = new DaysCalculation();
        do {
            System.out.println("INPUT THE DAY NUMBER:");
            dayNumber = in.nextInt();
            System.out.println("INPUT YEAR:");
            year = in.nextInt();
            System.out.println("INPUT THE VALUE OF N:");
            dayAfter = in.nextInt();
            flag = date.checkDate(dayNumber,year,dayAfter);
            if (flag == false)
                System.out.println("INVALID INPUTS:");
            } while(flag != true);
        date.setDate(dayNumber,year,dayAfter);   
        date.dateSpecifier();   
        in.close();
        }   
    }
class DaysCalculation {
    public void setDate(int dayNumber, int year, int dayAfter) {
        this.dayNumber = dayNumber;
        this.year = year;
        this.dayAfter = dayAfter;
        }
    public boolean checkDate(int dayNumber, int year, int dayAfter) {
        if ( dayNumber < 1 || dayNumber > 365 )
            return false;
            else if ( dayAfter < 1 || dayAfter > 100)
                return false;
                else if (String.valueOf(year).length() != 4)
                    return false;
                    else
                    return true;
        }
    public void dateSpecifier() {
        int m = 0,k=1;
        for(int i = 1; i <= dayNumber; i++) {
            if( checkLeap(year) == true ? k > ldays[m] : k > mdays[m] ) {
                k = 1;
                m++;
                }
            k++;   
            }
        String prefix;   
        prefix = (k-1)%10 == 1 ? "st" : (k-1)%10 == 2 ? "nd" : (k-1)%10 == 3 ? "rd" : "th";
        System.out.println(k-1+prefix+" "+months[m]);   
        for (int i = 1; i <= dayAfter; i++) {
            if( checkLeap(year) == true ? k > ldays[m] : k > mdays[m] ) {
                k = 1;
                m++;
                if(m > 11) {
                    year++;
                    m = 0;
                    }
                }
            k++;   
            }
        prefix = (k-1)%10 == 1 ? "st" : (k-1)%10 == 2 ? "nd" : (k-1)%10 == 3 ? "rd" : "th";
        System.out.println("DATE AFTER "+dayAfter+" DAYS:"+(k-1)+""+prefix+" "+months[m]);       
        }   
    private boolean checkLeap(int year) {
        if(year%400==0)
           leap=true;
        else if (year%100==0)
           leap=false;
        else if (year%4==0)
           leap=true;
        else
           leap=false;
           return leap;
        }    
    private boolean flag;
    private static boolean leap;   
    private int dayNumber,year;
    private int dayAfter;
    String[] months = {"January","Feburary","March","April","May","June","July","August","Sepetember","October","November","December"};
    int[] mdays={31,28,31,30,31,30,31,31,30,31,30,31};
    int[] ldays={31,29,31,30,31,30,31,31,30,31,30,31};   
    }           

Wednesday, October 22, 2014

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 211 and 37 is not difficult, as any calculator would confirm that 211 = 2048 < 37 = 2187.
However, confirming that 632382518061 > 519432525806 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/20.5
1/30.(3)
1/40.25
1/50.2
1/60.1(6)
1/70.(142857)
1/80.125
1/90.(1)
1/100.1
Where 0.1(6) means 0.166666..., and has a 1-digit recurring cycle. It can be seen that 1/7 has a 6-digit recurring cycle.
Find the value of d < 1000 for which 1/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()                              

Tuesday, October 21, 2014

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

Sunday, October 19, 2014

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

Saturday, October 18, 2014

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 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?

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;
    }       

Friday, October 17, 2014

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

Thursday, October 16, 2014

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 → 11
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 = 14 + 64 + 34 + 44
8208 = 84 + 24 + 04 + 84
9474 = 94 + 44 + 74 + 44
As 1 = 14 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()