Аннотация. Рассматривается задача точного вычисления числа пар индексов i < j, для которых целые части N/i и N/j совпадают, а также распределения размеров блоков одинаковых частных. Стандартный способ требует обхода порядка √N блоков. Предлагается алгоритм, использующий два наблюдения: размер блока c_w принимает одно из двух соседних значений m или m+1, где m = ⌊N/(w(w+1))⌋, а сумма размеров на отрезке постоянного m вычисляется телескопически по двум значениям целой части. Это позволяет находить вклад целого отрезка за O(1) арифметических операций и сводит число обрабатываемых отрезков к не более чем 2⌈N^1/3⌉. Описаны математическая основа метода, алгоритм, оценка сложности и процедура проверки результатов. Приведены результаты сравнительных измерений на Python для N от 10⁶ до 10¹⁶: ускорение составило от 1,21 до 51,33 раза и растёт с увеличением N. Также метод распространяется на вычисление распределения размеров блоков.

1. Введение

Значения ⌊N/i⌋ для i = 1, ..., N принимают не более 2√N различных значений, и на этом факте основано стандартное вычисление сумм вида Σ f(⌊N/i⌋): индексы i разбиваются на блоки с одинаковым частным, и каждый блок обрабатывается за O(1) операций, что даёт O(√N) операций в целом. Классическим примером служит функция делителей D(N) = Σ_i≤N ⌊N/i⌋ [1], [2], для которой стандартный метод также имеет сложность O(√N) [3].

В настоящей работе рассматривается величина, определяемая самими блоками частных: число пар индексов с равным частным E(N). Для её вычисления используется элементарное преобразование: размеры блоков группируются по значению ⌊N/(w(w+1))⌋. Это позволяет заменить обход √N значений на обход не более чем 2⌈N^1/3⌉ отрезков.

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

2. Постановка задачи

Пусть N - натуральное число. Для w ≥ 1 обозначим c_w = #{i ∈ {1, ..., N} : ⌊N/i⌋ = w} - размер блока частных со значением w. Блок - множество индексов с одним и тем же значением ⌊N/i⌋. Определим число коллизий

где C(c, 2) = c(c-1)/2. Вторая задача - найти распределение размеров блоков: H_j(N) = #{w : c_w = j}.

В работе сравниваются две реализации:

• стандартная реализация, в которой в цикле по w = 1, ..., ⌊√N⌋ вычисляется c_w = ⌊N/w⌋ - ⌊N/(w+1)⌋ и суммируются C(c_w, 2); сложность O(√N);
• новая сгруппированная реализация, в которой значения w объединяются в отрезки с постоянным значением ⌊N/(w(w+1))⌋; сложность O(N^1/3).

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

3. Математическая основа

Для любого w ≥ 1 условие ⌊N/i⌋ ≥ w равносильно условию i ≤ ⌊N/w⌋. Поэтому

Лемма 1. Пусть x, y - вещественные числа, x ≥ y, g = x - y. Тогда ⌊x⌋ - ⌊y⌋ ∈ {⌊g⌋, ⌊g⌋ + 1}.

Доказательство. Из x = y + g следует ⌊y + g⌋ ≥ ⌊y⌋ + ⌊g⌋, так как сумма целых частей не превосходит целой части суммы. С другой стороны, {y} + {g} < 2, где {·} - дробная часть, поэтому ⌊y + g⌋ ≤ ⌊y⌋ + ⌊g⌋ + 1. Вычитая ⌊y⌋, получаем утверждение.

Следствие 1. Применим лемму 1 к x = N/w, y = N/(w+1), g = N/(w(w+1)). Так как N и w(w+1) целые, ⌊g⌋ = ⌊N/(w(w+1))⌋ =: m(w), и из (2) получаем c_w ∈ {m(w), m(w)+1}.

Лемма 2 (телескопическая сумма). Для целых 1 ≤ a ≤ b выполнено Σ_w=a^b c_w = ⌊N/a⌋ - ⌊N/(b+1)⌋.

Доказательство. Прямо следует из (2): слагаемые вида ⌊N/w⌋ для a < w ≤ b сокращаются.

