Генератор чисел Смита

[Nataly-Mak]

Сейчас просмотрела тему о поиске простых чисел (о новом алгоритме).
В этой связи хочу озадачить форумчан генерацией чисел Смита (или просто смитов). Как выяснилось, генерировать смиты намного сложнее, чем простые числа; для выявления смитов необходимо раскладывать числа на простые множители.
Поскольку числа Смита появились сравнительно недавно, то и алгоритмов их генерации ещё не так много, как для генерации простых чисел. На форуме Портала ЕН в теме "Числа Смита" один участник представил генератор чисел Смита. Я воспользовалась этим генератором и сгенерировала массив смитов в интервале (1, 100000). Но это, разумеется, очень маленький массив.
В теме "Магические квадраты" несколько участников сделали свои генераторы смитов. Например, maxal предлагает всем желающим файл со смитами где-то в пределах нескольких миллиардов. Но и этот массив не достаточен для решения моих задач, связанных с построением наименьших магических квадратов из последовательных смитов.
Но отвлечёмся от магических квадратов. Вот, например, в каком интервале "лежит" восьмёрка смитов-близнецов? А девятка смитов-близнецов? Кстати, девятка смитов-близнецов вполне сгодилась бы для построения магического квадрата 3-го порядка.
Можно ли сделать генератор смитов в некотором заданном интервале, как это можно сделать для простых чисел? К примеру, от 1 до 30 миллиардов смиты проверены и магический квадрат 3х3 из последовательных смитов в этом интервале не построился. Теперь генерируем смиты в интервале от 30 миллиардов до 100 миллиардов, например. И снова проверяем на предмет построения магического квадрата 3х3. Ведь следующие смиты никак не связаны с предыдущими смитами и поэтому, как мне кажется, можно генерировать смиты в любом заданном интервале. Правильно?

[Ираклий]

Позволю себе не вполне приличный вопрос: зачем оно надо?
Простые числа это вещь важная, это понятно. Но смиты целиком и полностью зависят от выбора системы счисления. Чем они интересны? Палиндромы, например, хотя бы симпатишные.

[Nataly-Mak]

Ну, дорогой товарищ, вопрос старый, как мир! Вы не могли бы быть немножко пооригинальней?
Ответ будет такой: мне оно надо для построения магических квадратов. Другим оно надо для тренировки мозгов. Вы вот найдите, например, девятку смитов-близнецов, а потом мы поговорим (когда найдёте)
Представьте себе: магические квадраты прекрасно строятся из последовательных смитов для порядков больше 9 (уже до порядка 50 построены; созданы уникальные программы для такого построения, автор программ Stefano Tognon). А вот магические квадраты порядков 3 - 5 и 7 - 9 не могу построить. И не только я ведь не могу, никто пока не смог. Ах, а может быть, вы можете? Попробуйте-ка!
И вот обидно: такая замечательная последовательность из минимальных магических констант квадратов из последовательных смитов имеет два пробела (а я собираюсь эту последовательность в OEIS предложить). И интересен факт, что наименьший квадрат порядка 6 из последовательных смитов построился с ходу (из самых меньших смитов), как только участник форума сделал программу построения нетрадиционных магических квадратов порядка 6.

Ещё замечу: где бы я ни написала о магических или о латинских квадратах, сразу получаю этот же самый вопрос "а зачем оно надо". Странный какой-то вопрос для тех, кто любит математику.

[Ираклий]

Что они Вам нужны для построения магических квадратов это я догадался Но почему именно из смитов? Сам Смит их в связи с чем придумал, не в курсе? (А то я, знаете, могу тоже такого напридумывать! Будете магические квадраты из ираклиев строить )
Впрочем, мне понятно Ваше негодование относительно вопроса "зачем это надо". Мне тоже приходилось его слышать..

[Nataly-Mak]

Ираклий в сообщении #264030 писал(а):

