Целочисленные функции

В математике и информатике мы часто сталкиваемся с необходимостью «перевести» вещественные величины в целочисленные термины: подсчитать количество полных шагов, определить номер интервала, выделить остаток от деления или просто отбросить дробную часть. Однако интуитивные идеи вроде округления оказываются недостаточно точными для формального анализа — они либо неоднозначны, либо не обладают нужными алгебраическими или топологическими свойствами.

Именно для строгого и универсального описания таких операций были введены целочисленные функции — прежде всего, функции пола и потолка, а также связанные с ними дробная часть и остаток по модулю. Эти функции, несмотря на кажущуюся простоту, лежат в основе глубоких математических конструкций: от теории делимости и алгоритмов до спектрального анализа чисел, теории вероятности и даже теории игр.

В этом тексте мы систематизируем базовые целочисленные функции, их ключевые свойства и взаимосвязи, а также покажем, как с их помощью моделировать дискретные структуры, возникающие из непрерывных величин.

Пол и потолок

Простое округление не подходит для формальных систем: оно неоднозначно (особенно вблизи полуцелых значений) и не согласуется строго с порядком на числовой прямой. В отличие от таких эвристик, функции пола и потолка, введённые Кеннетом Айверсоном в начале 1960‑х годов, однозначно определены для любого вещественного числа, естественно связаны с неравенствами и позволяют точно переводить аналитические утверждения в дискретные.

Функции пол и потолок

Пол (floor) — функция, округляющее число вниз

\lfloor x \rfloor \defeq \text{наибольшее целое, не превышающее}~ x = \max\limits~ \{ n \in \ZZ : n \le x \}

Потолок (ceil) — функция, округляющее число вверх

\lceil x \rceil \defeq \text{наименьшее целое, не меньшее}~ x = \min\limits~ \{ n \in \ZZ : n \ge x \}

В целых точках значения функций пола и потолка совпадают, а в нецелых точках значения отличаются на $1$ :

\lfloor x \rfloor = x = \lceil x \rceil \Leftrightarrow x \in \ZZ \quad\text{и}\quad \lfloor x \rfloor = \lceil x \rceil - 1 \Leftrightarrow x \notin \ZZ

Симметрия относительно нуля. Функции пола и потолка зеркально связаны: отражение числа относительно нуля «переворачивает» порядок, а значит, меняет и направление округления:

\lfloor -x \rfloor = - \lceil x \rceil \quad\text{и}\quad \lceil -x \rceil = - \lfloor x \rfloor

Эта симметрия часто упрощает доказательства: достаточно разобрать случай $x \ge 0$ , а отрицательный получится автоматически.

Перевод равенств в неравенства. Самое ценное в функциях пола и потолка — их эквивалентные характеристики через неравенства. Например, утверждение $\lfloor x \rfloor = n$ равносильно двум условиям: $n \le x < n+1$ . Это очень удобный инструмент для доказательств, ведь он позволяет нам мгновенно переходить от равенства к системе неравенств, с которой гораздо проще работать. Вот четыре ключевых эквивалентности:

\align{ \lfloor x \rfloor = n &\iff n \le x < n + 1 \\ \lfloor x \rfloor = n &\iff x-1 < n \le x \\ \lceil x \rceil = n &\iff n-1 < x \le n \\ \lceil x \rceil = n &\iff x\le n < x+1 \\ }

Обратите внимание: каждая из эквивалентностей задаёт интервал, в который попадает $x$ , если его пол (или потолок) равен $n$ .

Пол числа всегда не больше самого числа, а потолок числа всегда не меньше самого числа. В сочетании с соответствующими равенствами для целых чисел эти факты дают нам способ немного огрубив неравенство записать его в терминах целых чисел:

\align{ x < n &\iff \lfloor x \rfloor < n \\ n < x&\iff n<\lceil x \rceil \\ x \le n &\iff \lceil x \rceil \le n\\ n \le x &\iff n \le \lfloor x\rfloor }

Давайте разберём простой пример, чтобы закрепить навыки обращения со свойствами функций пола и потолка. Вопрос: верно ли неравенство

\bigl\lfloor \sqrt{\lfloor x \rfloor} \bigr\rfloor = \lfloor \sqrt x \rfloor \quad\text{при}~ x \ge 0

