Последовательные почтиквадраты

[Shadow]

Натуральное число $n$ называется почтиквадратом, если его можно представить в виде произведения двух натуральных чисел
$n=ab$, где $a \le b$ и $\dfrac a b >0.999999$
Доказать, что существуют бесконечно много четверок последовательных почтиквадратов.

Сразу бросается в глазах пара $a^2-1,a^2$.

Понятно, что $\lim\limits_{a \to \infty} \dfrac{a-1}{a+1}=1$, так что при достаточно больших $a$ условие выполняется.

Дальше $a^2+1$. Тут тоже несложно, если $a=2x^2$ то $4x^4+1=(2x^2-2x+1)(2x^2+2x+1)$

А дальше у меня не получается идея представить $x=f(u)$, так чтобы $4x^4+2$, либо $4x^4-2$ разлагалось в произведение двух полиномов равной степени с равными старшими коэффициентами. Может поможете?

Занудное продолжение, чтобы как-то решить задачу: Попробуем $4x^4+2=(2x^2-u+1)(2x^2+u+2)$

$6x^2=u^2+u$. Или, имеем уравнение Пелля $(2u+1)^2-24x^2=1$. Оно имеет бесконечно много решений, причем $\dfrac{2u+1}{x} \to 2\sqrt 6$

Откуда $u<\sqrt 6 x$, а значит $\dfrac{2x^2-u+1}{2x^2+u+2} \to 1$

Но не нравится мне, может попроще?

[Andrey A]

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

... бесконечно много четверок последовательных почтиквадратов.

Не очень понятно условие. Если нужны четверки последовательных составных близких к целому квадрату, берем к примеру $5^2-2=23, 5^2-3=2\cdot 11$ и далее квадрат по $\mod 253=23 \cdot 11.$

$258^2=2\cdot2\cdot3\cdot3\cdot43\cdot43.$
$258^2-1=7\cdot37\cdot257.$
$258^2-2=2\cdot23\cdot1447.$
$258^2-3=3\cdot11\cdot2017.$
$258^2-4=2\cdot2\cdot2\cdot2\cdot2\cdot2\cdot2\cdot2\cdot2\cdot2\cdot5\cdot13.$

Следующий $511^2 $ и т.д. Целые пятерки почтиквадратов ) Или Вам нужно $a/b \approx 1 ?$

[Shadow]

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

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

... бесконечно много четверок последовательных почтиквадратов.

Не очень понятно условие.

Ну числа $k,k+1,k+2,k+3$ - почтиквадраты по определению. И таких $k$ бесконечно много.

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

Или Вам нужно $a/b \approx 1 ?$

Ну да, я бы мог дописать еще несколько десяток $9$ после запятой в определении - суть ясна.

[Andrey A]

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

... не нравится мне, может попроще?

А чем не нравится? $u_n \approx \dfrac{(5+\sqrt{24})^n-2}{4};\ x_n \approx \dfrac{(5+\sqrt{24})^n}{2\sqrt{24}}$. Ничем не мудреней ряда Фибоначчи. Хорошее решение, но $n$ надо взять большое, чтобы получить Ваши девятки. Так и запрос неслабый.

[Shadow]

Andrey A Ну да, решение оно есть, но задача-то школьная. А привлекать уравнение Пелля со всей теорией для школьника просто абсурдно. Три последовательные числа нетрудно находятся (от одного параметра): $4k^4-1,4k^4,4k^4+1$
Не знаю, может я не туда пошел.

[Shadow]

Попробую передать какой-то школьный вид данному решению. И так, пусть

$4x^4+2=(2x^2-u+1)(2x^2+u+2)$

$6x^2=u^2+u$ Из этого следует $u<3x$, а значит

$1>\dfrac{2x^2-u+1}{2x^2+u+2}>\dfrac{2x^2-3x+1}{2x^2+3x+2}$

При $x\to \infty$ выражение вправо стремится к $1$, значит зажали между милиционерами.

Осталось доказать бесконечность решений $6x^2=u(u+1)$.

Пусть $u=2n^2,u+1=3m^2,x=mn$

Получаем уравнение $3m^2-2n^2=1$

