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

[B@R5uk]

mathematician123, проблема в том, что числа вида $c\cdot\lfloor\frac{b}{c}\rfloor$ будут раскиданы туда-сюда по изучаемому отрезку, что потребует их упорядочивания для нахождения непосредственных соседей. А это расходы памяти. Если они выйдут за пределы кэша процессора, то процесс будет ОЧЕНЬ медленным. Идея интересная, но её ещё надо до ума довести.

[B@R5uk]

Вот интересно, сколько на отрезке $[K,L]$ почтиквадратов с точностью эпсилон. То есть

$$\begin{array}{l}K\le n=ab\le L\\a\le b\le a\left(1+\varepsilon\right)\\ \end{array}$$

Будет ли эта величина хотя бы в среднем пропорциональна длине отрезка? Будет ли она флуктуировать как число простых чисел на отрезке? Какая будет зависимость от эпсилон?

-- 10.06.2023, 12:12 --

Если не считать повторений (которые при малых эпсилон редки), то по идее искомое число будет пропорционально площади криволинейного четырёхугольника в плоскости Oab, ограниченного двумя гиперболами (вернее неравенство) и двумя лучами, выходящими из начала координат (нижнее неравенство). При малых эпсилон эту фигуру можно считать сектором кольца, радиусы которого равны корням из концов отрезка, а угол разворота надо прикинуть.

[mathematician123]

B@R5uk в сообщении #1597133 писал(а):

Если не считать повторений (которые при малых эпсилон редки),

Тут есть проблема. Можно взять $n = n_1n_2 \cdot \ldots \cdot n_{2k}$, где $n_i$ достаточно близки друг к другу. Тогда $n$ можно представить $C_{2k}^{k}$ способами в виде $ab$, $a \le b \le (1 + \varepsilon)a$.

Я реализовал идею из предыдущего сообщения.

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

a = 10**11
l = 10**5
b = a + l

N = [0]*(b - a + 1)

for c in range(1, int(a**0.5) + 2):
        d = b//c
        if 2/3 < d/c < 3/2 and a <= d*c:
                N[d*c - a] = 1
        
k = 0   
for i in range(len(N)):
        if N[i] == 1:
                k += 1
print(k, k/l)
 

Если подставлять $a = 10^{11}, 10^{12}, 10^{13}$ и т. д, то можно видеть что доля почтиквадратов понемногу убывает. Но данных мало. Хотелось бы проверить $a = 10^{m}$ хотя бы для $m \le 30$.

[B@R5uk]

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

На интервале от 1E8 до 1E10 с точностью 5% нашлось 20 последовательностей длины 5 и 6:

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

