Длина числа

Примечание: Если вы не видите математические формулы ниже см. сюда.

Пару дней назад меня на работе коллега, уроженец Израиля, сабра, спросил, как бы я нашёл "длину числа" $n$ ($0<n\in \mathbb{N}$) написанную в десятеричной системе исчисления? Например, "длина числа" 578 равняется трём, так как нужно три цифры чтобы записать такое число. Подумав секунд пять я взял ручку и и бумагу и начала писать ответь. Сначала я вспомнил, что это $\text{O(log n)}$, но в данном случае, этого было недостаточно, нужна была точная формула. Я также помнил, что нужно округлить число либо вверх, либо вниз, и что нужно добавить единицу. Этого оказалось достаточным, чтобы через минуту восстановить формулу $\text{1+[lg n]}$, где $\left[x\right]$ обозначает целая часть от $x$ (например, $[2,3]=2;[15,9]=15)$, а $\text{lg n}$ это десятичный логарифм, т.е. $\text{lg n}=lo{g}_{10}n$.

Коллега на меня недоверчиво посмотрел и спросил, откуда я знаю это формулу.

Ниже есть продолжение.

На что я ему резонно ответил, что это простая школьная математика, и эту формулу я ещё со школы помню, очевидно я её прочитал в одной из книжек для школьников. На что он заметил, что, быть может, в бывшем СССР дети и читают такие книжки, но он в детстве подобных книжек не читал. Я ему решил объяснить в чём тут дело. В самом деле, говорил я ему, возьмём любое число, к примеру, $137$. $137=1*10^2+3*10^1+7*10^0$ "Длина числа" будет $2+1=3$. Таким образом, нам достаточно узнать показатель степени полинома ($2$) и прибавить к нему единицу. Очевидно, что показатель полинома $3$ будет тогда и только тогда числа $100\le n<1000$, не трудно заметить, что $100=10^2\le n<10^3=1000$. Здесь, мне показалось уж совсем просто заметить, что показатель степени полинома есть десятичный логарифм числа, округлённый до ближайшего целого числа (напомню, все числа в рассмотрении натуральные), т.е. $\text{[lg n]}$.

К моему удивлению, это история имела продолжение. Сегодня, этот коллега ко мне подошёл и сказал, что среди его знакомых ни один не знаком с "моей" формулой и попросил объяснить откуда она берётся. Я был слегка шокирован. Ладно, я понимаю, человек может не помнить этой формулы, может быть он его также никогда и не знал, хотя последнее для меня очень странно, но я ведь ему объяснил на пальцах как её вести. Да, объяснение не было строгим, но не в этом была его претензия, да, я оставил довольно широкие "лакуны" в моём объяснении, но как он не смог их заполнить? Более того, почему никто ему не смог в это помочь?

Пришлось рисовать ему табличку:

число	"длина числа"
7	1
12	2
675	3
6784	4
...

Далее я произнёс фразу, что "длина числа" увеличивается на единицу всякий раз когда число увеличивается примерно в десять раз, вывод - это логарифм.

Как оказалось и этого оказалось недостаточно. Очевидно, что товарищ забыл, что такое логарифм...Я ему ещё раз попробовал объяснить уже используя "круглые цифры" и наблюдение, что это является "нижней" границей для всех чисел с "одинаковым количеством цифр".

число	"длина числа"
1	1
10=101	2=1+1
100=102	3=1+2
10=103	4=1+3
...

Не заметить, что с увеличением показателя степени на один (а это "нижняя граница") "длина числа" увеличивается на один по-моему нельзя. В принципе приведённых доводов достаточно уже, чтобы это оформить как формальное доказательство (нужно доказать сначала, что для чисел $10^k<n\le 10^{k+1}$ "длина числа" не меняется, а затем использовать индукцию по показателя степени полинома и формулу $\text{lg 10x=lg10+lg x=1+lg x}$). Про индукцию я ему не сказал, но эту формулу я ему написал. На него это не произвело никакого впечатления. Очень странно. Ведь функцию логарифма можно определить через набор свойств и доказав, что существует только одна функция, которая удовлетворяет этим условиям (так, в некоторых областях определяется показательная функция $e^x$, к примеру). Это условие является одним из базовых, натолкнувшись на него лично я думаю сразу про логарифм. Но это я не много вышел за рамки школьной программы. Можно то же самое показать и оставаясь в рамках школьной программы. Как известно, логарифм используется для "превращения" умножения в сложение. Этот трюк использовали в древности, когда надо было перемножить два больших числа (очевидно, об этом, мой коллега не знает). Этот трюк также используется в различных доказательствах вне школьной программы. Состоит он том, что

$lgab=lga+lgb$ (это следствие $10^a*10^b=10^{a+b}$)

и таким образом

$ab=10^{lgab}=10^{(lga+lgb)}$

Таким образом чтобы перемножить два числа, нужно сложить их десятичные логарифмы и возвести 10 в полученную степень. Замечание: вместо основания 10 можно использовать любое другое основание. Значения логарифмом находились по специально составленных таблицам (типа таблиц Брадеса), также по таблицам находилось значения возведения в степень.