Очевидно, это равенство справедливо, когда $x$ — целое число, ведь тогда $\lfloor x \rfloor = x$ . Но оно также оказывается верным и для $\pi$ , и для $e$ , и для $\vphi$ ... Наша безуспешная попытка найти какой-либо опровергающий пример наводит на мысль, что равенство справедливо и в общем случае. Давайте попробуем его доказать.

Давайте использовать разобранные выше свойства для доказательства. Попробуем каким-либо образом «разобрать» левую часть $\bigl\lfloor \sqrt{\lfloor x \rfloor} \bigr\rfloor$ , избавившись от корня и внешнего пола. Затем уберём внутренний пол $\lfloor x \rfloor$ . А потом вновь «соберём» выражение, но уже в виде $\lfloor \sqrt{x} \rfloor$ .

Пусть $m = \lfloor \sqrt{\lfloor x \rfloor} \rfloor$ . Это целое число.

Перейдём от равенства к двойному неравенству, избавившись от от наружного пола:

m = \bigl\lfloor \sqrt{\lfloor x \rfloor} \bigr\rfloor \implies m \le \sqrt{\lfloor x \rfloor} < m+1

Поскольку все три части этой конструкции неотрицательны, смело возводим их в квадрат, чтобы избавиться от квадратного корня:

m^2 \le \lfloor x \rfloor < (m+1)^2

Теперь избавимся от оставшегося пола, оценив его с обоих сторон. Используем два неравенства $n \le \lfloor x \rfloor \Leftrightarrow n \le x$ и $n < \lfloor x \rfloor \Leftrightarrow n < x$ при $n \in \ZZ$ . Поскольку $m$ — целое число, значит и $m^2$ , и $(m+1)^2$ тоже целые, и эти неравенства мы можем применять.

m^2 \le x < (m+1)^2

А теперь не составляет труда восстановить проделанное в обратном порядке. Извлечем квадратные корни

m \le \sqrt{x} < m+1

А это классическое определение функции пол. Перейдём от неравенства к равенству и получим

m = \lfloor \sqrt{x} \rfloor

Таким образом, мы начали с $m = \bigl\lfloor \sqrt{\lfloor x \rfloor} \bigr\rfloor$ и, используя только наши свойства, пришли к $m = \lfloor \sqrt{x} \rfloor$ . Значит

\bigl\lfloor \sqrt{\lfloor x \rfloor} \bigr\rfloor = \lfloor \sqrt{x} \rfloor

Наше утверждение оказалось верным.

Сколько целых чисел содержится на интервалах: $[a, b]$ , $(a, b]$ и $[a, b)$ при $a, b \in \RR$ и $a \le b$ ?

Сколько чисел в последовательности

1, 2, 3, \dotsc, n

, которые:

a) делятся на

p1

b) делятся на

p2

c) делятся и на

p1

, и на

p2

Выразите ответ через floor.

a) Чему равен

\lceil \lg 35 \rceil

? (

\lg

— двоичный логарифм).

b) Кстати говоря,

35_{10} = 100011_{2}

. Заметьте связь между этим ответом и количеством бит в двоичной записи числа.

c) Верно ли, что для

n \ge 1

количество бит равно

\lfloor \lg n \rfloor + 1

d) Как с помощью функций пола/потолка получить точное равенство для количества бит, работающее и для

n=0

Чему равно количество цифр в десятичной записи натурального числа

N

Приведите такой пример, где

\bigl\lceil \sqrt{\lfloor x \rfloor} \bigr\rceil \ne \bigl\lceil \sqrt{x} \bigr\rceil

Найдите закономерность для чисел, нарушающих это равенство.

Функция пол позволяет нам исследовать удивительные свойства иррациональных чисел.

Задолго до того, как это стало знаменитой математической задачей, лорд Рэлей в своей "Теории звука" изучал, как взаимодействуют несоизмеримые частоты и оказалось, что задача сводится к чистой теории чисел. Мы получаем инструмент, чтобы оцифровать иррациональный процесс и знакомимся с понятием спектра.

Спектр числа

Спектром некоторого вещественного числа $\alpha$ называется бесконечное мультимножество (множество с повторяющимися элементами) целых чисел:

Spec(\alpha) = \bigl\{ \lfloor k\alpha \rfloor \mid \forall\, k \in \NN \bigr\}

