Количество чисел в [1..N] с тройками (девятками)

[Gh0stik]

День добрый.
Наткнулся на вроде бы классическую задачу, да вот что-то запутался.

Необходимо найти сколько натуральных чисел от 1 до N содержат:
а) хотя бы одну цифру 3
б) хотя бы одну цифру 9.

Задача конечно решается от противного: необходимо найти количество чисел БЕЗ 3 (9). Для отрезков вида [1..$10^k$] решение понятно.
Количество $(S)$ чисел без троек находим:
[1..10)$= 8$
[10..100)$ = 8*9$
[100..1000)$ = 8*9^2$
...
$[10^{k-1}..10^k$) = 8*9^{k-1}$
Т.е. $S=8+8*9^1+8*9^2+\dots+8*9^{k-1}$

А искомая величина равна (количество чисел хотя бы с одной цифрой 3): $10^k - S$.

Но вот когда N равно произвольному числу получаются проблемы. Например для $N=43929$ (числа с цифрой 3) ответ должен быть 22060 (написал специально циклическую программу).
А вот при ручной проверке такой результат НЕ получается:
$[1..10000) = 8+8*9+9*9^2 +8*9^3$
$[10000..40000) = 2*9^4$
$[40000..43000) = 3*9^3$
$[43000..43900) = 8*9^2$
$[43900..43920) = 2*9$
$[43920..43929] = 9$
После вычислений получим: $43929 - (8(1+9+9^2+9^3)+2*9^4+3*9^3+8*9^2+2*9+9) = 21385$

Как видим результаты различны...

Подскажите пожалуйста в чем мое заблуждение, возможно есть другой более простой метод решения данных задач.
Заранее благодарен за любую помощь.

[venco]

Все числа начиная с 43000 содержат тройку.

[megamix62]

$(10000..40000) = 2 \cdot 9^4$

[Gh0stik]

megamix62 в сообщении #680170 писал(а):

$(10000..40000) = 2 \cdot 9^4$

Потому что на первую позиций можно поставить только цифры 1 и 2 (3 - исключаем, 4 не входит в интервал), а остальные 4 позиции каждую из них можно заполнить 9 вариантами (0..9, исключая цифру 3).

-- 06.02.2013, 00:42 --

venco в сообщении #680129 писал(а):

Все числа начиная с 43000 содержат тройку.

Большое спасибо за найденную ошибку! .

Но, может для произвольных $N$ есть более элегантное решение?