Разваливающиеся числа

[Утундрий]

Будем говорить, что натуральное число $z$ разваливается на два других натуральных числа $x$ и $y$, если $z\dfrac{{x + y}}{{xy - 1}}$ - также является натуральным числом. Обозначим этот факт записью $z = x\diamond y$. Например

$$1 = 2\diamond 3, \qquad 2 =3\diamond 7, \qquad 3 = 4\diamond 13 = 5\diamond 8 \qquad ...$$

Итак, $1$ и $2$ разваливаются на одну пару, $3$ - на две различные пары и, в общем случае, $n$ разваливается на $k_n$ различных пар.

Задача 1 Что можно сказать о распределении $\mathbb{N}$ по множествам $k_n=const$?

Задача 2 Как можно описать структуру неупорядоченных подмножеств $\mathbb{N}$, связанных развалами их элементов?

[Лукомор]

Утундрий в сообщении #1440643 писал(а):

$1$ и $2$ разваливаются на одну пару

Почему на одну пару?

$ 2 = 2\diamond 3 $

$ 3 = 2\diamond 3 $

[nnosipov]

Утундрий в сообщении #1440643 писал(а):

Итак, $1$ и $2$ разваливаются на одну пару, $3$ - на две различные пары и, в общем случае, $n$ разваливается на $k_n$ различных пар.

Угу, для $1$ получаем $6$ пар, для $2$ --- $10$ пар, а для $3$ --- $17$ пар.

[Andrey A]

Если имеется в виду всё же $z=\dfrac{{xy - 1}}{{x+y}}$, то $x^2 \equiv y^2 \equiv -1 \mod x+y$. Доля таких модулей в нат. ряду $\approx 1/4$, а $z$ оказывается в промежутке $\left [ x-1,(x+y)/4 \right )$. Грубо говоря, если $x<y$. Поэтому пересечения неизбежны $(n=2,n=3,...)$, но серьезных закономерностей в их распределении ожидать я бы не стал. Чисто по ощущению, возможно ошибаюсь.

Исправлено 12.22

[Утундрий]

Andrey A в сообщении #1440656 писал(а):

Если имеется в виду всё же $z=\dfrac{{xy - 1}}{{x+y}}$

Да, конечно. Не подумал, что представление выше даёт паразитов.

[Shadow]

Утундрий в сообщении #1440660 писал(а):

Да, конечно

Тогда имеем уравнение
$(x-z)(y-z)=z^2+1$ и число решений зависит от количество делителей $z^2+1$ (ровно половина).

[Andrey A]

Shadow в сообщении #1440662 писал(а):

$(x-z)(y-z)=z^2+1$ и число решений зависит...

Красиво. Еще закономерность: $\sqrt{x-z}+\sqrt{y-z} \approx \sqrt{x+y}$ — возможно лучшее верхнее приближение.

[Утундрий]

Shadow в сообщении #1440662 писал(а):

Тогда имеем уравнение
$(x-z)(y-z)=z^2+1$ и число решений зависит от количество делителей $z^2+1$ (ровно половина).

Спасибо, это резко упрощает перебор.

[Andrey A]

Утундрий в сообщении #1440750 писал(а):

... перебор.

Тут не перебор, тут точное решение: $k_n=\tau (z^2+1)/2$, где $\tau (m)$ — количество делителей $m$, вычисляемое по формуле (лучше бы $k_z$, поскольку функция от $z$). Для $z=7$, к примеру, $7^2+1=50=2^1\cdot 5^2 \Rightarrow \tau (50)=(1+1)(2+1)/2=3.$ Нечетной $\tau (m)$ может быть только если $m$ целый квадрат, что невозможно для $m=z^2+1$. Так что всё законно.

[Утундрий]

Это понятно, но мне также интересны и сами решения, а не только их число. Я имел в виду перебор решений. Что-то типа

z = 7; a = 1 + z^2; x = z + Divisors[a]; y = z + a/(x - z); For[
 i = 1, i <= Length[x], i++, xx = x[[i]]; yy = y[[i]]; 
 If[ xx < yy, Print[xx, "    ", yy]]]

[Andrey A]

Да, в этом есть своя эстетика )

[Утундрий]

Довольно забавно выглядит зависимость наименьшего числа $z$, разваливающегося на $\alpha$ различных вариантов.

$$\begin{tabular}{c|c} \alpha & z_1(\alpha) \\ \hline 1 & 1 \\ 2 & 3 \\ 3 & 7 \\ 4 & 13 \\ 5 & 182 \\ 6 & 43 \\ 7 & 1068 \\ 8 & 47 \\ 9 & 268 \\ 10 & 443 \\ 11 & ? \\ \end{tabular}​$$

[Andrey A]

Неповторяющиеся пики $\tau ()$. Вместо $185$ вроде бы $182$ должно быть: $\tau (185^2+1)/2=4.$ Для $\alpha=11$ видимо $15905182$ подойдет. Ну конечно там рваный график будет.

[Утундрий]

Andrey A в сообщении #1440783 писал(а):

Вместо $185$ вроде бы $182$ должно быть

Да, очепятался.

Andrey A в сообщении #1440783 писал(а):

Для $\alpha=11$ видимо $15905182$ подойдет

Проверил, подходит. Правда совершенно не вижу как это можно было подобрать.

[Andrey A]

Не, подбирать это долго. Нужно получить $\alpha=11$, значит $\tau (z^2+1)=22.$ Такую $\tau ()$ дала бы $21-$я степень простого, но ведь она должна еще оказаться числом вида $z^2+1$. Искать это тоже долго, к тому же наименьшим явно не будет. А вот если положить $z^2 \equiv -1$ по модулю $10-$й степени простого, то как раз получим $z^2+1=p^{10}q^1$, и если $q$ тоже простое, то $\tau (p^{10}q^1)/2=(10+1)(1+1)/2=11$. Двойка тут не может быть в $10-$й степени, наименьшее из возможных $p=5$. Заходим в Вольфрам, находим наименьший квадрат $\equiv -1 \mod 5^{10}$, но он не годится, поскольку $q$ оказывается составным. То же и второй. А вот тртий по величине квадрат дает то что нужно: $15905182^2+1=5^{10} \cdot 25904621^1.$