Лемма 3. Пусть s = ⌊√N⌋. Тогда для всех w > s выполнено c_w ≤ 1, и, следовательно, C(c_w, 2) = 0.

Доказательство. При w ≥ s + 1 имеем w(w+1) > N, поэтому g = N/(w(w+1)) < 1, ⌊g⌋ = 0 и по следствию 1 c_w ≤ 1.

Следствие 2 (вклад отрезка). Пусть на отрезке [a, b] значение m = m(w) постоянно, и пусть n₁ - число w ∈ [a, b], для которых c_w = m + 1. По следствию 1 для остальных w выполнено c_w = m. По лемме 2

а вклад отрезка в сумму (1) равен

Таким образом, вклад целого отрезка находится по двум значениям целой части и не требует обхода его внутренних точек.

Лемма 4 (границы отрезка). Пусть m = m(a) ≥ 1. Наибольшее b, для которого m(b) = m, равно b = (isqrt(4⌊N/m⌋ + 1) - 1) // 2, где isqrt(x) - целая часть квадратного корня, а // - целочисленное деление.

Доказательство. Функция m(w) не возрастает по w. Условие m(w) ≥ m равносильно w(w+1) ≤ N/m, т. е., для целых чисел, w(w+1) ≤ ⌊N/m⌋. Решая квадратное неравенство, получаем w ≤ (√(4⌊N/m⌋ + 1) - 1)/2, и наибольшее целое w равно указанному выражению, поскольку целая часть корня совпадает с isqrt. Так как m(a) = m, значение b не меньше a, а при w > b выполнено m(w) < m.

4. Алгоритм

Алгоритм обходит значения w от 1 до s = ⌊√N⌋ отрезками постоянного m. Для каждого отрезка по лемме 4 находится правая граница, по (3) - число n₁, по (4) - вклад в сумму. Обход прекращается, когда m = 0 (по лемме 3 и следствию 1 остальные c_w не превышают 1 и вклада не дают).

from math import isqrt

