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…

    Есть два мужика с именами «Van Eck». Первый, в 1985 году показал всему миру как за 15 долларов перехватывать данные с монитора (Van Eck phreaking), второй, в 2010 придумал хитрую последовательность (Van Eck's sequence). Круче простоты задания этой последовательности могут быть только её свойства и загадки.

    Итак, алгоритм генерации членов последовательности. Берем «стартовое число», например «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

    График:

    image


    Еще больше график:

    image

    Довольно легко доказываются свойства последовательности, что её максимальный член все время возрастает и что в ней бесконечное количество нулей. Или что в ней нет периодов. (Несколько теорем и следствий тут.)

    Логарифмический график:

    image


    Прога на 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

    График:

    image


    Для стартового числа «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

    График:

    image


    Источники








    Ads
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More

    Comments 61

      +13
      А есть ли у этой последовательности какие-нибудь полезные свойства?
        +12
        да, она вызывает интерес
          +10
          Успешно используется на собеседованиях для понижения самооценки кандидатов :)
            –2
            С какого перепугу от математических результатов/находок требуют практической пользы?
              +3
              А тогда с какого перепугу нужно платить зарплату математикам?
                +6
                Настоящий математик фигачит вне зависимости от того, платят ему или нет.
                  +2
                  Вы именно так работаете?
                    0
                    В общем — да (например эта статья)
                    хоть по диплому я математик, но в чистую математику вклад не вношу, только популяризаторство, к сожалению. Но вот в комменте ниже товарищ дополнил энциклопедию, это хорошо!
                      +1
                      Я не математик, но скажу вам одну важную истину — математика родилась от людских потребностей. И если математики об этом забудут — про них тоже все забудут.

                      А в плане приведённой вами последовательности, я бы (будь я популяризатором) постарался показать её значимость всем, а не очень узкому кругу фанатеющих по головоломкам. И для этого много не надо, ведь достаточно чуть пошире взглянуть на людские проблемы и найти в математике их решения. Так, например, последовательность простых чисел (слово «последовательность» не напоминает вам о необходимости увидеть общее?) даёт простым гражданам защиту от кражи их денег в интернете, а защита нужна для того, что бы не отрывая известное место от дивана оплачивать различные услуги. Вот вам и связь изучения последовательностей с очень удобным сервисом. И что вам мешало примерно так же указать класс задач, которые решаются именно при помощи алгоритмов, наработанных при исследовании аналогичных последовательностей? То есть общее между «последовательностями вообще» вижу даже я, ни разу не математик, а вы (ведь вроде математик) могли бы расширить классификацию, показать место вашей последовательности в вашей онтологии головоломок, рассказать о достижениях на пути исследования задач из данного класса, и т.д. и т.п.

                      Но вы просто бросили необработанный кирпич в толпу, на что толпа отреагировала абсолютно адекватно — да это же кирпич! Вот обработаете камешек, покажете блеск граней, вот тогда вам скажут — мужик, ты меня удивил!
                +1
                Не то чтобы практической, хотя бы интересность какую-нибудь.
                Зачем мне вобще знать, что так можно числа расставить? Чем последовательность хуже/лучше чем просто натуральные/случайные числа? Может быть её можно применить для решения какой-нибудь (даже чисто теоретической) задачи?
                  –1
                  «Красота – первый тест: в вечности нет места для некрасивой математики».
                  — Г.Х. Харди, Апология математики
                    0
                    Для меня набор чисел без продолжения в виде "… тогда получаем, что..." не является частью красивой математики.
              +6
              В OEIS на текущий момент 326134 последовательности. Почему вы выбрали именно эту?
                –2
                Предложите более интерсную
                  +1
                  Так они там все интересные — в этом и смысл энциклопедии, поскольку общее количество числовых последовательностей бесконечно. В качестве особо интересных лично для меня последовательностей — могу назвать, например, A144815, описывающей коэффициенты для полинома с заданным количеством нулевых производных на краях интервала (-1,1). Я подробно описывал их вывод вот тут, а дополнительный интерес представляет тот факт, что коэффициенты, изначально найденные через решение линейной системы уравнений, можно посчитать через формулу с гамма- и гипергеометрической функциями (которая, к слову, в самой OEIS отсутствует).
                    +1
                    Можно сделать подборку топ-20 самых «интересных» последовательностей
                      +1
                      У Слоана есть документик на эту тему — «My Favorite Integer Sequences» (pdf). Если его перевести — получится замечательная статья.
                        0
                        Ух ты, спасибо! Вчера поискал бегло — ничего стоящего не нашел. А теперь — уууух!!!
                    +1
                    UPD: я тут подумал — а не попробовать ли добавить свою формулу в A144815? И её утвердили! Причём довольно оперативно, в течении пары часов — а значит, энциклопедия живёт и развивается, и не все ещё формулы в математике найдены и опубликованы.
                      0
                      Это?
                      image
                        0
                        Ну вот польза от поста хоть какая-то :)
                          0
                          Безусловно — как минимум народ получил возможность поупражняться в остроумии. Но мне по-прежнему непонятно, почему такая достаточно интересная с точки зрения построения последовательность осталась и без предыстории, и без какой-либо попытки анализа.
                            0
                            В твиттере notch я наткнулся на видеоролик numberphile, очень удивился и поразился, и в 5 утра написал пост. Как-то так.

                            Больше (чем я привел) на эту тему в сети нет информации.
                              0
                              Моя суперспособность — «находить», а не «анализировать». Вот тут на мой взгляд хорошие наброски по анализу.
                          +1
                          Да. А ещё мне показалось, что её автор допустил ошибку, из-за чего эта последовательность теряет свой практический смысл — и мне пришлось подгонять свою формулу под эту ошибку. По этой причине я не нашёл эту последовательность в первый раз. Но кто я такой, чтобы спорить с немецкими профессорами?)
                      +1
                      0
                      Потому что её выбрал человек (Neil Sloane), создатель этой самой OEIS. И сказал что она потрясающая.
                      Вот.
                      +6
                      Интересно. А загадки-то какие?
                        +4
                        Видимо, мы должны придумать их самостоятельно. Например, можно ли посчитать произвольный член этой последовательности за ограниченное количество итераций либо же доказать невозможность этого. Можно было бы рассмотреть количество вхождений заданного числа в некотором интервале этой последовательности. Можно было рассмотреть числа, выраженные цепной дробью с коэффициентами из этой последовательности. Или функции, выраженные рядом с коэффициентами из этой последовательности.
                          0
                          Кроме того, исходя из профиля автора можно предположить, что эта последовательность каким-то образом может помочь в постройке реактивного ранца.
                          +7
                          Я все ждал, когда с помощью этой последовательности и 15 долларов вскроют код сейфа данные с монитора… не дождался.
                            +23
                            Тот случай, когда ждешь какого-то мега-продолжения, а фильмстатья внезапно заканчивается.
                              +4

                              (голосом диктора с ХернТВ) "У этой последовательности множество свойств, по легенде она излечивает все болезни, продлевает жизнь и улучшает карму, но мы не можем их раскрыть, поскольку мировое правительство позаботилось о том, чтобы никто и никогда не узнал этого."

                              +3
                              Круче простоты задания этой последовательности могут быть только её свойства и загадки.

                              В чем конкретно крутость ее свойств и где загадки?
                                +4
                                это первая загадка
                                  0
                                  Ну блин.
                                  Например, почему ранее никто не догадался до такой простой в описании, но безумно сложной по свойствам последовательности? Как упустили?
                                    +1

                                    Скорее всего, потому-что последовательности с "дальнодействием" (для вычисления текущего элемента может понадобиться просмотреть все предыдущие) не встречаются в природе.

                                      0
                                      Кватернионы тоже в природе не встречаются, да и «0» не встречается и ∞.
                                      Да и вообще, математика — это не то что встречается в природе :))) а скорее наоборот.
                                      Ни трейгольников с линиями нулевой толщины, ни чисел в природе нет. (У Бейтсона есть классная заметка про разницу числа и количество)
                                        0
                                        Всё равно я вижу, что мог бы придумать такую последовательность в 9 классе
                                +9
                                Если на втором графике в статье (который называется «Еще больше график») провести аппроксимированную прямую по «гипотенузе» визуально наблюдаемого «треугольника», а затем определить угол между этой прямой и осью абсцисс — может оказаться, что это оптимальный угол для стрельбы из пушки по воробьям.
                                  0

                                  Угол, кстати, 45 градусов.

                                    0

                                    О, вот и загадка!

                                      +2
                                      А вот и свойство: второе число всегда 0.
                                        0
                                        Допишем статью за автора! Больше загадок!
                                          0
                                          для всех натуральных чисел третье число всегда 0, а четвертое 1
                                        0
                                        Значит, случайный член последовательности примерно равен своему номеру?
                                          0

                                          С ненулевой (и довольно высокой, как я понимаю) вероятностью. (Там вроде бы -1 ещё, если начальный член считать за первый, а если считать как программисты, то все ОК) И да, N+1-й член будет нулем в случае истинности вашего утверждения для некоторого N.


                                          Ха, я нагнал. aN меньше или равен N-aN-1 для любого N, потому как ненулевые члены последовательности соответствуют парам уже находящихся в последовательности одинаковых элементов. Вот только угла точнее 45 градусов для верхней границы ИМХО не подобрать...

                                        –1
                                        оптимальный угол для стрельбы из пушки по воробьям.

                                        Из рогатки птицами в свиней же. Пушки и воробьи — это анахронизм.
                                        0
                                        Swift
                                        struct 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))
                                        
                                          0
                                          Фу, вербозно и нечитаемо.

                                          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 0
                                            0
                                            Красиво и непонятно ) Но уж какие средства есть! Да, «вербозно и (при этом) нечитаемо» — противоречие же!
                                          0
                                          Глянул сразу в Вики на последовательность Фибоначчи (со школы только про кроликов помню). Похоже, «была бы последовательность, а закономерности найдутся».
                                            0
                                            Фингербокс в мире последовательностей?
                                              0
                                              Вы забыли ещё написать, что в 1955 году была основана компания VanEck.
                                                +1
                                                Заметно, что с увеличением стартового числа пиковые значения появляются реже.
                                                  0

                                                  То есть, при стартовом значении, стремящемся к бесконечности, все вырождается в прямую?

                                                  +1
                                                  То что все числа последовательности не превысят какого-то значения ограниченного прямой линией и так понятно, так же как интуитивно понятно, что гипотеза Римана верна, но как говорится: «Попробуй докажи».

                                                  Возьмите и выпишите каждый n-й член последовательности, а потом покажите криптографу. Если у последовательности действительно нет периодов, а для вычисления каждого последующего числа, нужна вся последовательность целиком, то можно замутить довольно интересный ГПСЧ.

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

                                                  Ну и напоследок. Получаемое множество чисел последовательности является перечислимым, однако попробуйте подобрать полином который мог бы генерировать данную последовательность. Что-то мне подсказывает, что и сам этот полином будет весьма и весьма, прям ваще как весьма интересным.

                                                  Спасибо автор, за то что я провалялся в кровати без сна до самого рассвета. Среди всех ваших статей, эта оказалась для меня самой интересной.
                                                    0

                                                    Инициализировать ГПСЧ замучаетесь. Если брать псевдослучайный int64 для инициализации, то для полкучения точных значений последовательности вам понадобятся ВСЕ значения с индексами, меньшими переданного на вход.

                                                      0
                                                      Вопрос реализации сложный, но решаемый. Может показаться, что данный алгоритм должен потреблять много памяти, но не факт, что обязан. Длина используемых последовательностей может быть ограничена. Начальные значения, как и значения шага, могут быть результатом какой нибудь простой, даже линейной функции.
                                                      +1
                                                      Спасибо на добром слове!
                                                      (сам опубликовал в 5 утра)

                                                    Only users with full accounts can post comments. Log in, please.