Хабр Курсы для всех
РЕКЛАМА
Большая витрина: от крупнейших школ до частных авторов. Сравнивайте по цене, длительности, формату и выбирайте самый подходящий курс!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 11
Например, при n=12 получится последовательность 1, 2, 4, 7, 11, 4, 10, 5, 1, 10, 8, 7. Видно в ней есть повторяющиеся числа.
А для n=8, последовательность будет 1, 2, 4, 7, 3, 8, 6, 5. И в ней повторяющихся чисел нет.
Простите, но не совсем понятна суть. Если в первом случае есть закономерность — постепенное приращение шага на 1, то как получилась последовательность после 7 во втором?
Мне ваше доказательство показалось недостаточно чистым — в нём много рассуждений, но мало математики. По крайней мере у меня после прочтения не возникло ощущения «да, всё строго доказано».
Более чистое решение я вижу в более строгой формализации. Начать с вывода формулы для последовательности {1, 2, 4, 7, 11, 16, 22, 29, 37,...} Для n-го члена ею будет (2-n+n^2)/2. Затем формализовать критерий повторяемости — например, что сумма n членов по модулю n должна совпадать с суммой n первых натуральных чисел {1,2,3,4,5,...} — исходя из того, что от перестановки мест слагаемых сумма не меняется (тут, конечно, нужно дополнительное доказательство на что, что подобная формализация корректна и достаточна — что вообще не факт, просто она первой пришла мне в голову). Ну и т.д. Модульной арифметикой я не увлекаюсь и как подобные задачи решаются «по-взрослому» не знаю — но подозреваю, что нужно привлекать поля Галуа.
Более чистое решение я вижу в более строгой формализации. Начать с вывода формулы для последовательности {1, 2, 4, 7, 11, 16, 22, 29, 37,...} Для n-го члена ею будет (2-n+n^2)/2. Затем формализовать критерий повторяемости — например, что сумма n членов по модулю n должна совпадать с суммой n первых натуральных чисел {1,2,3,4,5,...} — исходя из того, что от перестановки мест слагаемых сумма не меняется (тут, конечно, нужно дополнительное доказательство на что, что подобная формализация корректна и достаточна — что вообще не факт, просто она первой пришла мне в голову). Ну и т.д. Модульной арифметикой я не увлекаюсь и как подобные задачи решаются «по-взрослому» не знаю — но подозреваю, что нужно привлекать поля Галуа.
Возможно и так. Просто я люблю всё делать как можно проще. Ещё со школы такая манера. Это не хорошо и не плохо, просто стиль такой.
Что не возникло ощущения «да, всё строго доказано», согласен. Например единственность представления числа 3*n где n степень двойки, надо обосновать более подробно. Ряд других утверждений тоже нуждается в дополнительном обосновании. Так что это скорее канва доказательства, чем доказательство.
Что не возникло ощущения «да, всё строго доказано», согласен. Например единственность представления числа 3*n где n степень двойки, надо обосновать более подробно. Ряд других утверждений тоже нуждается в дополнительном обосновании. Так что это скорее канва доказательства, чем доказательство.
P.S. Если хотите, попытайтесь формально доказать, что любое число не являющееся степенью двойки представимо в виде суммы двух или более последовательных чисел, а любая степень двойки не представима. Сумма первых n чисел натурального ряда равна n*(n+1)/2. Следовательно любая частичная сумма равна
s(m, n) = (m*(m+1) — n*(n+1))/2 где m>n.
Докажите что это число никогда не будет степенью двойки! Мне вот например так сразу в голову ничего и не приходит. Хотя конечно попытаюсь это сделать. С другой стороны используя простейшие соображения четности/кратности, я это достаточно строго доказал (я не рассмотрел случаи когда k>1, но они сводятся к тому же и не особо интересны). Так что упрощенческий подход порой не так уж и плох. Хотя да, согласен, порой оставляет в стороне какие-то тонкие, и интересные сами по себе аспекты задачи. Возможно именно поэтому я так и не стал профессиональным математиком. Для меня это просто хобби.
s(m, n) = (m*(m+1) — n*(n+1))/2 где m>n.
Докажите что это число никогда не будет степенью двойки! Мне вот например так сразу в голову ничего и не приходит. Хотя конечно попытаюсь это сделать. С другой стороны используя простейшие соображения четности/кратности, я это достаточно строго доказал (я не рассмотрел случаи когда k>1, но они сводятся к тому же и не особо интересны). Так что упрощенческий подход порой не так уж и плох. Хотя да, согласен, порой оставляет в стороне какие-то тонкие, и интересные сами по себе аспекты задачи. Возможно именно поэтому я так и не стал профессиональным математиком. Для меня это просто хобби.
P.P.S. Извиняюсь, но то что степень двойки не представима суммой последовательных чисел, формально всё-таки доказал, причём очень просто. Гораздо проще чем в статье.
s(m, n) = (m*(m+1) — n*(n+1))/2 = (m^2 + m — n^2 — n)/2 = (m^2 — n^2 — (m — n))/2 = ((m-1)*(m+1) + (m-1))/2 = (m-n)*(m+n+1)/2.
Поскольку речь о степенях двойки, множитель 1/2 можно отбросить. Итого, речь о равенстве степени двойки выражения (m-n)*(m+n+1). Но как очень просто видеть, четность выражений (m-n) и (m+n+1) будет разная. Одновременно четными они быть не могут. А значит сумма последовательных чисел никак не может быть степенью двойки. Доказательство гораздо более простое чем у меня. Так что прошу прощения за тупость.
s(m, n) = (m*(m+1) — n*(n+1))/2 = (m^2 + m — n^2 — n)/2 = (m^2 — n^2 — (m — n))/2 = ((m-1)*(m+1) + (m-1))/2 = (m-n)*(m+n+1)/2.
Поскольку речь о степенях двойки, множитель 1/2 можно отбросить. Итого, речь о равенстве степени двойки выражения (m-n)*(m+n+1). Но как очень просто видеть, четность выражений (m-n) и (m+n+1) будет разная. Одновременно четными они быть не могут. А значит сумма последовательных чисел никак не может быть степенью двойки. Доказательство гораздо более простое чем у меня. Так что прошу прощения за тупость.
Доказывать то, что что-то чем-то непредставимо — вообще сложнее. Лично мне хватило чисто численного доказательства — для того, чтобы после 100 подряд степеней двойки появилось какое-то отличное от степени двойки число — должна быть соответствующая сложность вычислений, заложенная в исходных данных. Но её там нет. Как, например, если нужно найти полином для ряда {1,2,3,4,5} — то это скорее всего просто x. А если после 5 вдруг пойдёт 7, то будет уже -120+394*x-225*x^2+85*x^3-15*x^4+x^5)/120. Коэффициенты у этого полинома друг от друга не зависимы — поэтому они не могут взяться магическим образом и должны быть заложены в исходные данные.
Эту задачу можно ещё рассмотреть с точки зрения комплексных чисел. Стрелка — это единичный вектор, поворот — возведение в степень. Число, на которое он указывается — аргумент (находится через арктангенс). Поскольку скорость вращения линейно возрастет — то получается ничто иное как ЛЧМ, линейно-частотная модуляция. А что с этим делать дальше — я пока не понимаю)
Эту задачу можно ещё рассмотреть с точки зрения комплексных чисел. Стрелка — это единичный вектор, поворот — возведение в степень. Число, на которое он указывается — аргумент (находится через арктангенс). Поскольку скорость вращения линейно возрастет — то получается ничто иное как ЛЧМ, линейно-частотная модуляция. А что с этим делать дальше — я пока не понимаю)
Не могу не отметить, что можно код
if condition:
return True
return Falseзаменить на
return condition:)
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Сижу за решеткой в темнице сырой