Например, для рационального числа $Spec(1/3) = \{ 0, 0, 1, 1, 1, 2, \dotsc \}$ . Но настоящая магия начинается, когда $\alpha$ иррационально.

Рассмотрим, например, два мультимножества:

\align{ Spec(\sqrt{2}) &= \{1, 2, 4, 5, 7, 8, 9, 11, 12, 14, 15, 16, 18, 19, 21, 22, 24, \dotsc \}\\ Spec(2+\sqrt{2}) &= \{3, 6, 10, 13, 17, 20, 23, 27, 30, 34, 37, 40, 44, 47, 51, \dotsc \} }

Более внимательное рассмотрение показывает, что два этих спектра связаны друг с другом гораздо более удивительным образом: получается так, что любое целое положительное число, отсутствующее в одном спектре, присутствует в другом, но никакое число не содержится одновременно в обоих!

Разбиение всех целых положительных чисел

И это действительно так — все целые положительные числа представляют собой объединение непересекающихся множеств

Spec(\sqrt{2}) ~\text{и}~ Spec(2+\sqrt{2})

. Говорят, что эти спектры образуют разбиение всех целых положительных чисел. Строгое доказательство этого красивого факта мы оставляем для самых искушенных читателей.

Сами же спектры иррациональных чисел (такие как $Spec(\sqrt{2})$ ) носят имя последовательностей Битти.

Тот факт, что спектры чисел $\sqrt{2}$ и $2+\sqrt{2}$ идеально дополняют друг друга, не является случайным совпадением. Это проявление жесткого арифметического закона. Чтобы два иррациональных числа могли поделить между собой натуральный ряд, они должны находиться в особой гармонической связи.

Теорема Битти

Пусть $\alpha$ и $\beta$ — положительные иррациональные числа. Множества $Spec(\alpha)$ и $Spec(\beta)$ образуют разбиение множества натуральных чисел $\NN$ тогда и только тогда, когда выполняется соотношение:

\frac{1}{\alpha} + \frac{1}{\beta} = 1

На первый взгляд спектр иррационального числа кажется хаотичным набором целых чисел. Однако функция пола накладывает на него строгие структурные ограничения.

Свойство двух шагов

Рассмотрим упорядоченную последовательность элементов спектра $x_n = \lfloor n\alpha \rfloor$ . Разность между соседними элементами $\Delta_n = x_{n+1} - x_n$ может принимать только два значения:

\Delta_n \in \{ \lfloor \alpha \rfloor, \; \lfloor \alpha \rfloor + 1 \}

Вернемся к нашему примеру с $\alpha = \sqrt{2} \approx 1.41$ . Тогда $\lfloor \alpha \rfloor = 1$ . Значит, шаги в спектре могут быть только $1$ или $2$ .

Последовательности Битти находят красивое применение в анализе Игры Витхоффа.

Представьте две кучки камней. Двое игроков по очереди делают ход. Разрешается два типа ходов:

Взять любое количество камней из одной кучки.
Взять одинаковое количество камней из обеих кучек сразу.

Выигрывает тот, кто забирает последний камень. Анализ показывает, что существует набор проигрышных позиций — если вы в них попали и противник играет оптимально, ваше поражение неизбежно.

Стратегия Витхоффа

Пара чисел $n, m$ для которых $n \le m$ является проигрышной позицией тогда и только тогда, когда она является парой чисел из спектров золотого сечения:

n = \lfloor k \vphi \rfloor, \quad m = \lfloor k \vphi^2 \rfloor

где $\vphi = \frac{1+\sqrt{5}}{2}$ , а $k$ — номер хода. Заметьте, что так как $\frac{1}{\vphi} + \frac{1}{\vphi^2} = 1$ , эти позиции покрывают все возможные варианты, никогда не повторяясь.

Упражнения

Докажите, что если

\alpha < \beta

, то для спектров

Spec(\alpha)\text{ и }Spec(eta)

выполняется следующее: начиная с некоторого номера, каждый элемент

Spec(\alpha)

не превосходит соответствующего элемента

Spec(\beta)

Верно ли, что

Spec(\alpha)

является подмножеством

Spec(\beta)

? (Приведите пример или контрпример).

Докажите, что в спектре любого вещественного числа

\alpha > 1

не могут встречаться два подряд идущих натуральных числа. Какие числа обязательно будут пропущены?

Найдите первые три проигрышные позиции в игре Витхоффа, используя формулу спектров.

