Comments 8
Интересно! Я и не знал об этой задаче. Шум с ВТФ утих давно уже, с ABC — всё неясно, а вот еще есть красивые вещи оказывается.
А на архив.орг выложили уже?
А на архив.орг выложили уже?
Пара вопросов про необходимое условие(2):
- Пусть n! не превышает некоторой степени k простого числа p — имеется ввиду, что n! <= p^k?
- На все степени p очевидно делится m^2 — 1, а не m^2
- F(k) — почему единственный параметр k, а не n и p?
Здравствуйте!
1. Да
2. Опечатка, поправил
3. Потому что рассматривается необходимое условие для постоянного p. В общем виде, действительно можно исследовать некоторую функцию G(n,p). Пока не считаю необходимым менять этот пункт в статье.
Спасибо за редактуру!
1. Да
2. Опечатка, поправил
3. Потому что рассматривается необходимое условие для постоянного p. В общем виде, действительно можно исследовать некоторую функцию G(n,p). Пока не считаю необходимым менять этот пункт в статье.
Спасибо за редактуру!
Уважаемый автор!
Можно ли всю вашу работу свести к одному утверждению:
Факториальные числа в десятичной записи после 7! заканчиваются на такое количество нулей, что алгоритмически невозможно найти точный квадрат целого числа, и, уменьшив его на единицу, получить такое же количество нулей?
Можно ли всю вашу работу свести к одному утверждению:
Факториальные числа в десятичной записи после 7! заканчиваются на такое количество нулей, что алгоритмически невозможно найти точный квадрат целого числа, и, уменьшив его на единицу, получить такое же количество нулей?
Здравствуйте! Нельзя. В целых:
1. Квадратных чисел вида k1 00..001, имеющих ровно k2 нулей в десятичной записи, бесконечно много. Так, квадрат числа, оканчивающегося k2 нулями и единицей будет также оканчиваться на k2 нулей и единицу. Суть в том, что ни один из таких квадратов, вероятно, не попадает в промежуток (ai, bi), содержащий факториал некоторого числа.
2. Учитывая свойства факториала, достаточно большое значение m^2, претендующее на выполнение равенства 1, будет иметь вид k1j 00..001 с k2j нулями в системах исчисления с основаниями 2..c, где j — основание системы исчисления, c — константа. Акцент на десятичную систему исчисления в работе не делается. Более того, для программной реализации рекомендован 2-тест.
1. Квадратных чисел вида k1 00..001, имеющих ровно k2 нулей в десятичной записи, бесконечно много. Так, квадрат числа, оканчивающегося k2 нулями и единицей будет также оканчиваться на k2 нулей и единицу. Суть в том, что ни один из таких квадратов, вероятно, не попадает в промежуток (ai, bi), содержащий факториал некоторого числа.
2. Учитывая свойства факториала, достаточно большое значение m^2, претендующее на выполнение равенства 1, будет иметь вид k1j 00..001 с k2j нулями в системах исчисления с основаниями 2..c, где j — основание системы исчисления, c — константа. Акцент на десятичную систему исчисления в работе не делается. Более того, для программной реализации рекомендован 2-тест.
Уважаемый автор, ответ понят.
Но, извините, давайте глянем свойство полного квадрата из Википедии:
«Две последние цифры квадрата в десятичной записи могут принимать значения 00, 01, 04, 09, 16, 21, 24, 25, 29, 36, 41, 44, 49, 56, 61, 64, 69, 76, 81, 84, 89 или 96 (квадратичные вычеты по модулю 100).»
Тогда понятно, что вам нужен хороший критерий на проверку k1j 00..001 на то, что это — полный квадрат. Допустим теоретико-числовой «квадрат не может оканчиваться нечётным количеством нолей», «квадрат либо делится на 4, либо при делении на 8 даёт остаток 1; „квадрат либо делится на 9, либо при делении на 3 даёт остаток 1.“
Кстати, можно рассмотреть еще один способ.
Сумма цифр у любого квадрата есть 9n,9n+1,9n+4,9n+7.
Но только сумма цифр 9n дает в квадрате число, похожее на искомый вами факториал: (10^n-1)^2=(Число 9 повторенное n-1 раз)8(число 0 повторенное n-1 раз)1.
Но факториала такого вида не существует. Проверяется построением факториала.
Теорема доказана, за изъятием случаев из вашей статьи.
Но, извините, давайте глянем свойство полного квадрата из Википедии:
«Две последние цифры квадрата в десятичной записи могут принимать значения 00, 01, 04, 09, 16, 21, 24, 25, 29, 36, 41, 44, 49, 56, 61, 64, 69, 76, 81, 84, 89 или 96 (квадратичные вычеты по модулю 100).»
Тогда понятно, что вам нужен хороший критерий на проверку k1j 00..001 на то, что это — полный квадрат. Допустим теоретико-числовой «квадрат не может оканчиваться нечётным количеством нолей», «квадрат либо делится на 4, либо при делении на 8 даёт остаток 1; „квадрат либо делится на 9, либо при делении на 3 даёт остаток 1.“
Кстати, можно рассмотреть еще один способ.
Сумма цифр у любого квадрата есть 9n,9n+1,9n+4,9n+7.
Но только сумма цифр 9n дает в квадрате число, похожее на искомый вами факториал: (10^n-1)^2=(Число 9 повторенное n-1 раз)8(число 0 повторенное n-1 раз)1.
Но факториала такого вида не существует. Проверяется построением факториала.
Теорема доказана, за изъятием случаев из вашей статьи.
Спасибо за ответ!
В моём понимании, решение задачи Брокара разбивается на 2 части: увеличение нижней границы для новых корней уравнения 1 и доказательство его (уравнения) неразрешимости для достаточно больших n.
1. Временная сложность О от количества цифр в числе для алгоритма, проверяющего любое из необходимых условий: «квадрат не может оканчиваться нечётным количеством нолей», «квадрат либо делится на 4, либо при делении на 8 даёт остаток 1» «квадрат либо делится на 9, либо при делении на 3 даёт остаток 1», «Сумма цифр у любого квадрата есть 9n,9n+1,9n+4,9n+7» будет больше, чем временная сложность алгоритма, реализующего 2-тест. При прямом переборе всех значений m^2-1 из промежутка (ai, bi) можно комбинировать несколько необходимых условий. Например для каждых восьми последовательных чисел подвергать p-тесту те три, которые делятся на 4 или дают остаток 1 при делении на 8. Но комбинирование известных свойств квадрата между собой не даёт такой средней скорости проверки значений n, как 2-тест в чистом виде. Это связано, прежде всего, со средней длиной цепочки последних цифр, необходимой для того, чтобы заключить, что число m не обладает P-свойством. Статистические данные опубликую, когда закончу эффективную реализацию 2-теста.
2. С теоретической точки зрения, я считаю утверждение об отсутствии корней уравнения 1 для n>7 недостаточно сильным и предполагаю в своей работе, что для целых m>71 множество M1 чисел вида m^2-1 не пересекается с некоторым множеством целых чисел M2, включающим n! для всех n>7 и «некоторые другие» числа, имеющие вид k1j 00..001 при записи с системах исчисления с основаниями 2..c, где с — константа. По этой причине числа вида "(цифра 9, повторённая n-1 раз) 8 (цифра 0, повторённая n-1 раз) 1" не исключаются из рассмотрения.
«Тогда понятно, что вам нужен хороший критерий на проверку k1j 00..001 на то, что это — полный квадрат», «Теорема доказана, за изъятием случаев из вашей статьи» — рассмотрите ту же задачу за пределами десятичной системы исчисления. С интересом жду следующего комментария!
В моём понимании, решение задачи Брокара разбивается на 2 части: увеличение нижней границы для новых корней уравнения 1 и доказательство его (уравнения) неразрешимости для достаточно больших n.
1. Временная сложность О от количества цифр в числе для алгоритма, проверяющего любое из необходимых условий: «квадрат не может оканчиваться нечётным количеством нолей», «квадрат либо делится на 4, либо при делении на 8 даёт остаток 1» «квадрат либо делится на 9, либо при делении на 3 даёт остаток 1», «Сумма цифр у любого квадрата есть 9n,9n+1,9n+4,9n+7» будет больше, чем временная сложность алгоритма, реализующего 2-тест. При прямом переборе всех значений m^2-1 из промежутка (ai, bi) можно комбинировать несколько необходимых условий. Например для каждых восьми последовательных чисел подвергать p-тесту те три, которые делятся на 4 или дают остаток 1 при делении на 8. Но комбинирование известных свойств квадрата между собой не даёт такой средней скорости проверки значений n, как 2-тест в чистом виде. Это связано, прежде всего, со средней длиной цепочки последних цифр, необходимой для того, чтобы заключить, что число m не обладает P-свойством. Статистические данные опубликую, когда закончу эффективную реализацию 2-теста.
2. С теоретической точки зрения, я считаю утверждение об отсутствии корней уравнения 1 для n>7 недостаточно сильным и предполагаю в своей работе, что для целых m>71 множество M1 чисел вида m^2-1 не пересекается с некоторым множеством целых чисел M2, включающим n! для всех n>7 и «некоторые другие» числа, имеющие вид k1j 00..001 при записи с системах исчисления с основаниями 2..c, где с — константа. По этой причине числа вида "(цифра 9, повторённая n-1 раз) 8 (цифра 0, повторённая n-1 раз) 1" не исключаются из рассмотрения.
«Тогда понятно, что вам нужен хороший критерий на проверку k1j 00..001 на то, что это — полный квадрат», «Теорема доказана, за изъятием случаев из вашей статьи» — рассмотрите ту же задачу за пределами десятичной системы исчисления. С интересом жду следующего комментария!
Sign up to leave a comment.
Обобщение задачи Брокара