A number theory problem by A Former Brilliant Member

The key is that any 8-digit palindrome is composite, because it is a multiple of 11. This follows most easily from the divisibility rule for 11: $\overline{abcddcba}\ \ \ \text{is divisible by 11 iff}\ \ \ \ a - b + c - d + d - c + b - a = 0\ \ \ \text{is divisible by 11},$ which is obviously the case.

The problem is now reduced to counting how many such palindromes there are. For $b,c,d$ we have 10 digits to choose from; for $a$ only 9, because a number can't start in zero. This leaves us with $9 \cdot 10^3 = \boxed{9000}$ palindromes.

This question would be a lot harder if it weren't multiple choice as a lot of the choices can be eliminated.

Let's call an 8 digit palindrome $\overline{abcddcba}$ .

Since every digit, except $a$ which can't be $0$ , can be the digits $(0 , 1, 2, \cdots 8, 9)$ therefore there are $10 \times 10 \times 10 \times 9 = 9000$ different possibilities for the number $\overline{abcddcba}$ . So we can eliminate the first choice. Also the 8 digit palindrome is definitely composite if $a$ is even. This means that $10 \times 10 \times 10 \times 4 = 4000$ so we can eliminate choice 2 and choice 3.

$\therefore$ The answer is choice 4 $\boxed{9000}$ .

If the number of digits is even then all palindromes are not primes since they are divisible by 11 (sure, with one exception of 11 for two-digit number).

Also, if the number of digits is odd it's harder to come up with the correct answer. In that case, the following procedure could be used:

 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

def is_palindrome(n):
    return str(n) == str(n)[::-1]


def is_prime(n):
    if n == 2:
        return True
    if n == 3:
        return True
    if n % 2 == 0:
        return False
    if n % 3 == 0:
        return False

    i = 5
    w = 2
    while i * i <= n:
        if n % i == 0:
            return False

        i += w
        w = 6 - w

    return True


def count_composite_palindromes(n_digits=8):
    cnt_prime = 0
    for i in range(10 ** (n_digits - 1), 10 ** n_digits):
        if is_palindrome(i):
            if int(str(i)[0]) % 2 == 0:
                cnt_prime += 1
            elif not is_prime(i):
                cnt_prime += 1
    return cnt_prime

For different n it returns:

My methode was to considre that there are 4 digits identical to the other 4 digits so we have 9999 case : a b c d ' d c b a but we must eliminate all numbers which start with 0 , in 10 we have only 1 number starts with 0 which is 10 in 100 we have 10 so in 10000 we have 999 number ( don't add 10000 as a case) so we got 9999 cases substracted by 999 and in the end we had 9000

Every 8 digit palindrome $d_1d_2d_3d_4d_4d_3d_2d_1$ can be written as:

$d_1(10^7) + d_2(10^6) + d_3(10^5) + d_4(10^4) + d_4(10^3) + d_3(10^2) + d_2(10^1) + d_1(10^0) = d_1(10000001) + d_2(1000010) + d_3(100100) + d_4(11000)$

And , since 10000001, 1000010, 100100, 11000 all pass the divisible rule of 11 (the difference of the alternating sum of digits of N is a multiple of 11):

all 8-palindrome is a factor of 11; a composite number.

So the aswer is all posible 8-palindromes: $9\cdot10^3$

First one is 1000 0001, last one 9999 9999, there is 9000 number between 1000 and 9999

Since C is a fast language, I decided to use it for the purposes of this question. It runs pretty well, in about 4 seconds on my machine:

 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

#include <stdio.h>

int is_composite(int number) {
    if (number % 2 == 0) return 1;
    for (int iterator = 3; iterator < number; iterator += 2) if (number % iterator == 0) return 1;
    return 0;
}

int inverse(int number){
    int result = 0;
    int number_copy = number;
    while (number_copy > 0){
        result = result * 10 + number_copy % 10;
        number_copy /= 10;
    }
    return result;
}

int main(){

    int count = 0;
    for (int integer = 10000000; integer < 100000000; integer++) if (inverse(integer) == integer && is_composite(integer)) count += 1;
    printf("%d", count);
    return 0;
}

This yields the result 9000 .

In any number if we add alternate digits and subtract one from the other, like for example if a number is 'abcd' sum of alternate digits is a+c, b+d. If the difference is divisible by 11, then the number is divisible by 11.

So any palindrome of even size, like aa, abba, abcddcba, etc will all be divisible by 11 as the difference of sum of alternate digits is 0.

So every palindrome is composite. As first number can't be a 0, we can have 9 different digits to choose from for the first digit. Three following digits can take any of 10 numbers 0-9. The rest 4 are the first 4 in reverse order.

Total composite palindromes =9 10 10*10 =9000

