computing count of numbers from 1 to 10 ^ d - 1 , d = 0 a [ 0 ] = 0 ; d = 1 a [ 1 ] = count of numbers from 0 to 9 is 1 d = 2 a [ 2 ] = count of numbers from 0 to 99 is a [ 1 ] * 9 + 10 = 19 d = 3 a [ 3 ] = count of numbers from 0 to 999 is a [ 2 ] * 19 + 100 = 171
$ a = array_fill ( 0 , $ d + 1 , NULL ) ; $ a [ 0 ] = 0 ; $ a [ 1 ] = 1 ; for ( $ i = 2 ; $ i <= $ d ; $ i ++ ) $ a [ $ i ] = $ a [ $ i - 1 ] * 9 + ceil ( pow ( 10 , $ i - 1 ) ) ;