Количество делителей числа x, не превосходящих числа y.

[agregat252]

Интересующие меня вопросы на тему сабжа.
1) Как в математической литературе обозначается данная функция? Что о ней известно (формулы для вычисления, оценки, взаимосвязи с другими функциями, ...)? Где все это можно найти (авторы, статьи, книги, ...)?
2) Обозначим эту функцию за $\tau_\leqslant(x, y)$. Для каких $L \in \mathbb N, L$ - четно, выполняется $\tau_\leqslant(L^2 / 2, L / \sqrt 2) - \tau_\leqslant(L^2 / 2, L / 2) = 1$ (т.е. количество делителей числа $L^2 / 2$ на интервале $(L / 2, L / \sqrt 2)$ равно 1) ? Можно ли как-нибудь явно описать это множество?
Интересует наиболее быстрый алгоритм поиска таких чисел $L$ в заданном диапазоне (от 1 до 100, например). Считаем, что известно разложение на множители всех чисел из этого диапазона.
Заранее спасибо за ответы.

[agregat252]

Может быть, кому-то будет интереснее, если будет известно, зачем мне нужно решение этой задачи. А может быть, кто-то укажет иной подход к ее решению.

Имеет место следующий факт.

Количество пифагоровых троек $(a, b, c) \in \mathbb N, a^2 + b^2 = c^2$ с периметром $L = a + b + c$ равно указанному в пункте 2) количеству делителей числа $L^2 / 2$ на промежутке $(L / 2, L / \sqrt 2)$.

Это предлагает более быстрый алгоритм для решения этой задачи: http://projecteuler.net/problem=75. Пользуясь этим фактом, не требуется построение пифагоровых троек, множество которых задается двумя параметрами, что, несомненно, затратно по времени. Если найти решение предложенной в пункте 2) задачи, то, вероятно, не потребуется даже перебирать по L.

Идея доказательства:
Решая систему уравнений $a + b = L - c, a^2 + b^2 = c^2$, выражаем и подставляем $a$. Получаем квадратное уравнение. Его дискриминант $D$ равен $(L + c)^2 - 2 L^2$, что должно быть полным квадратом, который мы обозначим за $x^2$. Также для того, чтобы решения уравнения были положительными, требуется $D < L - c$, откуда получаем $c < L / 2$ и $L + c < 3 L /2$. Итак, $(L + c)^2 - 2 L^2 = x^2$. Перепишем как $(L + c)^2 - x^2 = 2 L^2$. Будем рассматривать это уравнение как диофантовое относительно переменных $c$ и $x$ ($L$ нам известно по условию). Известно, что все рациональные решения уравнения $x^2 - y^2 = N$ представляются в виде $x = (N + k^2) / 2k, y = (N - k^2) / 2k, k \in \mathbb Z$. Нас интересуют целые положительные решения, поэтому, применительно к нашей задаче, $2 L^2 > k^2, k^2 > L^2$ (следует из $L + c < 3 L / 2$), $ 2 L^2 \mathrel{\raisebox{-2pt}{\vdots}} 2k$ и $k$ - четно. Переходим к условиям на $k / 2$ и получаем утверждение задачи. Каждое такое $k$ доставляет целочисленное решение уравнения относительно $c$ и $x$, а те, в свою очередь - относительно $a$ и $b$.

[bot]

Пусть $x=p_1^{k_1}\ldots p_s^{k_s}$ - разложение $x$ в произведение простых. Тогда искомое число это количество неотрицательных целых решений системы линейных неравенств