5  ~  0.048520175690653033
622253021 = 24943 * 24947  ~  1.603656336446324E-4
622253022 = 24382 * 25521  ~  0.04671478959888442
622253023 = 24361 * 25543  ~  0.048520175690653033
622253024 = 24944 * 24946  ~  8.017960230910504E-5
622253025 = 24945 * 24945  ~  0.0
5  ~  0.04500079226746956
1040526123 = 32029 * 32487  ~  0.014299541040931674
1040526124 = 31834 * 32686  ~  0.02676383740654642
1040526125 = 31555 * 32975  ~  0.04500079226746956
1040526126 = 31734 * 32789  ~  0.03324509989285929
1040526127 = 31601 * 32927  ~  0.04196069744628339
5  ~  0.04534288934485442
1251659716 = 34603 * 36172  ~  0.04534288934485442
1251659717 = 35261 * 35497  ~  0.006692946881824202
1251659718 = 35034 * 35727  ~  0.01978078438088704
1251659719 = 35089 * 35671  ~  0.016586394596597165
1251659720 = 34807 * 35960  ~  0.033125520728588986
5  ~  0.013029453311125705
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
5  ~  0.038665655799848375
3037617429 = 54901 * 55329  ~  0.007795850713101737
3037617430 = 54079 * 56170  ~  0.038665655799848375
3037617431 = 54721 * 55511  ~  0.014436870671223012
3037617432 = 54657 * 55576  ~  0.016813948808021006
3037617433 = 54601 * 55633  ~  0.018900752733466364
6  ~  0.020407812687887494
3457910411 = 58321 * 59291  ~  0.016632087927161754
3457910412 = 58802 * 58806  ~  6.802489711232873E-5
3457910413 = 58213 * 59401  ~  0.020407812687887494
3457910414 = 58562 * 59047  ~  0.008281820976059562
3457910415 = 58803 * 58805  ~  3.40118701427361E-5
3457910416 = 58804 * 58804  ~  0.0
5  ~  0.031443488737909586
3683303845 = 60385 * 60997  ~  0.010134967293201846
3683303846 = 59758 * 61637  ~  0.031443488737909586
3683303847 = 59859 * 61533  ~  0.02796571944068571
3683303848 = 60509 * 60872  ~  0.005999107570774598
3683303849 = 60113 * 61273  ~  0.019296990667576175
6  ~  0.047982010879449755
3833467220 = 60545 * 63316  ~  0.04576761086794945
3833467221 = 61913 * 61917  ~  6.460678694297783E-5
3833467222 = 60502 * 63361  ~  0.04725463621037318
3833467223 = 60481 * 63383  ~  0.047982010879449755
3833467224 = 61914 * 61916  ~  3.230287172528712E-5
3833467225 = 61915 * 61915  ~  0.0
5  ~  0.046606043602396285
3842626280 = 61240 * 62747  ~  0.024608099281515416
3842626281 = 60593 * 63417  ~  0.046606043602396285
3842626282 = 61426 * 62557  ~  0.01841239865854849
3842626283 = 60937 * 63059  ~  0.03482284982851147
3842626284 = 61548 * 62433  ~  0.014379021251706092
5  ~  0.04805080850708232
5402802948 = 72591 * 74428  ~  0.02530616743122427
5402802949 = 72817 * 74197  ~  0.018951618440748774
5402802950 = 73175 * 73834  ~  0.009005807994533654
5402802951 = 71799 * 75249  ~  0.04805080850708232
5402802952 = 72872 * 74141  ~  0.017414095949061403
5  ~  0.04772861833252606
5786466704 = 74962 * 77192  ~  0.02974840585896854
5786466705 = 74835 * 77323  ~  0.03324647557960847
5786466706 = 75434 * 76709  ~  0.01690219264522619
5786466707 = 75187 * 76961  ~  0.023594504369106373
5786466708 = 74316 * 77863  ~  0.04772861833252606
5  ~  0.04225768701534194
6302295765 = 79385 * 79389  ~  5.038735277440587E-5
6302295766 = 78458 * 80327  ~  0.023821662545565836
6302295767 = 77761 * 81047  ~  0.04225768701534194
6302295768 = 79386 * 79388  ~  2.5193359030506457E-5
6302295769 = 79387 * 79387  ~  0.0
5  ~  0.03311792212946996
6715003710 = 80715 * 83194  ~  0.030713002539800582
6715003711 = 80621 * 83291  ~  0.03311792212946996
6715003712 = 81472 * 82421  ~  0.011648173605655954
6715003713 = 80817 * 83089  ~  0.028112897038989226
6715003714 = 81698 * 82193  ~  0.00605889985066943
6  ~  0.013961647813199418
6927232895 = 82655 * 83809  ~  0.013961647813199418
6927232896 = 83228 * 83232  ~  4.806074878649369E-5
6927232897 = 82823 * 83639  ~  0.009852335703850468
6927232898 = 82942 * 83519  ~  0.006956668515348152
6927232899 = 83229 * 83231  ~  2.4030085667314793E-5
6927232900 = 83230 * 83230  ~  0.0
5  ~  0.04722153150272934
7469107772 = 86422 * 86426  ~  4.628451088839469E-5
7469107773 = 84453 * 88441  ~  0.04722153150272934
7469107774 = 84562 * 88327  ~  0.04452354485466281
7469107775 = 86423 * 86425  ~  2.314198766528719E-5
7469107776 = 86424 * 86424  ~  0.0
5  ~  0.04640059766304416
7679361213 = 87207 * 88059  ~  0.009769857924249115
7679361214 = 85667 * 89642  ~  0.04640059766304416
7679361215 = 86795 * 88477  ~  0.019378996485972744
7679361216 = 85872 * 89428  ~  0.04141047139929199
7679361217 = 85921 * 89377  ~  0.04022299554241693
5  ~  0.0440812993776758
8575493244 = 90628 * 94623  ~  0.0440812993776758
8575493245 = 90745 * 94501  ~  0.04139071023196861
8575493246 = 90721 * 94526  ~  0.041941777537725544
8575493247 = 92517 * 92691  ~  0.0018807354324070769
8575493248 = 92288 * 92921  ~  0.006858963245492289
5  ~  0.033807809949958356
8849917472 = 94072 * 94076  ~  4.252062250187372E-5
8849917473 = 92523 * 95651  ~  0.033807809949958356
8849917474 = 93266 * 94889  ~  0.017401839898784077
8849917475 = 94073 * 94075  ~  2.1260085252938765E-5
8849917476 = 94074 * 94074  ~  0.0
5  ~  0.03160234693114172
9031841292 = 95034 * 95038  ~  4.209019929701796E-5
9031841293 = 93601 * 96493  ~  0.030897105800151703
9031841294 = 93569 * 96526  ~  0.03160234693114172
9031841295 = 95035 * 95037  ~  2.1044878202758355E-5
9031841296 = 95036 * 95036  ~  0.0
5  ~  0.044843095165082225
9999889108 = 97898 * 102146  ~  0.04339210198369736
9999889109 = 98951 * 101059  ~  0.02130347343634731
9999889110 = 97830 * 102217  ~  0.044843095165082225
9999889111 = 99667 * 100333  ~  0.006682251898822988
9999889112 = 99103 * 100904  ~  0.018173011916894577
 

