You are viewing shkrobius

Quizzing the Anonymous - Я так не играю!
April 14th, 2014
06:47 pm

[Link]

Previous Entry Share Next Entry
Я так не играю!
http://edge.org/response-detail/11675
Неужели принципиально невозможно доказать, что обратная последовательность десятичных цифр 2^n никогда не даст 5^m?

Tags:

(41 comments | Leave a comment)

Comments
 
[User Picture]
From:egh0st
Date:April 15th, 2014 12:28 am (UTC)
(Link)
ну это какой-то стрёмный товарищ.

выдвигает статистически-пробалистическую гипотезу и потом что-то "доказывает".

в физике такое прокатит, а вот в матике -- нет. даже если шанс один на миллиард что гипотеза неверна, это не доказательство.

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

[User Picture]
From:shkrobius
Date:April 15th, 2014 01:47 am (UTC)
(Link)
Ненада. Товарищ наш, проверенный.
[User Picture]
From:egh0st
Date:April 15th, 2014 01:55 am (UTC)
(Link)
мне интересно как он это, до 2 ^ 1 000 000 000 все степени "легко" проверил. Одна десятичная запись такой степени (ну по цифре на байт, типа ANSI) это 300+ мегабайт.
[User Picture]
From:shkrobius
Date:April 15th, 2014 03:19 am (UTC)
(Link)
У него ход в самый верх. Все компьютеры Пентагона эту задачу решали.
[User Picture]
From:eterevsky
Date:April 15th, 2014 05:28 am (UTC)
(Link)
Это как раз очень легко. Посчитать скажем последние 30 цифр для всех степеней двойки до миллиардной, и первые 30 цифр для всех степеней пятёрки. Посмотреть, есть ли совпадения.
[User Picture]
From:shkrobius
Date:April 15th, 2014 05:42 am (UTC)
(Link)
Там степени двойки до миллиарда, а не экспоненты до миллиарда. Но Вы правы, конечно.
[User Picture]
From:egh0st
Date:April 17th, 2014 12:36 am (UTC)
(Link)
а как вы собираетесь считать *первые* цифры степеней? если их так легко подсчитать, можно и напрямую сравнивать, для начала первую и последную цифру 2^n и 5^m
[User Picture]
From:eterevsky
Date:April 17th, 2014 11:17 am (UTC)
(Link)
Первые цифры я посчитаю так: возьму дробную часть n * log_10(5) , и возведу 10 в эту степень. Получится примерно столько верных цифр из начала 5^n, с какой точностью считался логарифм.
[User Picture]
From:egh0st
Date:April 17th, 2014 08:10 pm (UTC)
(Link)
это как-то мягко говоря стрёмно. во-первых тут из этого нельзя предсказуемо вывести первые цифры, последовательных степеней, например. С помощью этого можно было и подоказывать, например.

во-вторых сомнительна сама идея возведения 10 в дробную степень. Имхо для относительно небольших чисел, типа 64бит, проще считать напрямую.

Насчёт точности -- правильней будет сказать точность знаков после запятой после умножения на n. А то к примеру для n=50 знать даже первые три знака недостаточно, нужно 0.6989 для угадывания первых двух цифр.
[User Picture]
From:eterevsky
Date:April 17th, 2014 09:00 pm (UTC)
(Link)
> это как-то мягко говоря стрёмно. во-первых тут из этого нельзя предсказуемо вывести первые цифры, последовательных степеней, например. С помощью этого можно было и подоказывать, например.

Не уловил мысль...

> во-вторых сомнительна сама идея возведения 10 в дробную степень. Имхо для относительно небольших чисел, типа 64бит, проще считать напрямую.

Если вопрос про 64 бита -- естественно, но если вам хочется посчитать первые 10 цифр 5^1000000, напрямую считать будет уже напряжно, а с логарифмом -- легко.

> Насчёт точности -- правильней будет сказать точность знаков после запятой после умножения на n.

Согласен.
[User Picture]
From:egh0st
Date:April 15th, 2014 12:48 am (UTC)
(Link)
чисто на правах наброса:

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


было бы любопытно для начала порешать такую же задачу в HEX, особенно учитывая степень двойки. Или в шестеричной. Ну а в пятиричной по идее проще всего.
В пятиричной чтоб делилось на 5 надо заканчивать запись на ноль, что в обратной записи степени двойки не будет гарантированно :)

что касаемо десятиричной, то запись степени двойки всегда должна начинаться от 52, и третьей цифрой или 1, или 6. Нельзя ли такие цифры исключить каким-то другим образом, из других соображений?
То есть в степенях 5ки последние три цифры вовсе не рандомные (в десятичной записи).


[User Picture]
From:salas
Date:April 15th, 2014 01:52 am (UTC)
(Link)
log102 иррационален => множество дробных частей log10(2n) всюду плотно => степеней двойки, десятичная запись которых начинается с 521, бесконечно много.

Edited at 2014-04-15 01:52 am (UTC)
[User Picture]
From:egh0st
Date:April 15th, 2014 02:06 am (UTC)
(Link)
ох старость не радость, универ давно был уже... как второго выводится третье?

