Итак, алгоритм генерации членов последовательности. Берем «стартовое число», например «0», выписываем. Следующий член — это то, сколько шагов назад встречалось это число в предыдущей под-последовательности. Если ни разу, то пишем ноль. Следующее — это сколько шагов назад встречался ноль в предыдущей под-последовательности, то есть один шаг назад. Записываем единицу. Единица впервые — пишем ноль. Опа, ноль встречался два шага назад. Пишем два, и так далее…
Для точки отчета «0» первые 97 членов последовательности:
0, 0, 1, 0, 2, 0, 2, 2, 1, 6, 0, 5, 0, 2, 6, 5, 4, 0, 5, 3, 0, 3, 2, 9, 0, 4, 9, 3, 6, 14, 0, 6, 3, 5, 15, 0, 5, 3, 5, 2, 17, 0, 6, 11, 0, 3, 8, 0, 3, 3, 1, 42, 0, 5, 15, 20, 0, 4, 32, 0, 3, 11, 18, 0, 4, 7, 0, 3, 7, 3, 2, 31, 0, 6, 31, 3, 6, 3, 2, 8, 33, 0, 9, 56, 0, 3, 8, 7, 19, 0, 5, 37, 0, 3, 8, 8, 1
График:
Еще больше график:
Довольно легко доказываются свойства последовательности, что её максимальный член все время возрастает и что в ней бесконечное количество нулей. Или что в ней нет периодов. (Несколько теорем и следствий тут.)
Логарифмический график:
Прога на Python:
A181391 = [0]
last_pos = {}
for i in range(10**4):
new_value = i - last_pos.get(A181391[i], i)
A181391.append(new_value)
last_pos[A181391[i]] = i
# Ehsan Kia, Jun 12 2019Для стартового числа «1» первая сотня такая:
1, 0, 0, 1, 3, 0, 3, 2, 0, 3, 3, 1, 8, 0, 5, 0, 2, 9, 0, 3, 9, 3, 2, 6, 0, 6, 2, 4, 0, 4, 2, 4, 2, 2, 1, 23, 0, 8, 25, 0, 3, 19, 0, 3, 3, 1, 11, 0, 5, 34, 0, 3, 7, 0, 3, 3, 1, 11, 11, 1, 3, 5, 13, 0, 10, 0, 2, 33, 0, 3, 9, 50, 0, 4, 42, 0, 3, 7, 25, 40, 0, 5, 20, 0, 3, 8, 48, 0, 4, 15
График:
Для стартового числа «2» первая сотня такая:
2, 0, 0, 1, 0, 2, 5, 0, 3, 0, 2, 5, 5, 1, 10, 0, 6, 0, 2, 8, 0, 3, 13, 0, 3, 3, 1, 13, 5, 16, 0, 7, 0, 2, 15, 0, 3, 11, 0, 3, 3, 1, 15, 8, 24, 0, 7, 15, 5, 20, 0, 5, 3, 12, 0, 4, 0, 2, 24, 14, 0, 4, 6, 46, 0, 4, 4, 1, 26, 0, 5, 19, 0, 3, 21, 0, 3, 3, 1, 11, 42, 0, 6, 20, 34, 0, 4, 20, 4
График:
Источники
- Van Eck's sequence (wikipedia)
- The Van Eck Sequence (IB Maths Resources from British International School Phuket)
- A181391 (On-Line Encyclopedia of Integer Sequences)
- A171911 (On-Line Encyclopedia of Integer Sequences)
- A171912 (On-Line Encyclopedia of Integer Sequences)
Комментарии (61)
Refridgerator
20.08.2019 06:49В OEIS на текущий момент 326134 последовательности. Почему вы выбрали именно эту?
MagisterLudi Автор
20.08.2019 13:09Предложите более интерсную
Refridgerator
20.08.2019 16:43+1Так они там все интересные — в этом и смысл энциклопедии, поскольку общее количество числовых последовательностей бесконечно. В качестве особо интересных лично для меня последовательностей — могу назвать, например, A144815, описывающей коэффициенты для полинома с заданным количеством нулевых производных на краях интервала (-1,1). Я подробно описывал их вывод вот тут, а дополнительный интерес представляет тот факт, что коэффициенты, изначально найденные через решение линейной системы уравнений, можно посчитать через формулу с гамма- и гипергеометрической функциями (которая, к слову, в самой OEIS отсутствует).
MagisterLudi Автор
20.08.2019 17:22Можно сделать подборку топ-20 самых «интересных» последовательностей
Refridgerator
21.08.2019 18:10+1У Слоана есть документик на эту тему — «My Favorite Integer Sequences» (pdf). Если его перевести — получится замечательная статья.
MagisterLudi Автор
21.08.2019 18:29Ух ты, спасибо! Вчера поискал бегло — ничего стоящего не нашел. А теперь — уууух!!!
MagisterLudi Автор
21.08.2019 18:30Вот Кнут баловался последовательностями — habr.com/ru/company/goto/blog/352386
Refridgerator
20.08.2019 22:36UPD: я тут подумал — а не попробовать ли добавить свою формулу в A144815? И её утвердили! Причём довольно оперативно, в течении пары часов — а значит, энциклопедия живёт и развивается, и не все ещё формулы в математике найдены и опубликованы.
MagisterLudi Автор
20.08.2019 22:46Это?
MagisterLudi Автор
20.08.2019 22:46Ну вот польза от поста хоть какая-то :)
Refridgerator
21.08.2019 09:08Безусловно — как минимум народ получил возможность поупражняться в остроумии. Но мне по-прежнему непонятно, почему такая достаточно интересная с точки зрения построения последовательность осталась и без предыстории, и без какой-либо попытки анализа.
MagisterLudi Автор
21.08.2019 15:53В твиттере notch я наткнулся на видеоролик numberphile, очень удивился и поразился, и в 5 утра написал пост. Как-то так.
Больше (чем я привел) на эту тему в сети нет информации.MagisterLudi Автор
21.08.2019 16:50Моя суперспособность — «находить», а не «анализировать». Вот тут на мой взгляд хорошие наброски по анализу.
Refridgerator
21.08.2019 09:06Да. А ещё мне показалось, что её автор допустил ошибку, из-за чего эта последовательность теряет свой практический смысл — и мне пришлось подгонять свою формулу под эту ошибку. По этой причине я не нашёл эту последовательность в первый раз. Но кто я такой, чтобы спорить с немецкими профессорами?)
MagisterLudi Автор
21.08.2019 17:16Потому что её выбрал человек (Neil Sloane), создатель этой самой OEIS. И сказал что она потрясающая.
Вот.
NeoCode
20.08.2019 07:16+2Интересно. А загадки-то какие?
Refridgerator
20.08.2019 07:58Видимо, мы должны придумать их самостоятельно. Например, можно ли посчитать произвольный член этой последовательности за ограниченное количество итераций либо же доказать невозможность этого. Можно было бы рассмотреть количество вхождений заданного числа в некотором интервале этой последовательности. Можно было рассмотреть числа, выраженные цепной дробью с коэффициентами из этой последовательности. Или функции, выраженные рядом с коэффициентами из этой последовательности.
Refridgerator
20.08.2019 09:35+1Кроме того, исходя из профиля автора можно предположить, что эта последовательность каким-то образом может помочь в постройке реактивного ранца.
fndrey357
20.08.2019 08:14+4Я все ждал, когда с помощью этой последовательности и 15 долларов вскроют код
сейфаданные с монитора… не дождался.
Groramar
20.08.2019 08:23+5Тот случай, когда ждешь какого-то мега-продолжения, а
фильмстатья внезапно заканчивается.roscomtheend
20.08.2019 09:01+4(голосом диктора с ХернТВ) "У этой последовательности множество свойств, по легенде она излечивает все болезни, продлевает жизнь и улучшает карму, но мы не можем их раскрыть, поскольку мировое правительство позаботилось о том, чтобы никто и никогда не узнал этого."
Ununtrium
20.08.2019 09:18+3Круче простоты задания этой последовательности могут быть только её свойства и загадки.
В чем конкретно крутость ее свойств и где загадки?nowfine
20.08.2019 13:51+3это первая загадка
MagisterLudi Автор
20.08.2019 14:16Ну блин.
Например, почему ранее никто не догадался до такой простой в описании, но безумно сложной по свойствам последовательности? Как упустили?Deosis
21.08.2019 09:34+1Скорее всего, потому-что последовательности с "дальнодействием" (для вычисления текущего элемента может понадобиться просмотреть все предыдущие) не встречаются в природе.
MagisterLudi Автор
21.08.2019 16:00Кватернионы тоже в природе не встречаются, да и «0» не встречается и ?.
Да и вообще, математика — это не то что встречается в природе :))) а скорее наоборот.
Ни трейгольников с линиями нулевой толщины, ни чисел в природе нет. (У Бейтсона есть классная заметка про разницу числа и количество)MagisterLudi Автор
21.08.2019 16:23Всё равно я вижу, что мог бы придумать такую последовательность в 9 классе
Xander_Vi
20.08.2019 09:27+5Если на втором графике в статье (который называется «Еще больше график») провести аппроксимированную прямую по «гипотенузе» визуально наблюдаемого «треугольника», а затем определить угол между этой прямой и осью абсцисс — может оказаться, что это оптимальный угол для стрельбы из пушки по воробьям.
vesper-bot
20.08.2019 10:18Угол, кстати, 45 градусов.
alexxisr
20.08.2019 10:37Значит, случайный член последовательности примерно равен своему номеру?
vesper-bot
20.08.2019 11:47С ненулевой (и довольно высокой, как я понимаю) вероятностью. (Там вроде бы -1 ещё, если начальный член считать за первый, а если считать как программисты, то все ОК) И да, N+1-й член будет нулем в случае истинности вашего утверждения для некоторого N.
tvr
20.08.2019 12:07оптимальный угол для стрельбы из пушки по воробьям.
Из рогатки птицами в свиней же. Пушки и воробьи — это анахронизм.
infund
20.08.2019 11:38Swiftstruct VanEck { static func sequence(firstnum : Int, count : Int) -> [Int] { var temp = [firstnum] for i in 0..<count-1 { guard let newValue = temp[0..<i].lastIndex(of: temp.last!) else { temp.append(0); continue } temp.append(i - newValue) } return temp } } // usage print(VanEck.sequence(firstnum: 0, count: 100))assembled
20.08.2019 14:04Фу, вербозно и нечитаемо.
J:
load 'primitives'
NB. получает последовательность, возвращает следующий элемент
next =: tally - 1 + curtail indexoflast tail
NB. добавляем следующий элемент к последовательности x-1 раз
vanEck =: dyad def '(, next)power(x - 1) y'
NB. любуемся
echo 100 vanEck 0infund
20.08.2019 14:26Красиво и непонятно ) Но уж какие средства есть! Да, «вербозно и (при этом) нечитаемо» — противоречие же!
DonArmaturo
20.08.2019 11:57Глянул сразу в Вики на последовательность Фибоначчи (со школы только про кроликов помню). Похоже, «была бы последовательность, а закономерности найдутся».
uchitel
21.08.2019 08:38То что все числа последовательности не превысят какого-то значения ограниченного прямой линией и так понятно, так же как интуитивно понятно, что гипотеза Римана верна, но как говорится: «Попробуй докажи».
Возьмите и выпишите каждый n-й член последовательности, а потом покажите криптографу. Если у последовательности действительно нет периодов, а для вычисления каждого последующего числа, нужна вся последовательность целиком, то можно замутить довольно интересный ГПСЧ.
Каждый последующий член зависит не от какого-то конкретного фиксированного числа предыдущих элементов, а от произвольной предыстории последовательности, что делает саму последовательность весьма любопытной для теории чисел. Например можно ли подобрать такой первый член последовательности, что бы все ее последующие члены имели наперед известные свойства. Или что бы среди ее членов не было чисел имеющих определенные свойства.
Ну и напоследок. Получаемое множество чисел последовательности является перечислимым, однако попробуйте подобрать полином который мог бы генерировать данную последовательность. Что-то мне подсказывает, что и сам этот полином будет весьма и весьма, прям ваще как весьма интересным.
Спасибо автор, за то что я провалялся в кровати без сна до самого рассвета. Среди всех ваших статей, эта оказалась для меня самой интересной.vesper-bot
21.08.2019 09:38Инициализировать ГПСЧ замучаетесь. Если брать псевдослучайный int64 для инициализации, то для полкучения точных значений последовательности вам понадобятся ВСЕ значения с индексами, меньшими переданного на вход.
uchitel
21.08.2019 12:30Вопрос реализации сложный, но решаемый. Может показаться, что данный алгоритм должен потреблять много памяти, но не факт, что обязан. Длина используемых последовательностей может быть ограничена. Начальные значения, как и значения шага, могут быть результатом какой нибудь простой, даже линейной функции.
alexxisr
А есть ли у этой последовательности какие-нибудь полезные свойства?
nowfine
да, она вызывает интерес
GCU
Успешно используется на собеседованиях для понижения самооценки кандидатов :)
MagisterLudi Автор
С какого перепугу от математических результатов/находок требуют практической пользы?
user_man
А тогда с какого перепугу нужно платить зарплату математикам?
MagisterLudi Автор
Настоящий математик фигачит вне зависимости от того, платят ему или нет.
user_man
Вы именно так работаете?
MagisterLudi Автор
В общем — да (например эта статья)
хоть по диплому я математик, но в чистую математику вклад не вношу, только популяризаторство, к сожалению. Но вот в комменте ниже товарищ дополнил энциклопедию, это хорошо!
user_man
Я не математик, но скажу вам одну важную истину — математика родилась от людских потребностей. И если математики об этом забудут — про них тоже все забудут.
А в плане приведённой вами последовательности, я бы (будь я популяризатором) постарался показать её значимость всем, а не очень узкому кругу фанатеющих по головоломкам. И для этого много не надо, ведь достаточно чуть пошире взглянуть на людские проблемы и найти в математике их решения. Так, например, последовательность простых чисел (слово «последовательность» не напоминает вам о необходимости увидеть общее?) даёт простым гражданам защиту от кражи их денег в интернете, а защита нужна для того, что бы не отрывая известное место от дивана оплачивать различные услуги. Вот вам и связь изучения последовательностей с очень удобным сервисом. И что вам мешало примерно так же указать класс задач, которые решаются именно при помощи алгоритмов, наработанных при исследовании аналогичных последовательностей? То есть общее между «последовательностями вообще» вижу даже я, ни разу не математик, а вы (ведь вроде математик) могли бы расширить классификацию, показать место вашей последовательности в вашей онтологии головоломок, рассказать о достижениях на пути исследования задач из данного класса, и т.д. и т.п.
Но вы просто бросили необработанный кирпич в толпу, на что толпа отреагировала абсолютно адекватно — да это же кирпич! Вот обработаете камешек, покажете блеск граней, вот тогда вам скажут — мужик, ты меня удивил!
alexxisr
Не то чтобы практической, хотя бы интересность какую-нибудь.
Зачем мне вобще знать, что так можно числа расставить? Чем последовательность хуже/лучше чем просто натуральные/случайные числа? Может быть её можно применить для решения какой-нибудь (даже чисто теоретической) задачи?
MagisterLudi Автор
«Красота – первый тест: в вечности нет места для некрасивой математики».
— Г.Х. Харди, Апология математики
alexxisr
Для меня набор чисел без продолжения в виде "… тогда получаем, что..." не является частью красивой математики.