Но почему именно из смитов?

А почему строили магические квадраты из простых чисел? Вы не в курсе?

Если вы придумаете оригинальные числа и их назовут вашим именем, может быть, и из этих чисел магические квадраты будут строить. Но вы сначала придумайте

[Nataly-Mak]

В OEIS числа Смита представлены в последовательности A006753. Представлено очень немного чисел, от 4 до 1086. Я не читаю по-английски, поэтому не знаю, есть ли в этой статье Энциклопедии ссылка на генератор чисел Смита. А такая ссылка не помешала бы.
По-моему, нет генератора чисел Смита и в Википедии (правда, я давно не заглядывала в эту статью). Кстати, желательно обновить некоторые данные о числах Смита в Википедии.
maxal, предлагаю вам сделать это, поскольку вы сгенерировали очень большой массив смитов.

[Андрей АK]

А какие у вас магические квадраты?
Поскольку в числах Смита используется сложение их цифр ... то и в магических квадратах надо складывать не сами числа , а их цифры.
И назвать их "цифровые магические квадраты Смита".
Тогда можно взять любой уже готовый магический квадрат, и подбирать числа Смита уже согласно сумме их цифр.
Думаю, что такие квадраты будут в два раза "магичнее", чем обычные.

[Nataly-Mak]

Андрей АK в сообщении #267694 писал(а):

Поскольку в числах Смита используется сложение их цифр ... то и в магических квадратах надо складывать не сами числа , а их цифры.
И назвать их "цифровые магические квадраты Смита". ...
Думаю, что такие квадраты будут в два раза "магичнее", чем обычные.

Почему же магические квадраты, полученные сложением цифр чисел Смита, а не самих этих чисел, будут в два раза магичнее?
Представьте, пожалуйста, хотя бы один "цифровой магический квадрат Смита". Попробую оценить его магичность.
Обычные магические квадраты (в смысле всем известного определения нетрадиционных магических квадратов) из чисел Смита представлены в теме "Магические квадраты", а также в моих статьях об этих квадратах (ссылки на статьи приведены в указанной теме).

[Андрей АK]

Цитата:

Почему же магические квадраты, полученные сложением цифр чисел Смита, а не самих этих чисел, будут в два раза магичнее?

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

Nataly-Mak в сообщении #267756 писал(а):

Представьте, пожалуйста, хотя бы один "цифровой магический квадрат Смита". Попробую оценить его магичность.

Ну на такие "наезды" , я обычно отвечаю строкой из своего любимого анекдота: "Я - не тактик, Я - стратег"!
Это ведь ваше любимое занятие - составлять магические квадраты.
Вот я вам и подбрасываю новые идеи для творчества...

[Nataly-Mak]

Вообще-то данная тема посвящена не магическим квадратам, а генератору чисел Смита.

Подбрасывать идеи все мастера, а вот реализовывать их что-то мало желающих.

[maxal]

Nataly-Mak в сообщении #263846 писал(а):

Можно ли сделать генератор смитов в некотором заданном интервале, как это можно сделать для простых чисел? К примеру, от 1 до 30 миллиардов смиты проверены и магический квадрат 3х3 из последовательных смитов в этом интервале не построился. Теперь генерируем смиты в интервале от 30 миллиардов до 100 миллиардов, например. И снова проверяем на предмет построения магического квадрата 3х3.

Я вам уже отвечал на этот вопрос: post262856.html#p262856

[Nataly-Mak]

Цитата:

Проблема тут не столько с большими числами (с ними PARI/GP работает без проблем), сколько в долгом времени работы - каждый новый миллиард требует для прогонки все большего и большего времени. А гарантий, что решение есть хотя бы меньшее 10^{15} - никаких.

Вы имеете в виду этот ответ?

