This number is huge!

Notice that $72=8\times9$

We will show that the huge number H is divisible by both 8 and 9 and so it must be divisible by 72, and the remainder is zero.

First write $H=k\times1000+16=8\times(125k+2)$ to see thet H is divisible by 8.

The remainder when a number is divided by 9 equals its digital root. The digital root is the sum of all the digits of the number reduced modulo 9. The key insight is that the place values of the digits are irrelevant and so the digital root of H is equal to the digital root of

$\sum_{i=1}^{2016}i=1008\times2017$

Since 1008 is a multiple of 9, the digital root of H is zero, or in other words H is divisible by 9.

Now since H is a multiple of both 8 and 9, and they are relatively prime, H is divisible by 72 and the required remainder is $\boxed{0}$

The number is definitely divisible by 8 as the last three digits are. $$ Now,the sum of the single digit numbers is divisible by 9. $$ Now,the two digit numbers are all of the form $\overline{ab}=10a+b$ ,so for all values of $a$ ,the sum of the values of $b$ ,are divisible by 9 as it varies from 0-9.Similarly,for $a$ ,it also varies from 1-9,hence 10(1+2+..9) which is also divisible by 9.This can be done for 3 digit numbers too.I am currently on phone so will post the full solution later on.

72=2^3*3^2 The number above is divisible by 2^3 because the number formed by the last three digits is divisible by 8 and also by 9 because the sum of every set of 9 positive consecutive integers is divisible by 9 and there are 224 sets of nine positive consecutive integers :). Thus 12345678910111213...20122013201420152016 is divisible by 72.