Almost 12345654321

Number Theory Level 3

Is ${\color{#E81990}1}{\color{grey}{2}}{\color{#20A900}{3}}{\color{#3D99F6}{4}}{\color{#D61F06}555}{\color{#3D99F6}{4}}{\color{#20A900}{3}}{\color{grey}{2}}{\color{#E81990}1}$ prime?

Hint: You may use the fact that $111111 \times 111111 = {\color{#E81990}1}{\color{grey}{2}}{\color{#20A900}{3}}{\color{#3D99F6}{4}}{\color{#D61F06}5}6{\color{#D61F06}5}{\color{#3D99F6}{4}}{\color{#20A900}{3}}{\color{grey}{2}}{\color{#E81990}1}$ . This is similar to, but not identical to the above number, due to the middle $6$ .

Yes No

8 solutions

Chung Kevin
Mar 1, 2017

I created this problem by thinking of why $111111 \times 111111 = 12345654321$ . If we wrote out the multiplication, we would immediately see that

$\begin{array} { llllllllllllllll} &&&&&&&&1&1&1&1&1&1\\ \times&&&&&&&&1&1&1&1&1&1\\ \hline &&&&&&&&1&1&1&1&1&1\\ &&&&&&&1&1&1&1&1&1\\ &&&&&&1&1&1&1&1&1\\ &&&&&1&1&1&1&1&1\\ &&&&1&1&1&1&1&1\\ &&&1&1&1&1&1&1\\ \hline &&&1&2&3&4&5&6&5&4&3&2&1\\ \end{array}$

That led me to think about how we can get similar patterns by chaging the number of 1's. For example,

$\begin{array} { llllllllllllllll} &&&&&&&&&&1&1&1&1&1\\ \times&&&&&&&&1&1&1&1&1&1&1\\ \hline &&&&&&&&&&1&1&1&1&1\\ &&&&&&&&&1&1&1&1&1\\ &&&&&&&&1&1&1&1&1\\ &&&&&&&1&1&1&1&1\\ &&&&&&1&1&1&1&1\\ &&&&&1&1&1&1&1\\ &&&&1&1&1&1&1\\ \hline &&&&1&2&3&4&5&5&5&4&3&2&1\\ \end{array}$

Hence, this number is not prime. We have $12345554321 = 11111 \times 1111111 = 41 \times 239 \times 271 \times 4649$ .

Nice solution! I answered "No" because if the number were prime, the solution would have been ugly. :P

Shourya Pandey - 4 years, 3 months ago

Haha nice antisolution. To be honest, I also did the same thing. I also thought "No way this problem is good if the number ends up being a prime"

Pi Han Goh - 4 years, 3 months ago

That's a pretty amazing pattern! I wouldn't have known how to factorize this (other than using a calculator).

Calvin Lin Staff - 4 years, 3 months ago

Rocco Davino
Mar 5, 2017

Another approach:

$\begin{aligned} 12345654321 & = & 111,111^2 \\ & = & ( 100, 000 + 11,111 )( 100,000 + 11,111 ) \\ & = & 100,000^2 + 2 \cdot 11, 111 \cdot 100,000 + 11, 111^2. \end{aligned}$

So we have:

$\begin{aligned} 12345554321 & = & (100,000^2 + 2 \cdot 11, 111 \cdot 100,000 + 11, 111^2) - 100,000 \\ & = & 100,000(100,000 - 1) + 2 \cdot 11, 111 \cdot 100,000 + 11, 111^2 \\ & = & 100, 000 \cdot 99,999 + 2 \cdot 11, 111 \cdot 100,000 + 11, 111^2 \\ & = & 100,000 \cdot 11,111 \cdot 9 + 2 \cdot 11, 111 \cdot 100,000 + 11, 111^2 \\ \end{aligned}$

and thus

$12345554321 = 11,111( 100,000 \cdot 9 + 2 \cdot 100,000 + 11,111)$ .

Love this. I tried to do something like this but didn't succeed.

Chung Kevin - 4 years, 3 months ago

I think there's a typo in the second equation: should it be $111,111^2$ ?

Christopher Boo - 4 years, 3 months ago

12345554321 is a prime number . Can you check that again !!

Mashuk Mak - 4 years, 3 months ago

12345554321 = 11,111 * 1,111,111, so it is composite. Therefore, it is not prime.

Rocco Davino - 4 years, 3 months ago

Dong kwan Yoo
Mar 5, 2017

Let $A = 100 000$ . Notice that $(10A - 1 ) / 9 = 111 111$ . Thus, we have:
$12345554321 \\ = 111111^2 - A \\ = (10A-1)^2 / 81 - A \\ = 1/81 * ( 100A^2 - 101A +1) \\ = 1/81 * (A-1)(100A-1)$
so, that is not prime.

That's a nice way to factorize the number 12345554321. I think it would be clearer if you substituted the value of A back in the expression at the end and simplify it. This will make it clear that 81 divides the numerator, and the numerator is still composite after it has been divided by 81.

Pranshu Gaba - 4 years, 3 months ago

Wow, nice factorization! Let $A = 100000$ makes this so much simpler :)

Calvin Lin Staff - 4 years, 3 months ago

It's as simple as knowing 111111 is a factor of 12345554321 means it's not prime.

David Fitzgerald - 4 years, 3 months ago

Hm, but 111111 is not a factor of 12345554321. Let me make that clearer in the question.

Chung Kevin - 4 years, 3 months ago

OH! I can see the difference now. Aha! I thought it seemed frighteningly simple aha!

David Fitzgerald - 4 years, 3 months ago

Love this. I tried to do something like this but didn't succeed.

Chung Kevin - 4 years, 3 months ago

If it is the result of a multiplication, it is not prime.

Carlos Alberto - 4 years, 3 months ago

Yes. So we have to find the multiplication that works.

Note that the multiplication given in the question is for a different value.

Chung Kevin - 4 years, 3 months ago

Timothy Chen
Mar 6, 2017

Honestly all I did was add up the digits ( 1 + 2 + 3 + 4 + 5 + 6 + 5 + 4 + 3 + 2 + 1), which was (3 + 3 + 9 + 6 + 9 + 3 + 3) . When you add them together, you get 36, which is a multiple of 3. Therefore, it is divisible by 3.

(I'm pretty sure this method only works with multiples of 3 and 9)

(I know it's the really stupid way but I was lucky and it worked so I just went along with it)

Hmm, the question wants to check whether $12345{\color{#D61F06}5} 54321$ is prime or not. The sum of its digits is $35$ which tells us that it is not divisible by 3, but does not give us any more information on whether it is prime or composite.

It is a good idea to test divisibility by small numbers while testing if a number is prime. If we are lucky, we would find a divisor and we would be done. Proving a number to be prime is often more tricky.

Pranshu Gaba - 4 years, 3 months ago

All I did was: $13245554321=111111\times 111111-100000 \\ =(11111+100000)\times 111111-100000 \\ =11111\times 111111+100000\times 111111-100000 \\ =11111\times 111111+100000\times (111111-1) \\ =11111\times 111111+100000\times 111110 \\ =11111\times 111111+1000000\times 11111 \\ =11111\times (111111+1000000) \\ =11111\times 1111111.$ \ Thus, not a prime.

Braian Barcelos - 4 years, 3 months ago

Awesome! I like how you have distributed and combined terms to simplify the expression to a product of two numbers.

Pranshu Gaba - 4 years, 3 months ago

Honestly, I noticed that there were a possible 111111 numbers to check and figured that there is no way they expect us to check all of them to determine that it is prime - therefore it is not.

A Former Brilliant Member - 4 years, 3 months ago

Yup, it is always easier with composite numbers than with primes. Even if we just use brute force, for a composite number, we can stop the moment we find a divisor, but for primes, we have to go all the way up to $\sqrt{n}$ .

Pranshu Gaba - 4 years, 3 months ago

Máté Benkő
Mar 10, 2017

function isPrime(value){
  var divider;
  for (var i = 2; i*i<value/2; i++){
    if(value%i == 0){
      divider = i;
        break;
    }
  }
  return divider ? 'It is not prime, first divider is: '+divider : 'It is Prime';
} 
isPrime(12345554321);

Could you explain more on what your program is doing?

Christopher Boo - 4 years, 3 months ago

Moin Khan
Mar 10, 2017

i just added all digits together 1+2+3+4+5+5+5+4+3+2+1=35. it has a 5 in the end so can't be prime.

This is not how divisibility test of 5 works. Consider 23. We get 2 + 3 = 5, but 23 is a prime number.

Pranshu Gaba - 4 years, 3 months ago

David Waldman
Mar 10, 2017

The sum of the integers is divisible by three so the number itself is divine by three

The sum of the digits are 35, so this number is not a multiple of 3.

Chung Kevin - 4 years, 3 months ago

Mo Aboulmagd
Mar 9, 2017

If we just modulo by 100, we are left with 21. Is 21 odd? the answers should be no.

Hm? Can you explain your idea further?

21 is indeed odd, but why does it show that the number is prime, or not prime?

Chung Kevin - 4 years, 3 months ago

Almost 12345654321

8 solutions

0 pending reports