Think small

What is the smallest (positive) prime number that divides

1 + 12 + 123 + 1234 + 12345 + 123456 + 1234567 + 12345678 + 123456789 + 1234567890 ? 1 + 12 + 123 + 1234 + 12345 + 123456\\ + 1234567 + 12345678 + 123456789 + 1234567890?

Details and assumptions

There are 10 terms in the expression, and the last number is 1234567890. To ensure that you see the entire equation, scroll till you see the question mark (?).


The answer is 3.

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.

12 solutions

Daniel Chiu
Oct 6, 2013

We can see that the number is odd by adding the last digits. By adding all the digits, the number is a multiple of 3 \boxed{3} .

Moderator note:

I like this proof the best, because it explains how to determine the smallest prime. Essentially, you have to test all the primes starting from the smallest (namely 2).

Solutions which focused on showing that the sum is a multiple of 3, tend to overlook that they needed to show that no smaller prime number divides it.

What about number 1 it divides all the nubers &its least than 3? Thank u 4 help

Mahdi Al-kawaz - 7 years, 8 months ago

Log in to reply

1 is not a prime number. If it was, then the prime factorizations of any whole number would have infinite zeros, and that doesn't end well. There are other reasons too, but remember, 1 is not prime!

Darryl Yeo - 7 years, 8 months ago

Log in to reply

*infinite ones

Darryl Yeo - 7 years, 8 months ago

Yeah...I translated wrong..my English not very well..but thanks:)

Mahdi Al-kawaz - 7 years, 8 months ago

Log in to reply

@Mahdi Al-kawaz Sure.

Darryl Yeo - 7 years, 8 months ago

the last digit give u 5 is it divisible by 3?

Lau Yie Hang - 7 years, 8 months ago

Log in to reply

You use the last digit to find the number is not divisible by 2.

You use the sum of the digits to find the number is divisible by 3.

Daniel Chiu - 7 years, 8 months ago

leat prime...try from leat 2 is nt disivisible...as it is od..so answer must be 3.

Harshavardhan Barlanka - 7 years, 8 months ago

but wat bout it?

Aditya Agarwal - 7 years, 8 months ago
Akshat Jain
Oct 9, 2013

Let me keep it very very simple!

Let the given expression be equal to x x .

By applying the rule of divisibility of 3 3 , we know that a number is divisible by 3 3 , if the sum of its digits is divisible by three. Applying this, we get that in the given expression, the 2 n d 2^{nd} , 3 r d 3^{rd} , 5 t h 5^{th} , 6 t h 6^{th} , 8 t h 8^{th} , 9 t h 9^{th} and 1 0 t h 10^{th} terms are divisible by 3 3 . And thus, the remaining expression, that is 1 + 1234 + 1234567 1 + 1234 + 1234567 will be left out as remainder.

So, we can write it as-

x 3 ( m o d [ 1 + 1234 + 1234567 ] ) x \equiv 3 \pmod{ [1 + 1234 + 1234567] }

x 3 ( m o d 1235802 ) x \equiv 3 \pmod{1235802}

Again applying the rule of divisibility of 3 3 , we get that 1235802 1235802 is also divisible by 3 3 . Therefore,

x 3 ( m o d 0 ) x \equiv 3 \pmod{0}

Hence, we get that 3 \fbox{3} is the smallest prime number that divides the given number x x .

Let me keep it very simple

Well, you could have made it more simple by simply summing up their digits. :)

Sreejato Bhattacharya - 7 years, 8 months ago

Log in to reply

But that would have went against the conscience of the question! That's not how one should solve a problem! The main motive should be to explore the problem, rather than just getting the answer by any marshy method. :)

Akshat Jain - 7 years, 8 months ago

Log in to reply

