Dodging Triangles

Number Theory Level 4

What are the last three digits of the $10000^\text{th}$ non-triangular natural number?

A triangular number is one of the form $\dfrac{n(n+1)}{2}$ for some positive integer $n$ .

The answer is 141.

3 solutions

Finn Hulse
May 13, 2014

We can use the Principle of Inclusion-Exclusion or just PIE. There are 10000 natural numbers that we're going to sort through. For each triangular number that we find, it's going to increase the 10000th non-trianglular number by 1 (convince yourself this is true). To illustrate what I mean, consider the following example:

Find the 10th non-triangular number

Let's look at the first few triangular numbers. They are 1, 3, 6, 10, 15, etc. Think about it like this. We have listed:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10

As of now, our desired answer is 10, since we haven't found any triangular numbers. If we realize that 1 is indeed a triangular number, our list becomes

2, 3, 4, 5, 6, 7, 8, 9, 10, 11

Notice how because we found that one, the desired answer (the 10th non-triangular number) has increased by 1. If we realized that 3 is another triangular number, our list becomes

2, 4, 5, 6, 7, 8, 9, 10, 11, 12

Which again raises our answer by 1. Eliminating 6 and 10, we get

2, 4, 5, 7, 8, 9, 11, 12, 13, 14

And thus our desired answer is $\boxed{14}$ for this problem.

Do you notice anything about our answer? It's the number of terms we're considering (which is 10) plus the number of triangular numbers less than or equal to 10 (which is 4).

Can we apply this to our problem here?

Let's try. We'll first set $\dfrac{n(n+1)}{2}$ equal to 10000. Solving produces

$n\approx 140.92, -141.92$

Which means that there are 140 triangular numbers beneath 10000. So our answer would just be the last three digits of $10000+140$ which is 140, right?

Wrong. Remember how in our example the answer was 14? Well, if there had been one more triangular number, the answer would have changed to 15, which is triangular and would make the result 16 instead! This isn't the case, obviously, but it is for 10000. So let's plug in 141. This produces $\frac{(141)(141+1)}{2}$ . That's 10011! Because the answer that we got before was 10140, this is another one we have to count since it's less than 10140, which raises our answer to 10141! Let's check the next highest case, 142. If this is above 10141, we're set and our answer is 141. Indeed, plugging this into the expression produces 10153, which is larger than 10141 and thus isn't counted.

Thus our final answer is $\boxed{141}$ . @Walker Anderson I saw that you had marked this problem as "Solution-Free", so I posted one for you. Thanks for being awesome! :D

Soumava Pal
Mar 6, 2016

It can be proved that the sequence that just misses the triangular numbers is given by $a_n=[n+\sqrt{2n}]$

where [x] is the greatest integer function.

I believe you are mistaken. Your formula hits 4 triangular numbers in the first 16 terms! $a_4=6 , a_7=10 , a_{11}=15 , a_{16}=21$ - Maybe something is missing.

After consulting OEIS, I think a better candidate for your sequence is: $a_n=n+\lfloor .5+\sqrt {2n} \rfloor$

Using this sequence formula the solution to the problem is simple: $a_{10000}=10000+\lfloor .5+\sqrt {20000} \rfloor =10000+141=10141$

The last 3 digits are $\boxed { \boxed {141}}$ The FloorFunction piece "rounds to the nearest integer" instead of just chopping off the fractional part. Without the rounding tweak, the formula hits some triangular numbers like $a_4=6$ as your formula did. With rounding, $a_4=7$ and you 'dodge' the triangular number 6.

Bob Kadylo - 5 years, 1 month ago

Faisal Basha
Mar 1, 2015

I wrote a program to solve this

Dodging Triangles

The answer is 141.

3 solutions

0 pending reports