Primey Palindromes

Computer Science Level 4

Let a a be an n n digit palindrome.
Let f ( x ) = f(x) = the sum of the digits of x x .
Given that there are 13 values such that a a is prime and a + f ( a ) a + f(a) is also prime, what is the value of n n ?

Example
- 383 383 is a prime palindrome
- f ( 383 ) = 3 + 8 + 3 = 14 f(383) = 3+8+3=14
- 383 + f ( 383 ) = 397 383+f(383)=397 which is also prime

I also made a slightly harder version of this problem - Primey Palindromes V2


The answer is 5.

View wiki
Katie Gardner by Katie Gardner , 24, United Kingdom

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

6 solutions

Daniel Rabelo
Jul 22, 2014

python3.4 python3.4

5 Helpful 0 Interesting 0 Brilliant 0 Confused
Abhimanyu Singh
Jul 22, 2014

Wrote the following code to solve this problem. Got result in 0.01 sec. 

  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
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
 
    #include "iostream"
    #include "string"

    #include "cstdio"

    using namespace std;

    #define int64 long long int

    int64 power(int64 a, int64 n, int64 mod) {
        int64 power = a, result = 1;

        while (n) {
            if (n & 1) { 
                result = (result * power) % mod;
            }

            power = (power * power) % mod;
            n >>= 1;
        }

        return result;
    }

    bool witness(int64 a, int64 n) {
        int64 t, u, prev, curr;

        u = n / 2;
        t = 1;

        while (! ( u & 1)) {
            u /= 2;

            ++t;
        }

        prev = power(a, u, n);

        for (int64 i = 1; i <= t; ++i) {
            curr = (prev * prev) % n;

            if ((curr == 1) && (prev != 1) && (prev != (n - 1))) { 
                return true;
            }

            prev = curr;
        }

        if (curr != 1) { 
            return true;
        }

        return false;
    }

    bool is_prime(int64 number) {
        if (((! (number & 1)) && number != 2) || (number < 2) || ((number % 3 == 0) && (number != 3))) {
            return (false);
        }

        if (number < 1373653LL) {
            for (int64 k = 1; 36 * k * k - 12 * k < number; ++k) {
                if ((number % (6 * k + 1) == 0) || (number % (6 * k - 1) == 0)) {
                    return (false);
                }
            }

            return true;
        }

        if (number < 9080191LL) {
            if (witness(31, number)) {
                return false;
            }

            if (witness(73, number)) {
                return false;
            }

            return true;
        }

        if (witness(2, number)) {
            return false;
        }

        if (witness(7, number)) {
            return false;
        }

        if (witness(61, number)) {
            return false;
        }

        return true;
    }

    bool is_palindrome(string s) {
        for (int i = 0; i < s.size(); i++) {
            if (s[i] != s[s.size() - 1 - i]) {
                return false;
            }
        }

        return true;
    }

    int64 digit_sum(int64 num) {
        string num_str = to_string(num);

        int64 sum = 0;

        for (int i = 0; i < num_str.size(); i++) {
            sum += (num_str[i] - '0');
        }

        return sum;
    }

    int main() {
        int t = 1;

        while (t--) {
            int c = 0;

            for (int64 i = 11; c < 13; i += 2) {
                if (is_prime(i)) {
                    if (is_palindrome(to_string(i))) {
                        if (is_prime(i + digit_sum(i))) {
                            c++;

                            if (c == 13) {
                                printf("%u\n", to_string(i).size());
                            }
                        }
                    }
                }
            }
        }

        return 0;
    }

2 Helpful 0 Interesting 0 Brilliant 0 Confused

Wow 0.01 seconds is really good!! :D

Katie Gardner - 6 years, 10 months ago

Log in to reply

Actually first I thought of solving it manually but after 15 mins I realized that I must write the code. :P :D

Abhimanyu Singh - 6 years, 10 months ago

This code takes just 0.25 secs to list all the palindromic primes less than 10000000000 that satisfy the given constraints. So this runs in fractions of milliseconds to solve this problem. Seems to be fastest running code. 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
 
You can get the code in Version 2 solution 
of this problem.
The output format for the code is like-

/*Output-
Palindromic_Primes_Count(2 digits) =  ?[Prime?].
Palindromic_Primes_Count(3 digits) =  ?[Prime?].
Palindromic_Primes_Count(5 digits) =  ?[Prime?].
Palindromic_Primes_Count(7 digits) =  ?[Prime?].
Palindromic_Primes_Count(9 digits) = ?[Prime?].
*/

Abhimanyu Singh - 6 years, 10 months ago
Lokesh Sharma
Jul 21, 2014 
 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
 
def isPalin(num):
    '''
    Checks if the number 'num' is palindrome
    '''
    return str(num) == str(num)[::-1]

def f(x):
    '''
    Return sum of digits of x
    '''
    return sum(map(int, str(x)))

def isPrime(num):
    '''
    Returns True if num is prime
    '''
    for i in range(2, int(num**.5)+1):
        if num % i == 0:
            return False
    return True

def checkRange(r):
    '''
    Checks within the range 'r'
    and returns number of numbers
    satisfying the criteria
    a is prime and a + f(a) is also prime
    '''
    res = 0
    for i in r:
        if isPalin(i) and isPrime(i) and isPrime(i + f(i)):
            res += 1

    return res

def buildRange(n):
    '''
    Returns all n digits numbers
    '''
    return range(10**(n-1), 10**(n))

n = 2
while True:
    if checkRange(buildRange(n)) == 13:
        print n #Here's the answer
        break
    n += 1

1 Helpful 0 Interesting 0 Brilliant 0 Confused
Bill Bell
Mar 4, 2015

Uses code from the Python sympy library to supply primes in n-digit range. Has all the tests for suitable numbers (palindromic, etc) in a single function.

0 Helpful 0 Interesting 0 Brilliant 0 Confused

I used prime palindrome number in Google. Number with middle term even would give, summation of digits as even. Our number is odd so this would give us ..a + f(a).. also as odd. Checked from Google if it was prime or not. 98689 was the 13th number ..with...
..a + f(a)..=98729..... Note even digit palindrome will never be prime since it will always be divisible by 11.

0 Helpful 0 Interesting 0 Brilliant 0 Confused
Cody Johnson
Jul 21, 2014

PalindromeQ[n_] := Catch[ s = IntegerDigits[n]; Do[ If[s[[i]] != s[[Length[s] - i + 1]], Throw[False]] , {i, Ceiling[Length[s]/2]}] Throw[True] ]

DigitSum[n_] := Total[IntegerDigits[n, 10]]

Do[ If[PalindromeQ[Prime[n]] && PrimeQ[Prime[n] + DigitSum[Prime[n]]], Print[Prime[n]]] , {n, 1000000}]

Then I saw the output for 5 digits :)

0 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...