PalPrimes

My general method was generating the palindromes first and then check them for primality. Generating palindromes is quite easy. For every integer $N=\overline { abc }$ (where $a,b,c$ are the base 10 digits of $N$ ) there exists two unique palindromes $\overline{abccba}$ and $\overline{abcba}$ . So I would only do $10^5$ checks at most.

After generating all the palindromes I check for primality. The code could have been faster if I used a better primality test like Miller Rabin but the normal method sufficed here. Also after generating the palindromes,I sorted them and started checking primality backwards.

Here's my code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

Palindromes = []
Limit = 10**9
def isprime(N):
    for i in range(2,int(N**.5)+1):
        if N%i==0:return 0
    return 1
def Make_Palindrome( n ):
    global Palindromes
    Sn = str( n )
    A = Sn + Sn[ :: - 1 ]
    Position = len( Sn )
    Palindromes += [ int( A ) , int( A[ 0 : Position ] + A[ Position + 1 :: ] ) ]

for n in range(10**5):
    Make_Palindrome(n)

Palindromes = sorted(filter(lambda x:x<Limit,Palindromes))
for palindrome in Palindromes[::-1]:#Start backwards
    if isprime(palindrome):
        print palindrome
        break

I wasn't able to figure out a really slick way to solve this. It helps if you have a program written to factor numbers (or determine if prime). Such programs have been shared before, and are not too hard to write for numbers with less than 12 digits.

After some thought, it was obvious the number should start with as many 9's as possible. Therefore I tried numbers of the form 9999n9999. None of these were prime.

It took a little more thought to convince myself that next I should try 9998n8999. Then 9997n7999. Finally a prime was found.

999727999 is prime. The digit sum is $\boxed{70}$

I presume that such prime number is a nine-digit one. A matlab built-in function, isprime , determines whether a number is prime or not.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

tic
for x1=9:-2:1
    for x2=9:-1:0
        for x3=9:-1:0
            for x4=9:-1:0
                for x5=9:-1:0
                    A=x1*(1e8+1)+x2*(1e7+10)+x3*(1e6+100)+x4*(1e5+1000)+x5*1e4;
                    if isprime(A)
                        fprintf('\nThe largest palindromic prime(<10^9) is %i\n',A)
                        return
                    end    
                end
            end
        end
    end
end
toc

OUTPUT

1
2

The largest palindromic prime (<10^9) is 999727999
Elapsed time is 0.020618 seconds. 

Quick and dirty perl solution. Only worked on odd numbers from 999999999 down to save bothering with guaranteed non prime even numbers. Checked palidromic first to avoid wasting time checking that every palindrome is prime.

sub is_prime {
  (my $number) = @_;
  my $d = 2;
  my $sqrt = sqrt $number;
  while(1) {
    if ($number % $d == 0) {
      return 0;
    }
    if ($d < $sqrt) {
        $d++;
    }
    else {
        print "$number\n";
        return 1;
    }
  }
}

my $num = 999999999;
my $found = 0;

while ( $found == 0 ) {
  if ( $num == reverse $num ) {
    if ( is_prime $num ) {
      $found = 1;
    }
    else {
      $num -= 2;
    }
  }
  else {
    $num -= 2;
  }
}

print "Largest palindromic prime less than 1000000000 is: $num\n";
my $sum = 0;
foreach my $x (split //, $num) {
  $sum += $x;
}
print "Sum of digits is $sum\n";

Basically I checked if it was a palindrome by reversing the number and checking if it was the same as the original number. Then I checked if the number was prime. The isPrime() method was checking for factors until the square root, as that is the maximum factor a number can be. The rest is explained in comments in my code.

public class ReverseNumber {
    public static void main(String args[]) {
System.out.println(findNumber());   
}

static boolean isPrime(long n) {
    //check if n is a multiple of 2
    if (n%2==0) return false;
    //if not, then just check the odds
    for(long i=3;i*i<=n;i+=2) {
        if(n%i==0)
            return false;
    }
    return true;
}

    public static long findNumber() {
        String a = "";
        for(long i = 1000000000l;i>0;i--){
                if(isPalindrome(i)){
                    if(isPrime(i)){
                        return i;
                    }
                }

            }
        return 2;
        }


    public static boolean isPalindrome(long number) {
        long palindrome = number; // copied number into variable
        long reverse = 0;

        while (palindrome != 0) {
            long remainder = palindrome % 10;
            reverse = reverse * 10 + remainder;
            palindrome = palindrome / 10;
        }

        // if original and reverse of number is equal means
        // number is palindrome in Java
        if (number == reverse) {
            return true;
        }
        return false;
    }

}

First, I created a function to check whether a number is palindromic. I then tested this on every number descending from $10^{9}$ . If these numbers were palindromic, I then tested for primality. Finally, as soon as the code found a number that was both palindromic and prime, it printed this to the console and stopped both loops.

def palindrome(number):
    y= str(number)
        if y == y[::-1]:
            return y
        else:
            return

for n in range(10**9, 2, -1):
    temp = palindrome(n)
    if temp != None:
        print temp
        for x in range(2, n):
            if n % x == 0:
                break
        else:
            print(n)
            quit = True
            break

        if quit == True:
            break

The digit sum was then found with the short piece of (unnecessary (as I could have done it in my head)) code shown below.

string = "999727999"
total = 0
for x in range(len(string)):
    temp = string[x]
    total += int(temp)

print(total)

The total was $\boxed{70}$

First it checks if the number is a palindrome,then checks if it is prime and finally calculates the digit sum.

My highly inefficient c# code :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

 static void Main(string[] args)
        {
            UInt64 sum = 0;
            for (UInt64 i = (UInt64)Math.Pow(10,9) - 1 ; i >= 101  ; i--)
            {                
                if (IsPalin(i))
                {
                   if(IsPrime(i))
                   {
                       sum = DigitSum(i);
                       break;                                         
                   }
                }              
            }
            Console.WriteLine(sum);
            Console.ReadLine();     
        }
        private static bool IsPrime(UInt64 number)
        {
            for (UInt64 index = 2; index <= (UInt64)Math.Sqrt(number); index++)
                if (number % index == 0) return false;
            return true;
        }
        public static string ReverseString(string s)
        {
            char[] arr = s.ToCharArray();
            Array.Reverse(arr);
            return new string(arr);
        }
        public static bool IsPalin(UInt64 n)
        {
            String orig = Convert.ToString(n);
            String rev = ReverseString(orig);
            UInt64 reverse = Convert.ToUInt64(rev);
            if ((reverse - n) == 0) return true;
            else return false;
        }
        public static UInt64 DigitSum(UInt64 n)
        {
            UInt64 num = 0, r, sum = 0;
            num = n;
            while(num>0)
            {
                r = num % 10;
                num = num / 10;
                sum = sum + r;
            }
            return sum; 
        }

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def is_prime(a):
    return a > 1 and all(a % i for i in xrange(2, a))
c=10**9
while c>=10:
    if str(c)==str(c)[::-1]:
        if is_prime(c):
            break
    c-=1
summ=0
for i in str(c):
    summ+=int(i)
print summ

checks for palindrome then prime then sum.