Как найти сомножители непростых нечётных чисел

[ivanovbp]

Существующие методы нахождения непростых нечетных чисел (далее в тексте - ННЧ) основаны, в сущности, на методе перебора вариантов. Предлагаемый метод - тоже. Но! Если требуется найти сомножители для группы близких по значению ННЧ - этот метод будет самое ТО! Не требует высокоумных математических знаний (достаточно таблицы умножения) и экономит массу времени.
Основан метод на трёх обнаруженных мною правилах.
Правило 1
Ближайшее справа к квадрату простого числа ННЧ всегда делится на 3
Так, для простого числа (далее в тексте - ПЧ) 19 его квадрат равен 361. Ближайшее справа ННЧ = 363 делится на 3.
Для ПЧ = 29 квадрат равен 841. Ближайшее справа ННЧ = 843 - делится на 3. И это справедливо для всех ННЧ, прилегающих справа к квадрату любого простого числа.
Правило 2
Разность между двумя соседними ННЧ, имеющими одинаковый левый сомножитель, всегда равна удвоенному значению этого сомножителя
Например, имею $N_1$ = 77 = 7$\cdot$11
$N_2$ = $N_1$ + (2$\cdot$7) = 77 + 14 = 91 = 7$\cdot$13
$N_3$ = $N_2$ + (2$\cdot$7) = 91 + 14 = 105 = 7$\cdot$15 и т.д.
Правило 3
В диапазоне между квадратами двух соседних простых чисел ни одно ННЧ не может иметь один из сомножителей больше, чем левое простое число
Привожу пример расчета:
Надо найти сомножители для группы ННЧ от 381 до 507. Группа ограничена слева квадратом ПЧ = 19 ($19^2$ = 363), справа квадратом ПЧ = 23 ($23^2$= 529)
1. Ищем ННЧ с сомножителем а = 3
Согласно правилу 1 ближайшее справа ННЧ = 363. Обозначу его как $N_0$ = 363 = 3$\dot{}$121
Последующие ННЧ будут определяться как
$N_1$ = $N_0$ + (2$\dot{}$3) = 363 + 6 = 369
$N_2$ = $N_1$ + (2$\dot{}$3) = 369 + 6 = 375
$N_3$ = $N_2$] + (2$\dot{}$3) = 375 + 6 = 381
......................................................................................
и так до последнего в диапазоне
$N_2_6$ = $N_2_5$+ (2$\dot{}$3) = 513 + 6 = 519
2. Ищем ННЧ с максимальным для диапазона сомножителем а = 19
За $N_0$ принимает квадрат числа 19, т.е. $N_0$ = 361 Следующие ННЧ с этим сомножителем будут
$N_1$ = $N_0$ + (2$\cdot$19) = 361 + 38 = 399
$N_2$ = $N_1$ + (2$\cdot$19) = 399 + 38 = 437
...............................................
$N_4$ = $N_3$ + (2$\cdot$19) = 475 + 38 = 513 - последнее в диапазоне. Все эти ННЧ делятся на 19
Алгоритм чуть усложняется, когда надо найти ННЧ с промежуточными сомножителями а = 7, 11, 13, 17
3. Ищем ННЧ с сомножителем а = 17
а) обозначу как m разность между квадрами ПЧ 19 и 17, т.е. m = $19^2$ - $17^2$ = 361 - 289 = 72
б) введем число k = m / (2$\cdot$17) = 72 / (34) = 2, 117.....,.,.,
в) округляем k до целого числа, т.е. принимаем k = 3
г) определяем $N_0$ как $N_0$ = 289 + (2$\cdot$17) = 391
$N_1 = N_0 $ + (2$\cdot$17) = 425
.....................................................................
$N_4 = N_3 $ + (2$\cdot$17) = 527
Задача решена - сомножители всей группы ННЧ найдены.

[mihaild]

Первые два "правила" очевидны, и упражнение для максмум 5го класса. Третье следует из того, что $p_{n + 1} < 2^{p_n / 2}$.

(Оффтоп)

С другой стороны, мои поздравления, без сарказма: по сравнению с предыдущим, серьезный прогресс - Вам удалось сформулировать несколько верных утверждений. Правда вопрос, умеете ли Вы их доказывать, пока открыт.

А в чем польза-то для народного хозяйства?

[ivanovbp]

mihaild в сообщении #1610953 писал(а):

Первые два "правила" очевидны, и упражнение для максмум 5го класса. Третье следует из того, что $p_{n + 1} < 2^{p_n / 2}$.

(Оффтоп)

С другой стороны, мои поздравления, без сарказма: по сравнению с предыдущим, серьезный прогресс - Вам удалось сформулировать несколько верных утверждений. Правда вопрос, умеете ли Вы их доказывать, пока открыт.

А в чем польза-то для народного хозяйства?