Поиск был выполнен за минуту. Программа вышла такая:

Файл Almost_Square_3.java

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

//      topic154565.html

public class Almost_Square_3 {
    
    public static void main (String [] args) {
        int k, l, m;
        long startTime, stopTime;
        double value;
        ProductSearcher ps = new ProductSearcher ();
        ProductSearcher .Record [] [] ra;
        startTime = System .nanoTime ();
        ra = ps .run (100_000_000L, 10_000_000_000L, 400_000, 5, 20);
        stopTime = System .nanoTime ();
        for (k = 0; ra .length > k; ++k) {
            l = ra [k] .length;
            value = 0.0;
            for (m = 0; l > m; ++m) {
                if (value < ra [k] [m] .getTol ()) {
                    value = ra [k] [m] .getTol ();
                }
            }
            System .out .println (l + "  ~  " + value);
            for (m = 0; l > m; ++m) {
                ra [k] [m] .display ();
            }
        }
        System .out .println ();
        System .out .println ("Seq: " + ra .length);
        System .out .println ("Time: " + (1.0E-9 * (stopTime - startTime)));
    }
}
 

Файл ProductSearcher.java

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

import java.util.*;

public class ProductSearcher {
    
    private SortedSet <Record>      recordList;
    private List      <Record>    sequenceBuff;
    private List      <Record []> sequenceList;
    
    public ProductSearcher () {
        recordList   = new TreeSet   <> ();
        sequenceBuff = new ArrayList <> ();
        sequenceList = new ArrayList <> ();
    }
    
    public Record [] [] run (long start, long stop, int step, int col, int tol) {
        long subStart, subStop, k, l, k_min, k_max, l_min, l_max, shift;
        Record record, prevRecord;
        Record [] [] result;
        Iterator <Record> iter;
        
        if (2 > tol) {
            tol = 2;
        }
        if (2 > col) {
            col = 2;
        }
        if (10 > step) {
            tol = 10;
        }
        sequenceBuff .clear ();
        sequenceList .clear ();
        
        subStart = start;
        prevRecord = null;
        while (stop > subStart) {
            subStop = Long .min (stop, subStart + step);
            recordList .clear ();
            
            k_min = (long) Math .sqrt (subStart - subStart / tol);
            k_max = (long) Math .sqrt (subStop);
            for (k = k_min; k_max >= k; ++k) {
                l_min = subStart / k + ((0 == subStart % k) ? 0 : 1);
                l_max = subStop  / k;
                l_min = Long .max (l_min, k);
                l_max = Long .min (l_max, k + k / tol);
                for (l = l_min; l_max >= l; ++l) {
                    record = new Record (k, l);
                    if (subStart <= record .product && record .product < subStop) {
                        recordList .add (record);
                    }
                }
            }
            
            iter = recordList .iterator ();
            if (null == prevRecord && iter .hasNext ()) {
                prevRecord = iter .next ();
            }
            while (iter .hasNext ()) {
                record = iter .next ();
                shift = record .product - prevRecord .product;
                if (0 == shift) {
                    continue;
                }
                if (1 != shift) {
                    if (col <= sequenceBuff .size ()) {
                        sequenceList .add (sequenceBuff .toArray (new Record [sequenceBuff .size ()]));
                    }
                    sequenceBuff .clear ();
                }
                sequenceBuff .add (record);
                prevRecord = record;
            }
            
            subStart = subStop;
        }
        
        if (col <= sequenceBuff .size ()) {
            sequenceList .add (sequenceBuff .toArray (new Record [sequenceBuff .size ()]));
        }
        result = sequenceList .toArray (new Record [sequenceList .size ()] []);
        
        sequenceBuff .clear ();
        sequenceList .clear ();
        recordList   .clear ();
        
        return result;
    }
    
    public class Record implements Comparable <Record> {
        
        private long product, first, second;
        
        private Record (long af, long as) {
            if (af <= as) {
                first   = af;
                second  = as;
            } else {
                first   = as;
                second  = af;
            }
            product = first * second;
        }
        
        public double getTol () {
            return ((double) second) / first - 1.0;
        }
        
        public void display () {
            System .out .println (product + " = " + first + " * " + second + "  ~  " + getTol ());
        }
        
        @Override
        public int compareTo (Record arg) {
            int result = Long .compare (product, arg .product);
            if (0 != result) {
                return result;
            }
            return Long .compare (second, arg .second);
        }
    }
}