Easier than you think
When you list the integers from 1 to 100, how many 7's have you written down?
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.
1 solution
Moderator note:
This is the most simplistic approach.
Bonus question : What would the answer be if I replace the number 100 by 1000? How about 10000 instead? Can you find a pattern?
In response to @Calvin Lin : I have added a general form of the solution , is it correct?
Log in to reply
That's a really complicated number to evaluate.
The question can be answered in 5 seconds, with the correct interpretation.
Log in to reply
I was just very keen to bring the general form through combinatorics, and I agree the answer can be found in less than 5 seconds , as the pattern goes like 1 , 2 0 , 3 0 0 , 4 0 0 0 , 5 0 0 0 0 . . . . . .
Log in to reply
@Siddharth Bhatnagar – Right. What is the simple one-line reasoning for that?
Hint: Rule of sum/product
Log in to reply
@Calvin Lin – reasoning : Say, if we require the number of occurences of a digit y before 1 0 n , then its clear
we have n places to fill, with atleast one occurence of y anywhere out of the n places and the rest n − 1 places are to be filled with any of [ 0 , 9 ] ( ten choices )
Thus by rule of products, we have n × 1 0 n − 1 as the total number of occurences .
Log in to reply
@Siddharth Bhatnagar – Different idea for same formula:
a n = 1 0 ⋅ a n − 1 + 1 0 n − 1 because in the last n − 1 digits, it appears a n − 1 times for each of the first digit, which is 1 0 ⋅ a n − 1 , and then you add the first 7 for all 1 0 n − 1 numbers between 700...0 and 799...9.
It's then easy to show that a n = n ⋅ 1 0 n − 1 .
Log in to reply
@Laurent Shorts – Indeed.
If we wanted to count the number of times that the digit (say) 7 appears in the kth position, we can set the remaining n − 1 digits to be anything from 0 to 9, giving us 1 0 n − 1 possibilities. Multiplying by the number of positions, the answer is n × 1 0 n − 1 .
{ 7 , 1 7 , 2 7 , 3 7 , 4 7 , 5 7 , 6 7 , 7 0 , 7 1 , 7 2 , 7 3 , 7 4 , 7 5 , 7 6 , 7 7 , 7 8 , 7 9 , 8 7 , 9 7 } are the natural numbers less than 1 0 0 and contain 7 as a digit.
NOTE : 7 7 has two sevens.
_____________________________________________________________________________
As an answer to Challenge master , I generalized the number of times a particular digit (non-zero)appears before 1 0 n
ξ ( 1 0 n ) = r = 1 ∑ n r ( r n ) 9 n − r