Prime Coincidence

2 2 2 = 2 × 11 67 67 76 = 2 × 3388 479 479 974 = 2 × 239987 8123 8123 3218 = 2 × 40616609 56209 56209 90265 = 5 × 1124198053 999007 999007 700999 = 7 × 142715385857 \displaystyle \begin{aligned} \color{#3D99F6} 2 & \Longrightarrow {\color{#3D99F6} 2}{\color{#D61F06}2} = 2 \times 11 \\ \color{#3D99F6} 67 & \Longrightarrow {\color{#3D99F6}67}{\color{#D61F06}76} = 2 \times 3388 \\ \color{#3D99F6} 479 & \Longrightarrow {\color{#3D99F6}{479}}{\color{#D61F06}{974}} = 2 \times 239987 \\ \color{#3D99F6} 8123 & \Longrightarrow {\color{#3D99F6}{8123}}{\color{#D61F06}{3218}} = 2 \times 40616609 \\ \color{#3D99F6} 56209 & \Longrightarrow {\color{#3D99F6}{56209}}{\color{#D61F06}{90265}} = 5 \times 1124198053 \\ \color{#3D99F6} 999007 & \Longrightarrow {\color{#3D99F6}{999007}}{\color{#D61F06}{700999}} = 7 \times 142715385857 \end{aligned}

You have a machine that does some very interesting prime arithmetic. The machine takes in a prime number, reverses its digits, and attaches the resulting number to the prime input to form a new number.

It seems that for every prime number shown above (in the far left column), the machine produces a composite number (as implied by the right side of the equation).

Does there exist a prime for which the machine will produce another prime?

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.

4 solutions

Marco Brezzi
Aug 12, 2017

Relevant wiki: Divisibility Rules

Let the prime number p p be

p = a 1 a 2 a n p=\overline{a_1a_2\ldots a_n}

Where the a i a_i i { 1 , 2 , , n } i\in\{1,2,\ldots,n\} are the digits of p p

After the process we get m = a 1 a 2 a n a n a 2 a 1 m=\overline{a_1a_2\ldots a_na_n\ldots a_2a_1}

m m is divisible by 11 11 if and only if the sum S S of its digits with alternated signs is divisible by 11 11

S = a 1 a 2 + ± a n a n a 2 a 1 = 0 0 m o d 11 \begin{aligned} S&=\mathbin{\color{#D61F06}a_1} \mathbin{\color{#3D99F6}-a_2}+\ldots \mathbin{\color{#20A900}\pm a_n}\mathbin{\color{#20A900}\mp a_n}\ldots \mathbin{\color{#3D99F6}a_2}\mathbin{\color{#D61F06}-a_1}\\ &=0\equiv 0 \mod{11} \end{aligned}

Since m m is a positive integer divisible by 11 11 and it's not 11 11 itself (because that would imply p = 1 p=1 , which is not prime), m m is always composite

Moderator note:

The comments mention that 1 doesn't work, but also that since 1 isn't prime it isn't accepted as an input by the machine. ( Discussion on if 1 is prime is at our wiki here .)

Note that, historically but not universally, 1 used to be considered prime. (Euler, in a work from 1770, did not consider 1 a prime. Yet in 1914, the Carnegie Institution published an engrossing work entitled List of Prime Numbers from 1 to 10006721 .) However, there came to be many instances where we wanted something to be true for all prime numbers "except 1". Excluding 1 as a prime is now standard. (From what I gather, some European countries were the last holdouts on this -- if you believe you heard back in school that 1 is a prime number, you might not be mistaken.)

The most prominent example is the Fundamental Theorem of Arithmetic which states any integer 2 or larger has a unique factorization into primes. If 1 was allowed as a prime, this wouldn't be true (consider 10 = 2 × 5 = 2 × 5 × 1 = 2 × 5 × 1 × 1 = ) . 10 = 2 \times 5 = 2 \times 5 \times 1 = 2 \times 5 \times 1 \times 1 = \ldots ).

Cool! Another way to say it is that the machine produces palindromic numbers with an even number of digits which, as you explain well, are divisible by 11.

Andrew Lamoureux - 3 years, 9 months ago

Log in to reply

Yes , by the same argument every palindromic number with an even number of digits is divisible by 11 11

Marco Brezzi - 3 years, 9 months ago

Sorry I got it wrong! When I was in school they taught me 1 was a prime number.

Ciro De Luca - 3 years, 9 months ago

Thanks for the solution. Using $n$ for a number and its length in decimal representation at the same time is confusing however.

David Mickisch - 3 years, 9 months ago

Log in to reply

Thanks, edited

Marco Brezzi - 3 years, 9 months ago

Given the Challenge Master Note, it seems that, since the problem did not exclude 1 explicitly, as it should have, nor exclude trivial answers, it is not appropriate to deny 1 as an acceptable response. Otherwise, it's a trap.

Bob Jarvis - 3 years, 9 months ago

Log in to reply

Right, this is a trap question that isn't specific enough. The answer is intuitively obvious if 1 is excluded.

Rick Tollefson - 3 years, 9 months ago

What about 1

Matt Howell - 3 years, 9 months ago

Log in to reply

As I already said, 1 1 is not a prime number so you can't give it to the machine

Marco Brezzi - 3 years, 9 months ago

But, the first one (11) is a prime

Jivesh Kesar - 3 years, 9 months ago

Log in to reply

The machine can produce 11 11 only when the input is 1 1 . But 1 1 is not a prime number so the machine doesn't accept it

Marco Brezzi - 3 years, 9 months ago
Isaac Browne
Aug 21, 2017

Another nice way of seeing this relationship without relying on divisibility rules is using the fact that x + 1 ( x + 1 ) 2 n 1 x+1|(x+1)^{2n-1} as follows. Let the prime number be

p = a n 1 0 n + a n 1 1 0 n 1 + . . . + a 1 1 0 1 + a 0 p=a_n*10^n+a_{n-1}*10^{n-1}+...+a_1*10^1+a_0

Then the new number is

n = i = 0 n a i ( 1 0 i ) ( 1 + 1 0 2 n + 1 2 i ) ) n=\sum_{i=0}^{n} a_i \cdot (10^i) (1+10^{2n+1-2i)})

Since each one of these parts of the sum is divisble by 11, as 1 + 10 1 + 1 0 2 n 1 1+10|1+10^{2n-1} , the whole sum is also divisible by eleven, and since n n is not 11 (1 is not prime), n n will always be composite.

How did you get the new number?

Praneeth Reddy - 3 years, 9 months ago

If you look at it, you can see it makes an a.0 as the ones digit and the 10^2n+1 digit, the a.1 as the tens digit and the 10^2n digit, and so on. I just combined like a.i terms and factored out the 10^i.

Isaac Browne - 3 years, 9 months ago

It looks like you missed some braces in the exponentiation: ( x + 1 ) 2 n 1 (x+1)^2n-1 should be ( x + 1 ) 2 n 1 (x+1)^{2n-1} .

Tom Verhoeff - 3 years, 9 months ago

Log in to reply

Yep, thanks!

Isaac Browne - 3 years, 9 months ago

Your formula is for the reversed number attached to the left, for the case at hand the terms would be a i ( 1 0 n + 1 + i + 1 0 n i ) a_i (10^{n+1+i} + 10^{n-i}) , which factorizes into a i 1 0 n i ( 1 + 1 0 2 i + 1 ) a_i 10^{n-i} (1 + 10^{2i+1}) .

M B - 3 years, 9 months ago
Deep Shah
Aug 23, 2017

If you closely observe, each number will be divisible by 11. Hence, there's just no question of the number being a prime.

Be careful: it is easy to observe a few cases but to generalize this to all cases is much harder, but more rigorous. Keep in mind that we cannot jump to conclusions about a few cases and make them represent all cases.

Zach Abueg - 3 years, 9 months ago

You would need to prove that each number will be divisible by 11.

javi jee - 3 years, 9 months ago

What about 3

Charles Fischer - 3 years, 9 months ago

Log in to reply

if you reverse the 3 and add it to the end of the other 3 you get 33

Laura Gao - 3 years, 3 months ago
Jimmy Kudo
Aug 27, 2017

I checked every prime up to 139 and found no solutions. At some point I had to determine this pattern would likely continue. Though, I don't have a way to write a proof.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...