кстати чисто по списку этих степеней -- в гугле нашел только первые 222 степени, из них подходила по этому простому признаку только степень 215 (первые три цифры 526)
[User Picture]
From:salas
Date:April 15th, 2014 02:27 am (UTC)
(Link)
1) Десятичная запись числа имеет префикс 521, когда дробная часть логарифма этого числа находится в полуинтервале [log105.21; log105.22).
2) В любом интервале (включая этот) содержится бесконечно много точек всюду плотного множества.

Кстати, к проверке я подошёл бы с той же стороны — чтобы вычислить старшие k цифр 2n с точностью до ±1 (и убедиться, что они не совпадают с младшими цифрами степеней пятёрки), достаточно знать n log102 с точностью 10-k.
[User Picture]
From:egh0st
Date:April 15th, 2014 02:52 am (UTC)
(Link)
чисто на правах колхоза :) а то мне реально через 4 часа вставать на работу.

оценим m через n.

колхозно: (n+3)/2 (ну не двойка там а log2 от 5).

и что, сразу же qed и чтд? :) в исходной записи банально слишком много цифр получается.
[User Picture]
From:salas
Date:April 15th, 2014 03:16 am (UTC)
(Link)
В смысле? Конечно, представляют интерес только такие пары m и n, что m ≈ n log52. И что?
[User Picture]
From:egh0st
Date:April 17th, 2014 12:49 am (UTC)
(Link)
да была идея, но оценка слишком грубая. я даже уточнил оценку, но всё равно фейл :)

уточним кстати вероятность сверху. очевидно что для любой последовательности цифр в десятичной будет не более двух вариантов 5^m, а чаще только один.

у нас 0.4 фактор из-за 4х цифр в конце двойки (2,4,6,8). Итого максимум для данного n вероятность попадания не выше: 0.4*2/(10^n*log2)

Уже при n=100 вероятность порядка 10^-31 и это еще оценка сверху. Шансов мягко говоря немного, но зато если рассмотреть бесконечность этих n, то по идее будет?
[User Picture]
From:shkrobius
Date:April 15th, 2014 01:54 am (UTC)
(Link)
Я не то, что не могу ее решить, а не имею понятия, как можно взяться за такое решение.

Что до автора... что с него взять... PhD и тот не смог получить...
[User Picture]
From:arbat
Date:April 15th, 2014 02:05 am (UTC)
(Link)
Но хоть бакалавра. Гельфанд, тот даже среднюю школу не осилил.
[User Picture]
From:shkrobius
Date:April 15th, 2014 03:24 am (UTC)
(Link)
Мне там история нашего Леона Ледермана понравилась:

My friend, the theoretical physicist, believed so strongly in String Theory, "It must be true!" He was called to testify in a lawsuit, which contested the claims of String Theory against Quantum Loop Gravity. The lawyer was skeptical. "What makes you such an authority?" he asked. "Oh, I am without question the world's most outstanding theoretical physicist", was the startling reply. It was enough to convince the lawyer to change the subject. However, when the witness came off the stand, he was surrounded by protesting colleagues."How could you make such an outrageous claim?" they asked. The theoretical physicist defended, "Fellows, you just don't understand; I was under oath."
[User Picture]
From:egh0st
Date:April 15th, 2014 02:15 am (UTC)
(Link)
интересно что например в HEX или пятиричной системе решение тривиально (таких пар не будет).