$$\left\{ \begin{matrix}x_i\leqslant k_i & i=1,\ldots s\\ x_1\ln p_1+\ldots +x_s\ln p_s\leqslant \ln y\end{matrix}\right.$$

Вряд ли отсюда можно получить что-нибудь покрасивше.

[mihiv]

Поскольку в задаче по ссылке предполагается $L\leqslant 1.5\cdot 10^6$ (т.е. значения $L$ не очень велики), то проще, видимо, действовать перебором, а именно, для выбранного значения $L$ проверить, при каких значениях c из интервала $(\sqrt 2-1)L<c<\dfrac {L}2, D=(L+c)^2-2L^2$ является квадратом целого числа (левая часть неравенства получается из условия $D>0$.
Задача облегчается тем, что если при данном $L_0$ мы обнаружили более одной пифагоровой тройки, то значения $L=kL_0, k=2,3,\dots $ уже проверять не нужно.

[agregat252]

bot
Подход интересный, но что-то не помогает. Вряд ли мы упростили задачу, т.к. нам теперь нужны целочисленные решения уравнений с вещественными числами, т.е. идеи делимости тут не применишь. Не уравнений даже, а неравенств.
mihiv
В связи с величиной $L$ для целей задачи подходит и обычный перебор (построение всех примитивных пифагоровых троек двумя параметрами: $x = u^2 - v^2, y = 2uv, z = u^2 + v^2$, с определенными условиями на $u$ и $v$, вычисление периметра для каждой, умножение троек на всевозможные $k$, занесение данных о найденных периметрах троек в массив $[1..1.5 \cdot 10^6]$, а потом подсчет числа индексов массива, элементы которого равны 1). На Python'е это заняло не более 5и секунд (а вот на Mathematica, почему-то - целую вечность, и именно это натолкнуло меня на поиск более быстрого решения). Короче говоря, решение задачи по ссылке "хоть как-нибудь", интереса не представляет - задача решается "в лоб". Интересно именно асимптотически более быстрое решение. К слову, предложенный вами подход не будет быстрее описанного выше, поскольку перебирает больше чисел, чем только образующие пифагоровы тройки (он натыкается еще на те $c$, которые не дают полного квадрата). Зато нет никаких массивов, что было бы существенно для больших $L$ (у нас бы просто не было столько памяти). Но тем не менее.

[agregat252]

Думаю, я уже вплотную подобрался к решению задачи. Получено условие, которому должны удовлетворять простые множители числа $L$ и степени, с которыми они входят, для того, чтобы $L$ было периметром единственной пифагоровой тройки (из условия задачи http://projecteuler.net/problem=75). Резюмирую это утверждение и вспомогательную(ые) лемму(ы).
Доказательства будут вставлены несколько позже.
В формулировке могут содержаться некоторые ошибки (неправильно проставленные границы или что-нибудь подобное), разумеется, все будет исправляться, просто спешу поделиться результатом, пожалуйста, отнеситесь с пониманием.

Утверждение 1. Если $L = 2^{k_1} \prod_{i = 2}^{n} p_i^{k_i}$ $, является периметром единственной пифагоровой тройки, то существует единственный набор $a_1, \dots , a_n \in \mathbb Z, a_1 \in [k_1 - 1, -k_1], a_i \in [k_2, -k_2], i = 2, \dots, n$, такой, что $2^{a_1} p_2^{a_2} \dots p_n^{a_n} \in (\frac{1}{\sqrt 2}, 1)$.

Лемма 1. Имеет место равенство $\tau_{\leqslant} (p^k a, b)$ = \tau_{\leqslant} (a, b) + \tau_{\leqslant} (a, \frac{b}{p}) + \dots + \tau_{\leqslant} (a, \frac{b}{p^k}).


По условию задачи, нам нужно посчитать количество таких $L$ в диапазоне от $1$ до $N$. Думаю, можно считать, что мы знаем все возможные простые делители и все наибольшие значения порядков вхождения этих простых множителей для чисел из этого диапазона. Как (асимптотически наиболее быстро) выделить множество искомых $L$, пользуясь условием из утверждения 1? Либо, если нахождение самих $L$ для этого не потребуется, как найти их количество?

[maxal]

agregat252 в сообщении #778335 писал(а):

Количество пифагоровых троек $(a, b, c) \in \mathbb N, a^2 + b^2 = c^2$ с периметром $L = a + b + c$ равно указанному в пункте 2) количеству делителей числа $L^2 / 2$ на промежутке $(L / 2, L / \sqrt 2)$.

Пляшите от делителей. Для фиксированного числа $d$, сколько существует таких $L$, что $d$ делит $L^2/2$ и лежит в интервале $(L / 2, L / \sqrt 2)$?