This counting puzzle from Matt Parker looks like the kind you should write a program to solve:

Imagine f(n) that counts the occurrences of the digit “1″ in {1,2,3…n}.

Eg f(13)=6

For what values of n does f(n)=n?

That’s all well and good – until you find yourself in a car park, waiting twenty minutes for a taxi. Under these circumstances, it’s reasonable to consider the first few values of f(n)…

Well, f(n)=1 for n=1,2,3,…9. Then you get a lot of changes in a row – f(10)=2, f(11)=4 and so on up to f(19)=12. And, since the next changes are far apart – 21,31,41… – that’s the closest f(n) and n will be for some time.

Now, let’s look at 1,2 and 3 digit n. We know that f(9)=1, but also, since 1 appears 10 times in each column, it’s easy to see that f(99)=20 and, similarly, f(999)=300. This pattern allows you to calculate f(n) for large values such as n=199,999 quite easily.

There’s further discussion of this problem on Twitter in the hashtag #count1s.

I think my taxi’s here, so, here’s some python:

# f(n) = how many times the digit '1' appears in {1,2,3,...,n}
# when does f(n)=n?

n = 1
f = 0
while 1 :
	f += str(n).count( "1" )
	if f == n :
		print n
	n += 1