почему PhD не дали? :)
[User Picture]
From:shkrobius
Date:April 15th, 2014 03:17 am (UTC)
(Link)
Не просил...
[User Picture]
From:eterevsky
Date:April 15th, 2014 05:32 am (UTC)
(Link)
Он же пишет, что для степеней тройки это не проходит. Так что вероятно в курсе. А из одних первых/поледних цифр ничего не получить, как правильно подсказывают соседние комментаторы.
[User Picture]
From:chaource
Date:April 15th, 2014 01:58 am (UTC)
(Link)
Dyson did not present an argument that this statement is unprovable. He merely said that the digits of 2^n are, in a certain sense, random, and therefore the statement cannot be proved by finding some "rules" describing the sequences of digits of 2^n and 5^n. However, number theorists would probably approach this problem from a totally different angle, not by presenting a rule for the sequences of digits, but by doing something entirely different.
[User Picture]
From:shkrobius
Date:April 15th, 2014 03:27 am (UTC)
(Link)
I've searched and I didn't find the solution. It might be an open problem.
[User Picture]
From:rezoner
Date:April 15th, 2014 03:05 am (UTC)
(Link)
Таких задач можно много придумать. Например, в записи числа пи встречается ли сто нулей подряд?
[User Picture]
From:shkrobius
Date:April 15th, 2014 03:15 am (UTC)
(Link)
Если в шестнадцатиричной системе, то можно решить, есть формула для вычисления любого знака.
[User Picture]
From:rezoner
Date:April 15th, 2014 03:17 am (UTC)
(Link)
Честно говоря, не очень понятно: если речь идет о числе пи, какая разница, в какой системе записи?
[User Picture]
From:shkrobius
Date:April 15th, 2014 03:33 am (UTC)
(Link)
В том, что в 16-ричной можно вычислить N-yю цифру без вычисления всех предыдущих, см.
http://www.math.hmc.edu/funfacts/ffiles/20010.5.shtml
Оттуда же видно, что 100 нулей подряд не будет.
[User Picture]
From:rezoner
Date:April 15th, 2014 03:42 am (UTC)
(Link)
Поразительно.
[User Picture]
From:eterevsky
Date:April 15th, 2014 05:38 am (UTC)
(Link)
А как именно видно, что 100 нулей не будет?
[User Picture]
From:shkrobius
Date:April 15th, 2014 02:26 pm (UTC)
(Link)
Да, я ошибся.
[User Picture]
From:max_i_m
Date:April 27th, 2014 04:28 pm (UTC)
(Link)
Википедия говорит: For example, it is widely believed that the numbers √2, π, and e are normal, but a proof remains elusive. Так что если бы действительно было видно что-то, это было бы открытие (и сюрприз).
[User Picture]
From:shkrobius
Date:April 27th, 2014 04:32 pm (UTC)
(Link)
Ошибся, виноват, исправлюсь.
[User Picture]
From:eterevsky
Date:April 15th, 2014 05:43 am (UTC)
(Link)
Не то чтобы этот факт про 2^n и 5^m принципиально не доказуем. Просто опыт показывает, что такие вот статистически очевидные, но зависящие от конкретного совпадения, гипотезы, оказываются чрезвычайно сложными. Два примера: проблема Гольдбаха и бесконечность множества простых чисел-близнецов. Ни то, ни другое пока не доказано, при том, что про поведение простых чисел известно очень много.
[User Picture]
From:shkrobius
Date:April 15th, 2014 02:18 pm (UTC)
(Link)
Дайсон приводит эту задачку как возможный пример неполноты. Я не понимаю, чем руководствуется такой выбор.
[User Picture]
From:eterevsky
Date:April 15th, 2014 02:43 pm (UTC)
(Link)
Дайсон приводит эвристическое рассуждение, которое должно нас убедить в том, что это утверждение верно и недоказуемо. Это рассуждение конечно не является строгим доказательством, но оно звучит вполне убедительно. Я очень удивлюсь, еслиэтот факт окажется неверен, и ещё более удивлюсь, если кому-то удастся его доказать.

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

Вопрос, вынесенный в заглавие, по всей видимости, подразумевал более скучные примеры типа P ≠ NP, гипотезы Римана и т.п., но они все и так на слуху. Вероятно, именно поэтому Дайсон решил дать такой игрушечный пример.
[User Picture]
From:cousin_it
Date:April 15th, 2014 11:29 am (UTC)
(Link)
I'd like to know what Dyson means when he says the sequence of digits of powers of 2 is "random". For example, it's not Martin-Löf random, because it can be written out by a short program. And it's not cryptographically random, because that program also has a small running time. What concept of randomness is he using?
[User Picture]
From:shkrobius
Date:April 15th, 2014 02:21 pm (UTC)
(Link)
Intuitive one. Wasn't taking the middle digits of a power the first generator of pseudorandom numbers?
[User Picture]
From:rwalk
Date:April 15th, 2014 01:40 pm (UTC)
(Link)
Есть такое понятие "нормальности" (по Борелю) некоторого числа х в основании q. Это означает, что асимпотическая частота любой цифры в q-ичном разложении x существует и равна 1/q, и, более того, то же справедливо и для любого блока из k последовательных цифр - его асимптотическая частота равна 1/qk. В частности, почти всякое число с независимыми равномерно распределенными случайными цифрами явялется нормальным (по-видимому, под случайностью цифр в степенях Дайсон понимает что-то в этом роде - возможно даже с увеличенным наборов тестов на случайность).

Несмотря на наличие BBP формулы, нормальность π по основанию 16, насколько мне известно, все еще не доказана. Отсутствие блока из 100 последовательных нулей очевидным образом опровергало бы нормальность, так что я подозреваю, что ваше утверждение несколько поспешно.

Задача Дайсона все-таки не представляется идеальным кандидатом на роль того примера, о котором Дайсон говорит, и вполне вероятно, что доказательство невозможности могло бы быть получено путем, например, исследования более сложных динамических систем, чем иррациональные повороты окружности.

Кстати, что касается аддитивных задач теории чисел (по поводу которых Ландау хлестко выразился: простые числа созданы для того, чтобы их умножать, а не складывать!), буквально в последние несколько лет был достигнут существенный прогресс в решении как проблемы Гольдбаха (слабая проблема полностью решена Хельфготтом), так и проблемы простых близнецов (Чжан Итан и последующие улучшатели во главе с Тао по состоянию на сегодняшний день доказали, что существует бесконечное количество пар простых чисел с разностью не более 246).
[User Picture]
From:shkrobius
Date:April 15th, 2014 02:34 pm (UTC)
(Link)
Да, поспешил. Грешен.

Проблему Гольдбаха в каждом поколении решало несколько человек, какой-то прогресс был и есть. Проблему Дайсона, наверно, никто решать не будет. Разве что это заковыристое следствие какого-то очень общего утверждения...



My Website Powered by LiveJournal.com