Польза для народного хозяйства очевидная: простота метода и экономия времени
Попробуйте иначе найти сомножители для всех ННЧ, скажем, от 1379 до 1651. Интересно, сколько времени это займёт?
P.S. Мне кажется, "мы с вами где-то встречались"

[mihaild]

ivanovbp в сообщении #1611010 писал(а):

простота метода и экономия времени

Покажите, как Вы считаете время.

ivanovbp в сообщении #1611010 писал(а):

Попробуйте иначе найти сомножители для всех ННЧ, скажем, от 1379 до 1651. Интересно, сколько времени это займёт?

Чуть больше 6 микросекунд https://colab.research.google.com/drive ... sp=sharing.

[Null]

mihaild в сообщении #1611012 писал(а):

Чуть больше 6 микросекунд

Я думаю этот код раскладывает числа на множители независимо. Что-то типа решета Эратосфена будет быстрее. Это похоже на то что предлагает ТС.

[Dmitriy40]

Вряд ли зачем-то надо раскладывать на множители миллиардные-триллионные интервалы чтобы преимущество решета проявилось.
А раскладывать большие числа (от полусотни знаков) никакое решето не поможет.
Так что да, я тоже не вижу преимуществ идеи ТС.

PS. Ну и проводить какие-то тесты на числах короче хотя бы десятка (а лучше пары десятков) знаков не слишком разумно. Если только не для ручного счёта на бумажке.

[mihaild]

Null в сообщении #1611017 писал(а):

Я думаю этот код раскладывает числа на множители независимо

А еще выполняется на неизвестно каком железе неизвестно каким интерпретатором, помимо собственно разложения на множители ходит по хеш-таблицам и т.д.
Но в целом сравнивать время на таком интервале бессмысленно, тут можно всё предпосчитать.

[ozheredov]

(namba theory)

mihaild в сообщении #1611012 писал(а):

https://colab.research.google.com/drive ... sp=sharing

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

from sympy import ntheory

Ничо си, в Питоне уже и такое появилось?

[ivanovbp]

mihaild и другие (цитата из классики):
"Аркадий, не говорите мне красиво..."
Сразу видно, что вы никогда в жизни не занимались работой с конкретным "железом". Много лет назад, ещё при советской власти, мне надо было для нескольких сотен оборонных "штуковин" (между прочим, нечётного числа) найти варианты их прямоугольного размещения. Может быть, вы не знаете, но тогда не было не только компьютеров, но даже электронных калькуляторов. Так что помучиться пришлось.
Предложенный метод - для инженеров-расчётчиков, работающих "на земле", на большее не претендую.

[mihaild]

(Оффтоп)

ozheredov в сообщении #1611042 писал(а):

Ничо си, в Питоне уже и такое появилось?

Что "такое"? Пакет для некоторых простых теоретико-числовых операций? Уже давно.

ivanovbp в сообщении #1611065 писал(а):

Сразу видно, что вы никогда в жизни не занимались работой с конкретным "железом".

Немного занимался, и мне очень интересно, как по двум строчкам на питоне можно это проверить.

ivanovbp в сообщении #1611065 писал(а):

тогда не было не только компьютеров, но даже электронных калькуляторов

Калькуляторы в СССР появились 60 лет назад. Теоретически конечно можно предположить, что Вам условно 85 лет, и Вы в то время уже занимались какими-то рассчетами, но гипотеза что Вы не совсем точны представляется мне более вероятной.

ivanovbp в сообщении #1611065 писал(а):

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

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

[wrest]

Я так понимаю, что ТС готовит нас к временам, когда все компьютеры сломаются и мы вернёмся к таблицам Брадиса. Тут, однако, есть вопрос... А останется ли всё ещё, в таком случае, потребность человечества

ivanovbp в сообщении #1611065 писал(а):

для нескольких сотен оборонных "штуковин" (между прочим, нечётного числа) найти варианты их прямоугольного размещения

[ivanovbp]

mihaild в сообщении #1611089 писал(а):

Немного занимался, и мне очень интересно, как по двум строчкам на питоне можно это проверить
тогда не было не только компьютеров, но даже электронных калькуляторов Калькуляторы в СССР появились 60 лет назад. Теоретически конечно можно предположить, что Вам условно 85 лет, и Вы в то время уже занимались какими-то рассчетами, но гипотеза что Вы не совсем точны представляется мне более вероятной

1. Поясните, что вам интересно. Смогу - отвечу. Только просьба не использовать язык "арго", даже если он профессиональный
2. 85 - не теоретически, а конкретно. И судить о том, где и когда появились калькуляторы, сподручнее мне.

[wrest]

ivanovbp в сообщении #1611010 писал(а):

Попробуйте иначе найти сомножители для всех ННЧ, скажем, от 1379 до 1651.

