maxim_arnold: (Warsaw)
[personal profile] maxim_arnold
Интересно, есть тут кто живой? Где-то с месяц тому, на недружественной площадке у горячо любимой супруги, народ обсуждал одну задачку из учебника. И вроде как аж цельный кандидат наук потратил на ту задачку пять минут своего времени.

Вобщем, у меня есть вопрос и я его сегодня, пока не смотрел на дорогу, думал. И ни до какого нормально ответа не додумался. Так что пишу его сюда. Не ответят, так хоть перекличку устроим.

Возьмём N единиц (пусть N достаточно большое) и разрешим использовать четыре арифметических действия и скобки. По-видимому, легко показать, что таким образом можно составить любое число от 1 до 2N-4. Максимальное число, которое можно таким образом получить, вообще где-то очень далеко. Но вполне естественно предположить существование лакун. Кто-нибудь знает какое минимальное число получить нельзя?

Date: 2015-09-28 04:27 pm (UTC)
From: [identity profile] zorgeo.livejournal.com
Поделить самое большое число на количество комбинаций? Только как оценить и то и другое...

Date: 2015-09-28 04:44 pm (UTC)
From: [identity profile] maxim-arnold.livejournal.com
Некоторые числа можно многими способами получить. Так что вроде и такая оценка ничего не даст. Разве нет?

Date: 2015-09-28 07:05 pm (UTC)
From: [identity profile] zorgeo.livejournal.com
Если способов меньше, чем самое большое число - это значит будут лакуны по принципу, извините, дирихле. Если способов больше чем самое большое число -то это ничего не значит.

А что предполагается делать с нецелыми результатами, выкидывать?

Date: 2015-09-28 07:16 pm (UTC)
From: [identity profile] maxim-arnold.livejournal.com
А, ну конечно лакуны будут. Тут нет вопросов. Мне кажется гораздо интереснее найти первое такое число, которое нельзя представить в виде N единиц. Ну например вот если N=8, то я умею получать числа от 1 до 16. А вот 17 так пока и не придумал. А если N=6, то я не умею получать чисел больших 9. А для N=4 я не смог получить число 5. Я вот думаю нет ли тут какого-то паттерна...

Date: 2015-09-28 09:24 pm (UTC)
From: [identity profile] papa-lyosha.livejournal.com
Если запретить деление, то получится: https://oeis.org/A255641
Если деление разрешить, то по-крайне мере до N=20 будет в точности то же.
Если запретить еще вычитание, получится расхождение уже при N=10: https://oeis.org/A005520.
Там есть еще дополнительные ссылки.

Date: 2015-09-29 03:28 pm (UTC)
From: [identity profile] maxim-arnold.livejournal.com
О как! А это очевидно, что такая последовательность экспоненциально себя ведет? Я правда все еще не убедил себя окончательно, что это та же самая последовательность, но вроде бы очень похожа. А про такую же, но из двоек составленную что-нибудь известно?

Date: 2015-09-29 05:24 pm (UTC)
From: [identity profile] type-o-graph.livejournal.com
Из двоек без деления совпадает с натуральными числами, а из двоек с делением вот она: https://oeis.org/A071997

Date: 2015-09-29 05:48 pm (UTC)
From: [identity profile] papa-lyosha.livejournal.com
Мой железный друг, говорит, что из двоек нельзя получить такие числа:
1,2,4,7,11,19,27,43,75,115,171,307,555,...
Такая последовательность не находится, так что думаю конкретно ей никто не интересовался.

Date: 2015-09-29 06:02 pm (UTC)
From: [identity profile] papa-lyosha.livejournal.com
То что растет быстро очевидно: Любое число, состоящие из k цифр в двоичной системе, можно представить из O(k^2) единиц. Например 11=2^3+2^2+1=2*2*2+2*2+1=(1+1)(1+1)(1+1) + (1+1)(1+1) + 1.
Правда получается нижняя оценка не совсем экспоненциальная, а скорее 2O(sqrt n)

Date: 2015-09-29 07:12 pm (UTC)
From: [identity profile] papa-lyosha.livejournal.com
Если для записи чисел использовать схему Горнера (например, 11=1+2(1+2*(1+1)) ), то можно получить настоящую экспоненту. А если использовать троичную систему вместо двоичной, и цифры -1,0,1 вместо 0,1,2, то можно еще чуток сэкономить и получить оценку снизу как O(3n/4).
При этом оценка сверху для максимального числа будет O(3n/3).

Date: 2015-09-30 02:29 am (UTC)
From: [identity profile] maxim-arnold.livejournal.com
Чума. Спасибо. Ума не приложу где бы это могло понадобиться. Хотя там в энциклопедии что-то говорят про теорию сложности, конечно...

Date: 2015-09-29 02:31 pm (UTC)
From: [identity profile] tufoed.livejournal.com
По-видимому, для того, чтобы постановка задачи была корректной, необходимо отказаться от вычитания, т.к. могут получаться отрицательные числа, среди которых нету наименьшего, удовлетворяющего условиям задачи (отрицательных чисел счетно, а чисел, которые можно представить - конечно при каждом N). Также будет необходимо отказаться от деления, из-за такой же ботвы с действительными числами (да, именно действительными, а не рациональными, т.к. число вида 11^(1/11) очевидным образом иррационально). То есть действия останется три. Тремя действиями уже неочевидно, что можно до 2N-4, и по-видимому, это вообще неверно
P.S. Упс, про степень тоне написано ничего, так что действия два.
Edited Date: 2015-09-29 02:38 pm (UTC)

Date: 2015-09-29 03:17 pm (UTC)
From: [identity profile] maxim-arnold.livejournal.com
Не-не-не, Дэвид Блейн. От вычитания я отказываться не хочу потому как 31 я так могу получить при помощи одиннадцати единиц, а без вычитания может оказаться дольше. Кроме того я не разрешал из единиц составлять большие числа. Все-таки составление числа одиннадцать из двух единиц - это такая хитрая операция, аппелирующая к десятичной системе. За такие фокусы в приличных домах и по лицу получить можно. Деление я тоже не хочу запрещать, по причинам, описанным выше. А про 2N-4 - это я погорячился, конечно. На самом деле должно быть просто получить все числа до (N/2)^2. Но вот по ссылке выше вроде бы рост еще быстрее.

Date: 2015-09-30 09:44 am (UTC)
From: [identity profile] tufoed.livejournal.com
31 = ((1+1+1)*(1+1+1)+1)*(1+1+1)+1, не?
А вообще, интересно, что троичная запись оказывается эффективнее двоичной.
Для оценок, кстати, деление не используется.
Edited Date: 2015-09-30 11:21 am (UTC)

Profile

maxim_arnold: (Default)
maxim_arnold

August 2017

S M T W T F S
  12345
6789101112
13141516171819
20 212223242526
2728293031  

Style Credit

Expand Cut Tags

No cut tags
Page generated Sep. 20th, 2017 02:06 am
Powered by Dreamwidth Studios