See dude, although I haven't been able to grasp the concept of "CONGRUENCES" very well, I feel quite obliged to inform you that from the above solution of yours some of the statements are absolutely wrong. Such as : x \equiv 3 \pmod{1+1234+1234567} - Acc. to me, It should have been x \equiv 1+1234+1234567 \pmod{3} and so the remainders are as such which are further divisible by 3 and hence the whole no. itself is divisible by 3. That accounts for the errors though I comply with Sreejato B. as to the concept of adding the digits. It's not any "MARSHY" method you got here, it's purely a game of concise and clear thinking. NOTE: If u still think that I m wrong regarding the CONGRUENCES concept and the correction, plz inform me so.

Mihir A - 7 years, 8 months ago

Log in to reply

@Mihir A Can you write the math part in latex? I couldn't really catch it. Enclose the statements in \ ( \ ).

Akshat Jain - 7 years, 8 months ago

Log in to reply

@Akshat Jain Yea, Thnx Sreejato. Srry for the mess up though. x ( 1 + 1234 + 1234567 ) ( m o d 3 ) x \equiv (1+1234+1234567) \pmod{3} Further, the remainder is (1+1234+1234567) but that too is divisible by 3 so ultimately the whole no. is divisible by 3.

Mihir A - 7 years, 8 months ago

Log in to reply

@Mihir A Got it.

Akshat Jain - 7 years, 7 months ago

@Mihir A What he meant is that you messed up somewhere, and interchanged the terms between ( m o d ) \pmod{} and outside them. That was a small typo, I think. :)

Sreejato Bhattacharya - 7 years, 8 months ago

Log in to reply

@Sreejato Bhattacharya Oh. I'm really sorry for that!

Akshat Jain - 7 years, 8 months ago

What I meant is that you simply could have calculated the digit sum of each term, and note that N S 10 ( N ) ( m o d 3 ) N \equiv S_{10}(N) \pmod{3} , (where S 10 ( N ) S_{10}(N) denotes the digit sum of N N in decimal base) for all N Z N \in \mathbb{Z} , which is an easy consequence of the fact that 1 0 n 1 ( m o d 3 ) 10^n \equiv 1 \pmod{3} for all n N n \in \mathbb{N} .

Sreejato Bhattacharya - 7 years, 8 months ago

Log in to reply

@Sreejato Bhattacharya But that would somewhat mean the same. Adding all the numbers and dividing by 3?

Akshat Jain - 7 years, 8 months ago

Log in to reply

@Akshat Jain Just apply the divisibility rule of 3 3 , it's lot simpler. Also note that your solution is incomplete, as it provides no justification why 2 x 2 \nmid x .

Sreejato Bhattacharya - 7 years, 8 months ago

cause 2 is first prime number, we must find are these terms is divisible by 2? so we just add the last digits of this terms:

1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 0 1+2+3+4+5+6+7+8+9+0 = 45 45 which not divisible by 2.

now we try 3 , second prime number , to make sure this term is divisible by 3 , we must add of ALL digits ,

1 + 3 + 6 + 10 + 15 + 21 + 28 + 36 + 45 + 45 1+3+6+10+15+21+28+36+45+45 = 210 210 , which 210 is DIVISIBLE by 3 and it is the smallest possible so the answer is 3 3

Darryl Yeo
Oct 6, 2013

Take the prime factorization of every number in this sum and you'll notice that they are all multiples of 3 3 except for 1 1 , 1234 1234 , and 1234567 1234567 . Adding these three numbers gives you a multiple of 3 3 as well, making the entire sum divisible by 3 3 , which is a prime number. Thus the answer is 3 3 .

(This makes it the smallest because the sum, and odd number, is not divisible by the only smaller prime, 2.)

Moderator note:

Remember that when you want to show that p p is the minimum number that satisfies a condition, you not only need to show that p p satisfies it, you also must show that no smaller number satisfies the condition.

Julio Reyes
Oct 6, 2013

Upon adding the terms we get:

