Python,C,C++ and JAVA programs for CBSE, ISC and MCA students

The Programming Project

Monday, September 1, 2014

Truncatable primes : Problem 37 Euler Project Pyhton Code

Truncatable primes : Problem 37

The number 3797 has an interesting property. Being prime itself, it is possible to continuously remove digits from left to right, and remain prime at each stage: 3797, 797, 97, and 7. Similarly we can work from right to left: 3797, 379, 37, and 3.
Find the sum of the only eleven primes that are both truncatable from left to right and right to left.
NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes.

Problem Source : Euler Project

Python Code : Truncatable Prime
import math
def TruncatablePrime():
    def checkPrime(numb):
        prime = True
        if numb == 1:
            return False
        else:   
            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 reverse(text):
            if len(text) <= 1:
                return text
            return reverse(text[1:]) + text[0]           
    truncPrimeCount = 0   
    sumTruncPrimeCount = 0   
    dummy = 12
    while truncPrimeCount < 11:
        if checkPrime(dummy) == True:
            strnumb = str(dummy)
            flag = False
            truncPrimeflag = False
            for i in range(len(strnumb)-1):
                i = i+1
                if int(strnumb[i])%2 == 0:
                    flag = True   
                    break
            if flag == False:
                strnumbrev = reverse(strnumb)
                #print "reverse",strnumbrev
                tmpstrleft = ""
                tmpstrright = ""
                for i in range(len(strnumb)-1):
                    tmpstrleft = tmpstrleft+strnumb[i]
                    #print "111*****",tmpstrleft
                    tmpstrright =(tmpstrright)+strnumbrev[i]
                    #print "222#####",tmpstrright
                    if checkPrime(int(tmpstrleft)) == True and checkPrime(int(reverse(tmpstrright))) == True:
                        truncPrimeflag = True
                    else:
                        truncPrimeflag = False
                        break
                if truncPrimeflag == True:
                    sumTruncPrimeCount = sumTruncPrimeCount + dummy
                    truncPrimeCount = truncPrimeCount + 1   
                    print "Truncatable Prime[",truncPrimeCount,"]",dummy
        dummy = dummy + 1
       
    print "sum of the only eleven primes that are both truncatable from left to right and right to left",sumTruncPrimeCount                                           
TruncatablePrime()

Sunday, August 31, 2014

Consecutive prime sum :Problem 50

Consecutive prime sum :Problem 50

The prime 41, can be written as the sum of six consecutive primes:
41 = 2 + 3 + 5 + 7 + 11 + 13
This is the longest sum of consecutive primes that adds to a prime below one-hundred.
The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953.
Which prime, below one-million, can be written as the sum of the most consecutive primes?

Problem Source : Euler Project

Python Code 

import math
def largestSumofConsecutivePrime():
    def checkPrime(numb):
        prime = True
        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
    primeList = ()   
    cumiSumList = ()
    sumd = 0
    count = 0
    cumiSumList =cumiSumList+(0,)
    maxPrime = 0
    maxLength = 0
    for prime in range(1000000):
        prime = prime + 2
        if checkPrime(prime) == True:
            primeList = primeList+(prime,)
            sumd = sumd + prime
            cumiSumList =cumiSumList+(sumd,)
            count = count + 1
    #print primeList
    #print cumiSumList
    for i in range(count):
        for j in range(i+1):
            if cumiSumList[i]-cumiSumList[j] > 1000000:   
                break
            if (cumiSumList[i]-cumiSumList[j]) in primeList:
                if i-j > maxLength:
                    maxLength = i-j
                    maxPrime = cumiSumList[i] - cumiSumList[j]
    print maxLength,maxPrime                   
largestSumofConsecutivePrime()                


Saturday, August 30, 2014

Lychrel numbers : Problem 55 Euler Project

Lychrel numbers : Problem 55

If we take 47, reverse and add, 47 + 74 = 121, which is palindromic.
Not all numbers produce palindromes so quickly. For example,
349 + 943 = 1292,
1292 + 2921 = 4213
4213 + 3124 = 7337
That is, 349 took three iterations to arrive at a palindrome.
Although no one has proved it yet, it is thought that some numbers, like 196, never produce a palindrome. A number that never forms a palindrome through the reverse and add process is called a Lychrel number. Due to the theoretical nature of these numbers, and for the purpose of this problem, we shall assume that a number is Lychrel until proven otherwise. In addition you are given that for every number below ten-thousand, it will either (i) become a palindrome in less than fifty iterations, or, (ii) no one, with all the computing power that exists, has managed so far to map it to a palindrome. In fact, 10677 is the first number to be shown to require over fifty iterations before producing a palindrome: 4668731596684224866951378664 (53 iterations, 28-digits).
Surprisingly, there are palindromic numbers that are themselves Lychrel numbers; the first example is 4994.
How many Lychrel numbers are there below ten-thousand?

Problem Source : Euler Project

Python Code