Но мне всё равно непонятно (уж извините за бестолковость ), почему сгенерировать смиты, например, в двадцатом миллиарде можно, а в пятидесятом миллиарде (то есть в интервале от 49 миллиардов до 50 миллиардов) уже нельзя. Неужели нет (например, в Maple) эффективного метода разложения больших чисел на простые множители? Или такую методику ещё не придумали?

[maxal]

Nataly-Mak в сообщении #274303 писал(а):

почему сгенерировать смиты, например, в двадцатом миллиарде можно, а в пятидесятом миллиарде (то есть в интервале от 49 миллиардов до 50 миллиардов) уже нельзя

Кто сказал, что нельзя? Сгенерировать можно, но это займет больше времени.
В частности, планка в 30 миллиардов была достигнута за несколько недель счёта. Однако рано или поздно такой безрезультатный счёт начинает надоедать - и я потерял к нему интерес. Это не значит, что нельзя продвинуться дальше, а всего лишь то, что лично я больше не хочу тратить на подобный счёт вычислительные ресурсы. И, судя по всему, другим это также неинтересно.

Nataly-Mak в сообщении #274303 писал(а):

Неужели нет (например, в Maple) эффективного метода разложения больших чисел на простые множители?

Все известные алгоритмы факторизации являются субэкспоненциальными, и поэтому время их работы очень чуствительно к размеру факторизуемых чисел. Большие числа требуют заметно большего времени.

[Nataly-Mak]

Цитата:

В частности, планка в 30 миллиардов была достигнута за несколько недель счёта. Однако рано или поздно такой безрезультатный счёт начинает надоедать - и я потерял к нему интерес. Это не значит, что нельзя продвинуться дальше, а всего лишь то, что лично я больше не хочу тратить на подобный счёт вычислительные ресурсы. И, судя по всему, другим это также неинтересно.

О вас я уже давно всё поняла. Тема открыта не для вас одного. Тут много других.
То, что в теме нет ответов, ещё не означает, что это никому неинтересно.
Счёт не может быть совсем безрезультатным. Результат рано или поздно появится
Опять приведу пример простых чисел (только, пожалуйста, не говорите, что для простых чисел всё проще - это я тоже уже поняла). Найдены арифметические прогрессии, в которых фигурируют числа из нескольких сотен цифр. Ведь вот кто-то занимается таким счётом. А для чего нужны все эти прогрессии из простых чисел? Есть ли какое-то практическое применение этих прогрессий? Неужели тоже ищут эти прогрессии из любви к искусству?
Так же, как я строю свои магические квадраты.

И есть ли какие-то оригинальные и интересные алгоритмы поиска арифметических прогрессий из простых чисел (либо из каких-то других чисел, например, из смитов)? Насколько я поняла, все участники форума ищут такие прогрессии (из смитов) простым перебором. Разве такой тупой перебор может быть интересен? Интересны разработки алгоритмов, не связанных с тупым перебором. Кроме того, например, в тех же магических квадратах в большинстве случаев простой перебор всех вариантов выполнить просто невозможно за реальное время.

Кстати, нашли (зачем-то??) пятёрки, шестёрки и семёрки смитов-близнецов. О восьмёрках и девятках смитов-близнецов в Википедии не сообщается. Наверное, пока не найдены. А, между прочим, девятка смитов-близнецов - это готовый магический квадрат 3-го порядка из последовательных смитов.
Может, кто найдёт?

[maxal]

Nataly-Mak в сообщении #274326 писал(а):

Счёт не может быть совсем безрезультатным. Результат рано или поздно появится

А если он появится через 10 лет или через 100 или через 1000? Лично у меня нет столько времени.

Nataly-Mak в сообщении #274326 писал(а):

И есть ли какие-то оригинальные и интересные алгоритмы поиска арифметических прогрессий из простых чисел (либо из каких-то других чисел, например, из смитов)?

Есть. Вот например статья на эту тему:
http://compgeom.cs.uiuc.edu/~jeffe/pubs/pdf/arith.pdf