Про Пелля не слышали, но догадались, что если $(m,n)$ - -решение, то $(5m+4n,6m+5n)$ - тоже решение.

И так как $(1,1)$ есть решение, то получаются бесконечно много, сколь угодно больших решений.

[Andrey A]

Еще вариант. Без Пелля тоже не обошлось, но можно оформить как зависимость от последовательности

$$2,5,12,...\ u_{n+1}=2u_n+u_{n-1}.$$

Для каждой пары последовательных членов определены $p_n=6u_nu_{n+1}+1,\ q_n=\dfrac{3(u_n^2+u_{n+1}^2)-1}{2}$ и $A_n=p_n^2+p_n+1.$
Имеем четверку:
$A^2-2=\left ( 2q^2-1 \right )\left ( 2(q+1)^2-1 \right )$
$A^2-1=(A-1)(A+1)$
$A^2=A \cdot A$
$A^2+1=\left ( p^2+1 \right )\left ( (p+1)^2+1 \right ).$

[Andrey A]

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

$p_n=6u_nu_{n+1}+1,\ q_n=\dfrac{3(u_n^2+u_{n+1}^2)-1}{2}$

Тут ошибка, виноват. Верно: ... определены $p_n=\dfrac{(u_{n+1}^2-u_n^2+2u_nu_{n+1}) \cdot3-1}{2},\ q_n=\dfrac{(u_{n+1}^2+u_n^2) \cdot3-1}{2}$ и $A_n=p_n^2+p_n+1.$

[Andrey A]

Еще можно связать с задачей $t_x=y^2$ — равенство треугольного и квадратного числа $( t_x=\frac{x(x+1)}{2}).$ Эту задачу в школе вполне могут знать: $t_1=1^2,t_8=6^2,t_{49}=35^2,$ и т.д. Если что, Серпинский на стр. $21-24$ показывает, как тут обойтись без Пелля.

Положим $A=2y^2-2.$ Тогда их целая пятерка:
$A^2=A \cdot A$
$A^2-1=(A-1)(A+1)$
$A^2-2=\left ( x^2-2 \right )\left ( (x+1)^2-2 \right )$
$A^2-3=(4t_{y-1}-1)(4t_y-1)$
$A^2-4=(A-2)(A+2).$

Ну, а с Пеллем, понятно, $(2x+1)^2-8y^2=1,\ x_n \approx \dfrac{(3+\sqrt{8})^n-2}{4},\ y_n \approx \dfrac{(3+\sqrt{8})^n}{4\sqrt{2}}. $

[Shadow]

Спасибо Andrey A, пятерка это красиво.

[B@R5uk]

Интересно эту задачу численно пощупать. Метод факторизации Ферма как раз очень подойдёт для детектирования того, является тестируемое число почтиквадром или нет. Вот тут я даже прикидывал сколько итераций метода потребуется в зависимости от того, как близки множители по величине. Для шести девяток величины порядка триллионов будут за одну итерацию проверяться. Хотя, конечно, интереснее требования по-слабее и числа по-меньше посмотреть.

[mathematician123]

Можно ввести почтиквадраты порядка $\varepsilon$, то есть числа вида $xy$, где $(1 - \varepsilon)y \le x \le y$. Тестировать числа на почтиквадратность по одному скорее всего медленно. Лучше тестировать все числа на некотором отрезке.

Если $x = cd$, где $(1 - \varepsilon)d \le c \le d$ и $x \in [a, b]$, то $\sqrt{(1 - \varepsilon)a} \le c \le \sqrt{b}$, $\sqrt{a} \le d \le \sqrt{\frac{b}{1 - \varepsilon}}$. Соответственно, для нахождения всех почтиквадратов на отрезке $[a, b]$ можно просто перебрать все такие пары $c, d$ за линейное по $b$ время.

Верно ли, что множество почтиквадратов имеет положительную плотность? Рассмотрим отрезок $[1, N]$. Если рассматривать множество произведений вида $xy$, где $(1 - \varepsilon)y \le x \le y$, на этом отрезке, то их будет $c(\varepsilon)N$ для некоторой константы $c(\varepsilon)$. Но некоторые произведения будут задавать один и тот же почтиквадрат. Например, числа вида $p_1p_2p_3p_4$, где $p_i$ - близкие друг к другу простые, допускают вплоть до шести различных подходящих разложений.