def E_fast(N):
    s = isqrt(N)
    total = 0
    v = 1
    while v <= s:
        m = N // (v * (v + 1))
        if m == 0:
            break
        vmax = (isqrt(4 * (N // m) + 1) - 1) // 2
        if vmax > s:
            vmax = s
        ln = vmax - v + 1
        n1 = (N // v - N // (vmax + 1)) - ln * m
        total += (ln - n1) * (m * (m - 1) // 2) + n1 * (m * (m + 1) // 2)
        v = vmax + 1
    return total

Алгоритм использует только целочисленные операции: умножение, целочисленное деление и isqrt, и требует O(1) дополнительной памяти.

5. Оценка сложности

Теорема. Число отрезков, обрабатываемых алгоритмом, не превышает 2⌈N^1/3⌉. Следовательно, E(N) вычисляется за O(N^1/3) арифметических операций.

Доказательство. Разобьём w на две части. Для w ≤ N^1/3 отрезков не больше, чем таких w, т. е. не больше ⌊N^1/3⌋. Для w > N^1/3 выполнено m(w) ≤ N/w² < N^1/3, поэтому m(w) принимает целые значения из {0, 1, ..., ⌈N^1/3⌉ - 1}, т. е. не более ⌈N^1/3⌉ различных значений. Так как m(w) не возрастает, каждому значению соответствует не более одного отрезка. Суммируя, получаем не более 2⌈N^1/3⌉ отрезков. На каждый отрезок затрачивается постоянное число арифметических операций над числами длины O(log N) бит.

Стандартный метод выполняет s = ⌊√N⌋ итераций. Следовательно, число обрабатываемых элементов сокращается с √N до порядка N^1/3. В экспериментах (раздел 8) число отрезков составило около 0,945 от верхней оценки 2N^1/3 для всех проверенных N.

6. Распределение размеров блоков

Те же отрезки позволяют найти распределение размеров блоков. Каждый отрезок добавляет (b - a + 1 - n₁) блоков размера m и n₁ блоков размера m + 1 к значениям H_m и H_m+1. По лемме 3 блоки размера не менее 2 встречаются только при w ≤ s, поэтому после обработки всех отрезков известны все H_j для j ≥ 2. Число блоков размера 1 находится из тождества Σ_j j·H_j = N, так как каждый индекс i принадлежит ровно одному блоку: H₁ = N - Σ_j≥2 j·H_j. Сложность вычисления распределения также составляет O(N^1/3).

Любая величина вида Σ_w F(c_w), например моменты Σ c_w^k, выражается через эти значения H_j.

7. Методика эксперимента и проверка корректности

Все реализации написаны на Python и используют только стандартную библиотеку (функцию math.isqrt и целые числа произвольной длины). Время измерялось функцией time.perf_counter для одного запуска на каждое значение N. Значения N выбирались в виде 10^e + 12345.

Корректность проверялась следующим образом:

• для всех N < 300 результат сгруппированной реализации совпал с прямым подсчётом по определению (1) (перебор всех пар, сложность O(N²)), с обходом всех блоков и с реализацией стандартного метода;
• для всех N от 300 до 19 999 результат сгруппированной реализации совпал с обходом всех блоков и со стандартной реализацией;
• для 544 случайных N из диапазона от 10⁵ до 10¹² результат сгруппированной реализации совпал со стандартной;
• распределение размеров блоков совпало с результатом прямого обхода блоков для всех N < 3 000 и для 200 случайных N из диапазона от 10⁶ до 10⁹;
• в измерениях раздела 8 значения стандартной и сгрупированной реализаций проверялись на равенство для каждого N.

8. Результаты

В таблице приведены результаты измерений. Столбец «Число отрезков» - число отрезков постоянного m, обработанных сгруппированной реализацией. Столбец «2N^1/3» - основной член верхней оценки теоремы.

Число отрезков для всех N составило 0,94-0,95 от 2N^1/3, что согласуется с теоремой. Ускорение возрастает с ростом N: от 1,21 раза при N порядка 10⁶ до 51,33 раза при N порядка 10¹⁶. Для оценки эмпирического показателя роста времени сопоставим измерения при N порядка 10¹⁰ и 10¹⁶ (шесть десятичных порядков): время стандартного метода выросло с 0,013287 с до 12,012418 с, т. е. в 904 раза, что соответствует показателю около 0,49; время сгруппированной реализации выросло с 0,002019 с до 0,234033 с, т. е. в 116 раз, что соответствует показателю около 0,34. Эти значения близки к теоретическим 1/2 и 1/3.

9. Заключение

В работе рассмотрен способ точного вычисления числа коллизий частных E(N) и распределения размеров блоков одинаковых частных ⌊N/i⌋ посредством группировки значений w в отрезки с постоянным ⌊N/(w(w+1))⌋.

Основной результат состоит в том, что размер блока принимает одно из двух соседних значений, а сумма размеров на отрезке находится телескопически, поэтому вклад целого отрезка вычисляется за O(1) операций, а число отрезков не превышает 2⌈N^1/3⌉. Сложность вычисления сокращается с O(√N) до O(N^1/3). Для реализации на Python экспериментально получено ускорение от 1,21 до 51,33 раза на значениях N от 10⁶ до 10¹⁶, причём ускорение растёт с увеличением N.

Обе реализации совпали с прямым подсчётом по определению для всех N < 300 и друг с другом на всех остальных проверенных значениях. Результаты измерений относятся к описанным реализациям и вычислительной системе. Дальнейшее развитие метода может включать исследование возможности снижения показателя ниже 1/3, вычисление других статистик вида Σ F(c_w) и перенос подхода на частные вида ⌊N/(a·i + b)⌋.

Исходные тексты реализаций, тесты корректности и скрипт измерений доступны в репозитории: https://github.com/tankwars92/quotient_blocks.

Список использованных источников

1. Apostol T. M. Introduction to Analytic Number Theory. - New York: Springer, 1976. - 338 p.

2. The On-Line Encyclopedia of Integer Sequences. A006218: a(n) = Sum_{k=1..n} floor(n/k) [Электронный ресурс]. - URL: https://oeis.org/A006218 (дата обращения: 15.10.2026).

3. Sladkey R. A Successive Approximation Algorithm for Computing the Divisor Summatory Function [Электронный ресурс] // arXiv:1206.3369 [math.NT]. - 2012. - URL: https://arxiv.org/abs/1206.3369 (дата обращения: 15.10.2026).