def lychrelNumbers():
    counter = 50
    lychrelCounter = 0
    def reverse(text):
            if len(text) <= 1:
                return text
            return reverse(text[1:]) + text[0]
    for i in range(10000):
        i = i+1
        count = 0
        k = i
        while True:
            s1 = str(k)
            s2 = reverse(s1)
            s3 = str(int(s1)+int(s2))
            if s3 != reverse(s3):
                count = count + 1
            else:
                break   
            k = int(s3)
            if count > counter:
                lychrelCounter = lychrelCounter + 1
                break
    print lychrelCounter
lychrelNumbers()               
                   
       
       

Amicable numbers : Problem 21 Euler Project

Amicable numbers : Problem 21

Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).
If d(a) = b and d(b) = a, where ab, then a and b are an amicable pair and each of a and b are called amicable numbers.
For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.
Evaluate the sum of all the amicable numbers under 10000.

Problem Source : Euler Project

Python Code

def amicableNumber():
    totalSum = 0
    def sumOfDivisors(numb):
        sumD = 0
        for d in range(numb/2):
            d = d+1
            if numb%d ==0:
                sumD = sumD + d
        return sumD
    for i in range(10000-1):
        i = i+1
        if i == sumOfDivisors(i):
            continue
        if i == sumOfDivisors(sumOfDivisors(i)):
            print i
            totalSum = totalSum + i   
    print "Evaluate the sum of all the amicable numbers under 10000:",totalSum
amicableNumber()               

Lexicographic permutations:Problem 24

Lexicographic permutations:Problem 24

A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:
012   021   102   120   201   210
What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

Problem Source Euler Project

C Code

#include<stdio.h>
#include<malloc.h>
void sort(char *permutation,int n,int pos);
void replace_min (char *permutation,int n,int pos);
int main()
{
char alpha[]={'0','1','2','3','4','5','6','7','8','9','K','L','M',
          'N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
int n,i,flag=1,pos;
long int tot=0;
char *permutation;
printf("\n Enter the numbr of objects (max values is 26):");
scanf("%d",&n);
permutation =(char *)malloc(n*sizeof(char));
for(i=0;i<n;i++)
    permutation[i]=alpha[i];
printf("\n The permutations are:\n");
printf("\t\t      ");
for(i=0;i<n;i++)
    printf("%c",permutation[i]);
    tot=1;
while(flag)
    {
    pos=-1;
    for(i=n-1;i>=1;i--)
        {
        if(permutation[i-1]<permutation[i])
             {
             pos=i-1;
             flag=1;
             break;
             }
        }
        if(pos==-1)
            {
            flag=0;
            break;
            }
    replace_min(permutation,n,pos);
    sort(permutation,n,pos);
   printf("\n");
    printf("\t\t      ");
    for(i=0;i<n;i++)
        printf("%c",permutation[i]);
    tot++;
    printf(">>>>>>>>>>%ld",tot);
    if (tot==1000000)
        break;
    }
//printf("\n Total number of permutation is: %ld",tot);
return 0;
}
void sort(char *permutation,int n,int pos)
{
    int i,j;
   char temp='A';
    for(i=pos+1;i<n-1;i++)
        {
        for(j=pos+1;j<n-1;j++)
            {
            if(permutation[j]>permutation[j+1])
                {
                temp=permutation[j+1];
                permutation[j+1]=permutation[j];
                permutation[j]=temp;
                }
            }
        }
  return;
}
void replace_min(char *permutation,int n,int pos)
{
  char min='Z',temp;
  int k,min_pos=0;
  for(k=pos+1;k<n;k++)
    {
        if(permutation[k]>permutation[pos])
            {
            if(permutation[k]<min)
                {
                min=permutation[k];
                min_pos=k;
                }
            }
    }
    temp=permutation[min_pos];
    permutation[min_pos]=permutation[pos];
    permutation[pos]=temp;
    return;
}

1000-digit Fibonacci number : Problem 25

1000-digit Fibonacci number : Problem 25

The Fibonacci sequence is defined by the recurrence relation:
Fn = Fn−1 + Fn−2, where F1 = 1 and F2 = 1.
Hence the first 12 terms will be:
F1 = 1
F2 = 1
F3 = 2
F4 = 3
F5 = 5
F6 = 8
F7 = 13
F8 = 21
F9 = 34
F10 = 55
F11 = 89
F12 = 144
The 12th term, F12, is the first term to contain three digits.
What is the first term in the Fibonacci sequence to contain 1000 digits?

Problem Source: Euler Project

Python Code

def ThousandDigitFiboNumbers():
    a = 1
    b = 1
    nextSum = 0
    totalSum = 2
    while True:
        nextSum = a+b
        a = b
        b = nextSum
        totalSum = totalSum + 1
        if len(str(nextSum)) == 1000:
            break
    print "first term in the Fibonacci sequence to contain 1000 digits:",totalSum       
ThousandDigitFiboNumbers()

Power digit sum : Problem 16 Python Code

Power digit sum : Problem 16 Euler Project

215 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.
What is the sum of the digits of the number 21000?

Python Code

def powerDigitSum():
    l = 2**1000
    strNumb = str(l)
    sumFact = 0
    for i in range(len(strNumb)):
        sumFact = sumFact + int(strNumb[i])
    print "sum of the digits in the number! is",sumFact
powerDigitSum()