[B@R5uk]

Накатал на коленке вот такую вот программулину:

Используется синтаксис Java

//https://dxdy.ru/topic154565.html

public class Almost_Square {
    
    private static final int testTol = 20;
    private static final int factor1 = 229;
    private static final int factor2 = 457;     //      104653
    private static long result1, result2;
    
    public static void main (String [] args) {
        int k, l, m;
        long value;
        for (value = 3_000_000_000_001L, k = 0, l = 0; 500_000_000 > k; ++value, ++k) {
            if (testAlmostSquare (value, testTol)) {
                ++l;
            } else {
                if (3 <= l) {
                    System .out .println ((value - l) + " " + l);
                    for (m = 0; l > m; ++m) {
                        testAlmostSquare (value - l + m, testTol);
                        System .out .println ((value - l + m) + " = " + result1 + " * " + result2 + " ~ " + (1.0 * result2 / result1 - 1.0));
                    }
                }
                l = 0;
            }
        }
    }
    
    private static boolean testAlmostSquare (long value, int tolerance) {
        int k = 0;
        long temp;
        boolean flag = false;
        while (0 == (value & 3)) {
            value >>= 2;
            ++k;
        }
        if (0 == (value & 1)) {
            flag = true;
            value >>= 1;
            value *= factor1 * factor2;
        }
        //System .out .println (value);
        if (!factorFerma (value, tolerance)) {
            return false;
        }
        if (flag) {
            if          (0 == result1 % factor1 && 0 == result2 % factor2) {
                result1 /= factor1;
                result2 /= factor2;
                result2 <<= 1;
            } else if   (0 == result2 % factor1 && 0 == result1 % factor2) {
                result2 /= factor1;
                result1 /= factor2;
                result1 <<= 1;
            } else {
                return false;
            }
            if (result1 > result2) {
                temp    = result1;
                result1 = result2;
                result2 = temp;
            }
        }
        result1 <<= k;
        result2 <<= k;
        return true;
    }
    
    private static boolean factorFerma (long value, int tolerance) {
        int k;
        long x, x2, y;
        if (0 == (value & 1)) {
            throw new IllegalArgumentException ("\n\nTested value must be odd.\n");
        }
        k = 0;
        x = (long) Math .ceil (Math .sqrt ((double) value));
        x2 = x * x;
        while (tolerance > k) {
            y = (long) Math .sqrt ((double) (x2 - value));
            if (x2 - y * y == value) {
                result1 = x - y;
                result2 = x + y;
                //System .out .println (k + " " + y);
                return true;
            }
            ++k;
            ++x;
            x2 += (x << 1) - 1;
        }
        return false;
    }
}
 

Погонял чутка, на четвёрки пока не натыкался, а вот тройки попадаются. И даже без пар вида $a^2-1,a^2$:

1000017578987 3
1000017578987 = 994159 * 1005893 ~ 0.011802940978254073
1000017578988 = 997478 * 1002546 ~ 0.00508081381243497
1000017578989 = 994331 * 1005719 ~ 0.011452926641128514
1000030281535 3
1000030281535 = 998705 * 1001327 ~ 0.0026253998928611466
1000030281536 = 991016 * 1009096 ~ 0.018243903226587754
1000030281537 = 994399 * 1005663 ~ 0.011327445019554627
2000014559099 3
2000014559099 = 1408579 * 1419881 ~ 0.008023689122157895
2000014559100 = 1405146 * 1423350 ~ 0.01295523739170168
2000014559101 = 1410007 * 1418443 ~ 0.005982949020820527
3000329442691 3
3000329442691 = 1726859 * 1737449 ~ 0.0061325215318679405
3000329442692 = 1731578 * 1732714 ~ 6.560489911513478E-4
3000329442693 = 1730201 * 1734093 ~ 0.0022494496304186207

-- 09.06.2023, 22:02 --

Ан, нет. Парочку предквадратов нащупал таки. Хотя они субъективно реже попадаются, чем обычные тройки последовательных почтиквадратов:

Используется синтаксис Text

2001650377515 3
2001650377515 = 1413065 * 1416531 ~ 0.0024528241800625405
2001650377516 = 1410334 * 1419274 ~ 0.00633892397120106
2001650377517 = 1408967 * 1420651 ~ 0.008292600181551535
2002361043967 3
2002361043967 = 1410319 * 1419793 ~ 0.006717629132132474
2002361043968 = 1392416 * 1438048 ~ 0.03277181531955975
2002361043969 = 1408563 * 1421563 ~ 0.00922926415076919
2002378206927 3
2002378206927 = 1412759 * 1417353 ~ 0.003251793122535318
2002378206928 = 1408804 * 1421332 ~ 0.008892649367832517
2002378206929 = 1413491 * 1416619 ~ 0.0022129606767924415
2002480835823 3
2002480835823 = 1412963 * 1417221 ~ 0.0030135254780203624
2002480835824 = 1400348 * 1429988 ~ 0.021166167266993607
2002480835825 = 1409131 * 1421075 ~ 0.008476145936751056
2002562418075 3
2002562418075 = 1412319 * 1417925 ~ 0.0039693581974045156
2002562418076 = 1413638 * 1416602 ~ 0.0020967178301658507
2002562418077 = 1412879 * 1417363 ~ 0.0031736617219166874
2002633882623 3
2002633882623 = 1411989 * 1418307 ~ 0.004474539107599318
2002633882624 = 1407008 * 1423328 ~ 0.011599081170824865
2002633882625 = 1413925 * 1416365 ~ 0.0017256926640381032
2002640420879 3
2002640420879 = 1413293 * 1417003 ~ 0.0026250749136944584
2002640420880 = 1406724 * 1423620 ~ 0.012010884864408267
2002640420881 = 1409279 * 1421039 ~ 0.00834469256974657
2002898596643 3
2002898596643 = 1415237 * 1415239 ~ 1.4131908647740943E-6
2002898596644 = 1415238 * 1415238 ~ 0.0
2002898596645 = 1409185 * 1421317 ~ 0.008609231577117349
2002966528643 3
2002966528643 = 1415261 * 1415263 ~ 1.413166899943974E-6
2002966528644 = 1415262 * 1415262 ~ 0.0
2002966528645 = 1411505 * 1419029 ~ 0.005330480586324571
 

Интересно, сохраняется ли эта тенденция для больших точностей и/или больших чисел и/или для четвёрок/пятёрок?

[B@R5uk]

С пониженной точностью нащупал пятёрку:

Используется синтаксис Text

2078299178 = 44789 * 46402 ~ 0.03601330683873272
2078299179 = 44487 * 46717 ~ 0.050127003394250025
2078299180 = 44410 * 46798 ~ 0.053771673046611124
2078299181 = 45101 * 46081 ~ 0.021729008225981783
2078299182 = 45057 * 46126 ~ 0.023725503251436963
 

-- 10.06.2023, 00:12 --

И ещё одну, с предквадратом теперь:

Используется синтаксис Text

2279012117 = 47737 * 47741 ~ 8.379244611100845E-5
2279012118 = 47521 * 47958 ~ 0.00919593442898936
2279012119 = 47431 * 48049 ~ 0.013029453311125705
2279012120 = 47738 * 47740 ~ 4.1895345427089836E-5
2279012121 = 47739 * 47739 ~ 0.0
 

[mathematician123]

B@R5uk
Есть одна идея. Возможно, это ускорит перебор.

Будем искать все почтиквадраты на некотором интервале $[a, b]$. Причём интервал возьмём "коротким", то есть его длина должна быть в несколько раз меньше $\sqrt{b}$. Тогда все почтиквадраты в этом интервале будут иметь вид $c \cdot \lfloor \frac{b}{c} \rfloor$ для некоторого натурального $c$. Соответственно, для нахождения всех почтиквадратов достаточно перебрать все $c$ от 1 до $\sqrt{b}$ и проверить два условия: $a \le c \cdot \lfloor \frac{b}{c} \rfloor$ и дробь $\frac{c}{\lfloor \frac{b}{c} \rfloor}$ достаточно близка к 1.