Мы только что видели, как функция пол помогает нам анализировать структуры, порожденные иррациональными числами.

Теперь вернемся к целочисленной арифметике. При делении $n\text{ на }m$ функция пол дает нам точное частное: $\lfloor n/m \rfloor$ .

Эта же самая операция, как мы сейчас увидим, служит фундаментом для формального определения остатка — краеугольного камня всей дискретной математики.

Операция взятия остатка

Если $m \text{ и } n$ — целые положительные числа, то частное от деления $m \text{ на } n$ равно $\lfloor n/m \rfloor$ . Нам также полезно иметь обозначение и для остатка от этого деления — обозначим его $n \bmod m$ .

Свяжем воедино:

n = m \cdot \lfloor n/m \rfloor + n \bmod m

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

MOD как остаток от деления

x\bmod y = x - y \lfloor x/y \rfloor

для $x,y \in \RR$

MOD является бинарной операцией. Обратите внимание, что она имеет приоритет выше сложения/вычитания, поэтому скобки намерено опущены. Число после MOD называется модулем, а само выражение $x \bmod y$ читается как «икс по модулю игрек».

Вообразим себя бегущими по кругу с длиной окружности $y$ , точкам которой приписаны вещественные числа из интервала $[0, y)$ . Если, взяв старт в точке $0$ , пробежать некоторое расстояние $x$ по окружности, мы остановимся в точке $x \bmod y$ . (А пока мы бегаем, точка 0 встретится нам $\lfloor x/y \rfloor$ раз.)

Из нашего формального определения $x - y \lfloor x/y \rfloor$ логически вытекают важные свойства остатка:

\align{ y > 0 &\implies 0 \le x \bmod y < y\\ y < 0 &\implies y < x \bmod y \le 0 }

В частности, $x \bmod 0 = x$ (пробежались по окружности нулевой длины).

В статье основы модулярной арифметики вводится целый раздел, порождаемый операцией MOD. Я же остановлюсь здесь на интересном факте.

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

Дробная часть числа

Операция

x \bmod{1}

— элегантный способ мгновенно получить дробную часть числа

Теорема Вейля

Есть знаменитая теорема Вейля о том, что если

\alpha

— иррациональное число, то последовательность

\{n \cdot \alpha\}

(то есть

n \cdot \alpha \mod{1} \text{ при }n=1, 2, 3...

) будет равномерно распределена по всему отрезку

[0, 1)

. Она никогда не попадет в одну точку дважды, но со временем "заполнит" весь отрезок, как бы хаотично, но при этом нигде не оставляя пустот. Это основа многих генераторов псевдослучайных чисел.

Пусть $\omega = (x_n) ~ (n=1, 2, \dots)$ — заданная последовательность действительных чисел. Для положительного целого числа $N$ и подмножества $E$ промежутка $I$ введем счетчик $A(E; N; \omega)$ , по определению равный количеству членов $x_n ~ (1 \le n \le N)$ , для которых $\{x_n\} \in E$ . При отсутствии опасности путаницы буду писать $A(E; N)$ вместо $A(E; N; \omega)$ . Вот основное определение:

Равномерное распределение по модулю 1

Последовательность $\omega = (x_n) ~ (n=1, 2, \dots)$ действительных чисел равномерно распределена по модулю 1 (сокращенно р.р. $\bmod \text{ }1$ ), если для любой пары $a, b$ действительных чисел, для которых $0 \le a < b \le 1$ , имеем:

\lim\limits_{N \to \infty} \frac{A([a, b); N; \omega)}{N} = b - a. \quad (1.1)

Обозначим теперь через $c_{[a, b)}$ характеристическую функцию интервала $[a, b) \subseteq I$ . Тогда (1.1) можно записать в форме:

\lim\limits_{N \to \infty} \frac{1}{N} \sum\limits_{n=1}^{N} c_{[a, b)}(\{x_n\}) = \int\limits_{0}^{1} c_{[a, b)}(x) \,dx. \quad (1.2)

Это замечание дает следующий критерий:

Критерий Вейля

Последовательность $(x_n) ~ (n=1, 2, \dots)$ действительных чисел р.р. $\bmod \text{ }1$ тогда и только тогда, когда для любой действительной непрерывной функции $f$ , определенной на замкнутом интервале $\overline{I} = [0, 1]$ , имеем:

\lim\limits_{N \to \infty} \frac{1}{N} \sum\limits_{n=1}^{N} f(\{x_n\}) = \int\limits_{0}^{1} f(x) \,dx. \quad (1.3)

Пусть $(x_n)$ р.р. $\bmod \text{ }1$ , а $f(x) = \sum\limits_{i=0}^{k-1} d_i \cdot \bigl[ x \;\! \in \;\! [a_i, a_{i+1}) \bigr]$ — ступенчатая функция, определенная на $\overline{I}$ , причем $0 = a_0 < a_1 < \dots < a_k = 1$ . Из (1.2) следует, что для любой такой функции $f$ справедливо уравнение (1.3).

Предположим теперь, что $f$ действительная непрерывная функция, определенная на $\overline{I}$ . Из определения интеграла Римана вытекает, что для любого заданного $\varepsilon > 0$ существуют две ступенчатые функции $f_1$ и $f_2$ такие, что $f_1(x) \le f(x) \le f_2(x)$ при всех $x \in \overline{I}$ и

\int\limits_{0}^{1} \bigl( f_2(x) - f_1(x) \bigr) \,dx \le \varepsilon.

Тогда справедлива следующая цепочка неравенств:

\align{ \int\limits_{0}^{1} f(x) \,dx - \varepsilon &\le \int\limits_{0}^{1} f_1(x) \,dx = \lim\limits_{N \to \infty} \frac{1}{N} \sum\limits_{n=1}^{N} f_1(\{x_n\}) \\ &\le \varliminf_{N \to \infty} \frac{1}{N} \sum\limits_{n=1}^{N} f(\{x_n\}) \;\! \le \;\! \varlimsup_{N \to \infty} \frac{1}{N} \sum\limits_{n=1}^{N} f(\{x_n\}) \\ &\le \lim\limits_{N \to \infty} \frac{1}{N} \sum\limits_{n=1}^{N} f_2(\{x_n\}) = \int\limits_{0}^{1} f_2(x) \,dx \\ &\le \int\limits_{0}^{1} f(x) \,dx + \varepsilon, }

так что в случае непрерывной функции $f$ имеет место (1.3).

Обратно, пусть задана последовательность $(x_n)$ и предполагается, что (1.3) выполнено для любой действительной непрерывной функции $f$ , определенной на $\overline{I}$ . Пусть $[a, b)$ — произвольный подынтервал $I$ . Для любого заданного $\varepsilon > 0$ существуют две непрерывные функции $g_1$ и $g_2$ такие, что $g_1(x) \le c_{[a, b)}(x) \le g_2(x)$ при $x \in \overline{I}$ и в то же время

\int\limits_{0}^{1} (g_2(x) - g_1(x)) \,dx \le \varepsilon.

Тогда имеем:

\align{ b - a - \varepsilon &\le \int\limits_{0}^{1} g_2(x) \,dx - \varepsilon \;\! \le \;\! \int\limits_{0}^{1} g_1(x) \,dx \\ &= \lim\limits_{N \to \infty} \frac{1}{N} \sum\limits_{n=1}^{N} g_1(\{x_n\}) \\ &\le \varliminf_{N \to \infty} \frac{A([a, b); N)}{N} \;\! \le \;\! \varlimsup_{N \to \infty} \frac{A([a, b); N)}{N} \\ &\le \lim\limits_{N \to \infty} \frac{1}{N} \sum\limits_{n=1}^{N} g_2(\{x_n\}) \\ &= \int\limits_{0}^{1} g_2(x) \,dx \;\! \le \;\! \int\limits_{0}^{1} g_1(x) \,dx + \varepsilon \\ &\le b - a + \varepsilon. }

Так как $\varepsilon$ сколь угодно мало, то отсюда вытекает (1.1).

Чему равно

(((\pi \bmod 1)\bmod 1)\dotsc\bmod 1)

Чему равен

I = \int\limits_{0}^{100} (x \pmod 1) \,dx

Возьмем рациональное $\alpha = 3/7$ . Рассмотрим последовательность $a_n = (n \cdot 3/7) \bmod 1$ .

"Заполнит" ли эта последовательность отрезок $[0, 1)$ ?

Сколько уникальных точек она породит? Будет ли множество таких точек счётным?

Докажите, что теорема Вейле не выполняется для рациональных чисел.