There are 8 digits abcdefgh .In this number a=h, b=g, c=f, d=e. Then the number comes out to be abcddcba. 'a' can have only 9 values , 'b' an have 10 values , 'c' can have 10 values and 'd' can also have 10 values . Rest of digit. must have same value as a,b,c,d so they can take only one value. So the answer is 9x10x10x10x1x1x1x1 = 9000 .

And every palidromic number which contains even number of digits is multiple of 11. abcdefgh : ( a+c+e+g)-(b+d+f+h)=(a+b+c+d)-(a+b+c+d). { a=h,b=g,c=f,d=e}

                                                 =0,

Which means that is divisible by 11

abcddcba

a : 1 to 9 = 9 digit

b : 0 to 9 = 10 digit

c : 0 to 9 = 10 digit

d : 0 to 9 = 10 digit

(9) (10) (10)*(10) = 9000 numbers

We don't need to consider the last 4 digits of it which is symmetric. But 0 is not allowed at the first. We can choose 1 to 9 at the first digit, and second to fourth would be 10 choices. And these occurs simultaneously that we multiply 4 of them: 9•10^3=9000

Any even digit palindrome is always composite only(always multiple of $11$ )

So for ( $2n$ ) digit palindrome, the answer is

$9(10^{n-1})$

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

import math
count=0
lista=[]
# Since there is reflection symmetry, we can scan all 4 digit numbers
for j in range(1000,10000):
    p=j
    s= p*pow(10,4)
    # We get the palindromic number by adding in reverse order the original digits, one by one 
    for i in range (1,5):
        new= p%10
        s+=new*pow(10,4-i)
        p=(p-new)//10
    if s%2==0 or s%3==0 or s%5==0 or s%7==0 or s%11==0 or s%13==0:
        count+=1
        lista.append(s)
print("The number is", count)
#You can even print those numbers if you are brave enough
print("Those numbers are", lista)

The answer is $\boxed{9000}$ Of course you can check whether s is divisible by primes greater than 13. You will find no change

Solution not knowing the 'division by 11 rule' and using R-script

The inner 6 numbers of the palindrome are constructed using the numbers 000:999 and for each one we paste its mirror behind it. (ex: 001 100). This leads to a total of 1000 numbers of length 6.

What we know for the outer numbers (first and last) of the palindrome:

• Palindromes starting/ending with 0 are not allowed

• Palindromes starting/ending with an even number are guaranteed composite (n = 4 x 1000)

• Palindromes starting/ending with 5 are guaranteed composite (n = 1 x 1000)

==> We have at least 5000 composite palindromes

This leaves us with 4000 numbers to check: the ones starting/ending in 1, 3, 7, 9. We can use a script to check each number.

 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

firstLast = c("1", "3", "7", "9")
myList = data.frame(matrix(nrow = 1000, ncol = 6))
myList[,1:3] = permutations(n=10,r=3,v=0:9,repeats.allowed=T)
myList[,4:6] = myList[,3:1]

count = 0

for(j in 1:4){
  for(i in 1:1000){
    run = T
    number = as.numeric(paste(firstLast[j], paste(myList[i,], collapse = ""), firstLast[j], sep = ""))
    x = 3
    while(run){
      test = number/x
      if(test %% 1 == 0){
        run = F
      } else if(x < floor(sqrt(number))){
        x = x + 2
      } else {
        run = F
        count = count + 1
      }
    }
  }
}

print(paste("The number of prime palindromes in the sample is:", count))

The script runs in less than a second and returns 0 prime numbers, so all 4000 are composite. This means in total there are 5000 + 4000 = 9000 composite palindromes of length 8

I did:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

from math import sqrt; from itertools import count, islice

def isPrime(n):
    return n > 1 and all(n%i for i in islice(count(2), int(sqrt(n)-1)))

non_prime = 0
for i in range(1000,10000): # first palindrome is "1000_0001", last one will be "9999_9999"
    palindrome = int("%s%s" % (str(i), str(i)[::-1]))
    if not isPrime(palindrome):
        non_prime += 1
print non_prime 

I solved this with ruby...

require 'prime'
a=0
for i in 1..9
  for j in 0..9
    for k in 0..9
      for l in 0..9
        if not(Prime.prime?(i*10000001+j*1000010+k*100100+l*11000))
          a+=1
        end
      end
    end
  end
end
puts a

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

 Matlab
1. k=0;
2. for i = 10000000:99999999
3.    a = num2str(i);
4.    b = flip(a);
5.    if a == b
6.        if isprime(i) == 0
7.            k=k+1;
8.       else
9.        end
10.    else
11.    end
12. end
13. disp(k) 

I'm not a good programmer and this takes an insane amount of time, but it worked. Also, I can't figure out how to format this so it becomes readable, sorry.