Дальше буду сопровождать расчетами из pari/gp - это такой калькулятор.
Если я правильно понял что вы предлагаете, то делаем так.
Присвоим переменным a и b значения начала и конца диапазона
? a=1379;b=1651;
Вычисляем квадратный корень из правого конца диапазона и ищем наименьшее простое число, большее этого корня, назовём его p:
? p=nextprime(sqrtint(b));print(p)
41
?
Теперь возьмём начало диапазона и посчитаем остатки от деления его на все удвоенные простые числа q начиная от 3 до p, и соответственно первое нечётное число диапазона, которое делится на q, оно будет нашим первым ННЧ, имеющим множитель q

? forprime(q=3,p,print("Следующее за числом ",a," ННЧ, которое делится на q=",q," равно ",a-a%(2*q)+3*q))
Следующее за числом 1379 ННЧ, которое делится на q=3 равно 1383
Следующее за числом 1379 ННЧ, которое делится на q=5 равно 1385
Следующее за числом 1379 ННЧ, которое делится на q=7 равно 1393
Следующее за числом 1379 ННЧ, которое делится на q=11 равно 1397
Следующее за числом 1379 ННЧ, которое делится на q=13 равно 1417
Следующее за числом 1379 ННЧ, которое делится на q=17 равно 1411
Следующее за числом 1379 ННЧ, которое делится на q=19 равно 1425
Следующее за числом 1379 ННЧ, которое делится на q=23 равно 1403
Следующее за числом 1379 ННЧ, которое делится на q=29 равно 1421
Следующее за числом 1379 ННЧ, которое делится на q=31 равно 1457
Следующее за числом 1379 ННЧ, которое делится на q=37 равно 1443
Следующее за числом 1379 ННЧ, которое делится на q=41 равно 1435
time = 1 ms.
?

Теперь для каждого простого числа q из диапазона от 3 до p, выпишем арифметическую прогрессию нечетных чисел, которые попадают в диапазон между a и b и делятся на q
На примере q=41, получаем
? q=41;forstep(i= a-a%(2*q)+3*q,b,2*q,print1(i," "));print()
1435 1517 1599
?
Это все нечётные непростые числа из диапазона от a=1379 до b=1651, которые делятся на 41
Так же поступаем с остальными $q=3,5,7,\dots,37$

Итого, чтобы разбить все числа из данного диапазона на нечетные не простые числа, которые делятся на все возможные в качестве делителей простые числа, имеем такую программу:

? non_prime_odd(a,b)=print("Задан диапазон от a=",a," до b=",b);forprime(q=3,nextprime(sqrtint(b)), print("ННЧ которые делятся на  ",q,":");forstep(i= a-a%(2*q)+3*q,b,2*q,print1(i," "));print())

Результат её работы для заданного вами диапазона (внимание, много букв и широкие строки):

(Оффтоп)

1. ? non_prime_odd(1379,1651) 
2. Задан диапазон от a=1379 до b=1651 
3. ННЧ которые делятся на  3: 
4. 1383 1389 1395 1401 1407 1413 1419 1425 1431 1437 1443 1449 1455 1461 1467 1473 1479 1485 1491 1497 1503 1509 1515 1521 1527 1533 1539 1545 1551 1557 1563 1569 1575 1581 1587 1593 1599 1605 1611 1617 1623 1629 1635 1641 1647 
5. ННЧ которые делятся на  5: 
6. 1385 1395 1405 1415 1425 1435 1445 1455 1465 1475 1485 1495 1505 1515 1525 1535 1545 1555 1565 1575 1585 1595 1605 1615 1625 1635 1645 
7. ННЧ которые делятся на  7: 
8. 1393 1407 1421 1435 1449 1463 1477 1491 1505 1519 1533 1547 1561 1575 1589 1603 1617 1631 1645 
9. ННЧ которые делятся на  11: 
10. 1397 1419 1441 1463 1485 1507 1529 1551 1573 1595 1617 1639 
11. ННЧ которые делятся на  13: 
12. 1417 1443 1469 1495 1521 1547 1573 1599 1625 1651 
13. ННЧ которые делятся на  17: 
14. 1411 1445 1479 1513 1547 1581 1615 1649 
15. ННЧ которые делятся на  19: 
16. 1425 1463 1501 1539 1577 1615 
17. ННЧ которые делятся на  23: 
18. 1403 1449 1495 1541 1587 1633 
19. ННЧ которые делятся на  29: 
20. 1421 1479 1537 1595 
21. ННЧ которые делятся на  31: 
22. 1457 1519 1581 1643 
23. ННЧ которые делятся на  37: 
24. 1443 1517 1591 
25. ННЧ которые делятся на  41: 
26. 1435 1517 1599 
27. time = 4 ms. 
28. ? 

[ozheredov]

(mihaild)

mihaild в сообщении #1611089 писал(а):

Пакет для некоторых простых теоретико-числовых операций?

В общем да, но меня больше поразило существование sympy. Умеет ли он переплевывать Вольфрам?

[Dedekind]

(Оффтоп)

ozheredov
Нет, там все очень печально, ни в какое сравнение с Вольфрамом.