1 + 12 + 123 + 1234 + 12345 + 123456 + 1234567 + 12345678 + 123456789 + 1234567890 = 1371742095 \begin{matrix} 1+12+123+1234+12345+123456+\\1234567+ 12345678+123456789+1234567890 \end{matrix} = 1371742095

Using the rules of divisibility we can start checking for prime numbers that divide 12371742095 . Right away we know that 5 divides it since the number ends in 5 .

The only prime smaller than 5 is 3 . The rule for divisibility by 3 is:

Add up all the digits of the number. If the sum is divisible by 3, then so is the number.

1 + 3 + 7 + 1 + 7 + 4 + 2 + 0 + 9 + 5 = 39 39 = 13 3 1+3+7+1+7+4+2+0+9+5 = 39 \quad \Rightarrow \quad 39 = 13 \cdot 3

So the smallest prime number that divides the expression is 3 \fbox{3} .

I forgot to mention, that the sum of the expression is not divisible by 2 since the number is odd.

Julio Reyes - 7 years, 8 months ago

I think its more complicated because you have to add big numbers. :D my opinion. There's a simpler solution than this one :D

Matthew Franz Oco - 7 years, 8 months ago

hello What about 5??? Look only the last digit... If it's 0 or 5 we can divide it with 5

Jithu Sajith - 7 years, 8 months ago

Log in to reply

They asked for the smallest prime number, didn't they? So I completely agree with Julio here.

Kenneth Lee Wen - 7 years, 8 months ago

Like Kenneth mentioned, they asked for the smallest prime number. But you are right, 5 works. So you just have to check if 2 or 3 work. In this case 3 also worked but not 2, so 3 is the answer since its smaller than 5.

Julio Reyes - 7 years, 8 months ago

Log in to reply

ok thanks for your answer

Jithu Sajith - 7 years, 8 months ago
Abubakarr Yillah
Jan 8, 2014

1 + 12 + 123 + 1234 + 12345 + 123456 + 1234567 + 12345678 + 123456789 + 1234567890 = 1371742095 {1}+{12}+{123}+{1234}+{12345}+{123456}+{1234567}+{12345678}+{123456789}+{1234567890}={1371742095}

Since the last digit of the sum is *5, this excludes 2 as a possible divisor.*

The next prime number after *2 is 3 and* 1371742095 3 = 457247365 \frac{1371742095}{3}={457247365}

Hence 3 is the smallest positive prime number that divides the above sum.

I also used the same method!

kowshik dey - 7 years, 3 months ago

Log in to reply

me too!!

Apurv Rajput - 7 years, 2 months ago
Angel Leon
Oct 9, 2013

solution in python. gathered an ordered list of prime numbers

>>> bigNumber = 1 + 12 + 123 + 1234 + 12345 + 123456 + 1234567 + 12345678 + 123456789 + 1234567890
>>> 

>>> primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

>>> 

>>> for x in primes:
...   if bigNumber % x == 0:
...     print x
...     break
... 
3
Iranna Hubballi
Apr 24, 2014

same method!

Vaibhav Reddy
Oct 12, 2013

the sums would be * (1+3 + 6 + 1+ 6 + 3 + 1 + 9 + 9 + 9) mod 9 = 3 mod 9 * hence it is divisible by 3 a prime number

Jeremiah Jocson
Oct 12, 2013

if we sum all the integer the result is 1,371,742,095 then if we see the ones digit is end in digit "5" so it assume the answer is 5 because it is divisible by five but five is not the smallest prime number so the answer will be 2 or 3 only,, try trial and error and you'll get 3.... then the aswer is THREE (3),,

Sanjay Banerji
Oct 12, 2013

See the last digit and add all...

You get 5 as the last digit of the expression...

Put 5 in the answer box........Brilliant says wrong answer

Only 3 is left......cant be 2....

What if you had just one try?

Vikram Waradpande - 7 years, 8 months ago
Kenneth Lee Wen
Oct 8, 2013

Just add them up, how difficult can it be?

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...