South African Mathematics Olympiad Third Round

$6123$ is the smallest number starting with a $6$ and $3621$ is the largest number starting with a $3$. The difference between these is $6123-3621=2502$. Adjacent numbers between $1236$ and $3621$ will be less than $2500$ apart, while adjacent numbers larger than $6123$ will be less than $1000$ apart. Thus $2502$.