Фон

Последовательность 1-2-3-Трибоначи

Представьте себе на секунду, что вы можете создать последовательность Фибоначчи, заменив стандартную формулу итерации следующим:

По сути, вместо суммирования двух последних, чтобы получить следующее, вы суммируете последние три. Это основа для последовательности 1-2-3-Tribonacci.

Критерий Брауна

Критерий Брауна гласит, что вы можете представлять любое целочисленное значение в виде суммы членов последовательности при условии, что:

1. 

2. Для всех nбольше 1,

Что это значит для вызова

Вы можете описать любое положительное целое число как сумму членов последовательности 1-2-3-Tribonacci, образованной следующими начальными условиями:

Это известно как, для каждого значения в этой последовательности, соотношение между терминами никогда не бывает больше 2 (отношение в среднем составляет около 1,839).

Как написать в этой системе численного представления

Допустим, вы используете представление с прямым порядком байтов. Выстроить членов последовательности так:

1  2  3  6 11 20 37 68

Затем вы берете свое число, которое будет представлено (для наших тестов, скажем, оно 63) и находите значения заданных 1-2-3-Tribonacci, которые в сумме составляют 63 (используя сначала самые большие значения!) . Если число является частью суммы, поставьте 1 под ним, 0, если нет.

1  2  3  6 11 20 37 68
0  0  0  1  0  1  1  0

Вы можете сделать это для любого заданного целого числа - просто убедитесь, что вы сначала используете самые большие значения ниже заданного вами значения!

Определение (наконец)

Напишите программу или функцию, которая будет выполнять следующие действия при условии положительного целочисленного ввода n(записанного в любой стандартной базе) между 1 и максимальным значением вашего языка:

1. Преобразуйте значение в определенное числовое представление 1-2-3-Tribonacci.
2. Используя это двоичное представление, и читайте его, как если бы оно было двоичным. Это означает, что цифры остаются прежними, но их значение меняется.
3. Возьмите это двоичное число и конвертируйте его в основание исходного числа.
4. Выведите или верните этот новый номер.

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

Примеры

Позвольте функции fбыть функцией, описанной определением, и позвольте []представлять шаги, предпринятые (как little-endian, хотя это не должно иметь значения) (вам не нужно следовать этому процессу, это просто процесс, описанный):

>>> f(1)
[1]
[1]
[1]
1

>>> f(5)
[5]
[0, 1, 1]
[6]
6

>>> f(63)
[63]
[0, 0, 0, 1, 0, 1, 1]
[104]
104

Javascript 117 111 байт

Спасибо @theonlygusti за помощь в удалении 5 байтов

x=>{r=0;a=[1,2,3];i=1;while(a[++i]<x)a[i+1]=a[i]+a[i-1]+a[i-2];for(;x;i--)if(x>=a[i]){r+=1<<i;x-=a[i]}return r}

Как это устроено

Во-первых, функция генерирует все числа Tribonacci, пока не найдет одно больше, чем вход

a=[1,2,3];i=1;for(;a[++i]<x;)a[i+1]=a[i]+a[i-1]+a[i-2];

Далее производится обратный поиск по списку номеров. Если число меньше, чем вход, оно добавляет 2 ^ (индекс этого числа) к возвращаемому значению и уменьшает ввод на это число.

for(;x;i--)if(x>=a[i]){r+=1<<i;x-=a[i]}

Наконец, он возвращает результат.

Попробуйте онлайн

Python 2 , 110 102 байта

-3 байта благодаря Роду (изящный трюк для приведения логического значения iк +iцелочисленному типу, поэтому репр `+i`работает)

n=input()
x=[3,2,1]
r=''
while x[0]<n:x=[sum(x[:3])]+x
for v in x:i=n>=v;n-=v*i;r+=`+i`
print int(r,2)

Попробуйте онлайн!

JavaScript (ES6), 97 93 байта

Здесь мы используем reduce()рекурсивную функцию. Мы предполагаем, что вывод является 31-битным (это наибольшее количество без знака, с которым JS может легко работать для побитовых операций в любом случае).

n=>[...Array(x=31)].reduce(p=>(c=(F=k=>k<4?k:F(--k)+F(--k)+F(--k))(x--))>n?p:(n-=c,p|1<<x),0)

С точки зрения производительности это явно не очень эффективно.

Для любопытных:

• Соотношение между количеством вызовов F()для N + 1 reduce()итераций и N итераций быстро сходится к константе Трибоначи (≈ 1.83929). Поэтому каждый дополнительный бит на выходе стоит примерно вдвое больше времени, чем предыдущий.
• С 31 битом эта F()функция называется хорошей 124 миллиона раз.

Тестовое задание

NB. Это может занять 1 или 2 секунды.

let f =

n=>[...Array(x=31)].reduce(p=>(c=(F=k=>k<4?k:F(--k)+F(--k)+F(--k))(x--))>n?p:(n-=c,p|1<<x),0)

console.log(f(63))

Mathematica, 78 74 байта

Fold[#+##&,#~NumberDecompose~Reverse@LinearRecurrence[{1,1,1},{1,2,3},#]]&

LinearRecurrence[{1,1,1},{1,2,3},#]генерирует список, длина которого равна входу, чисел 1-2-3 трибоначи. ( {1,1,1}Представляет сумму предыдущих трех терминов, в то время как {1,2,3}являются начальными значениями.) Затем #~NumberDecompose~находит самый жадный способ записать входные данные в виде суммы элементов списка (это та же самая функция, которая разлагает денежную сумму на кратные доступные валюты, например). Наконец, Fold[#+##&,...]преобразует результирующий двоичный список в целое число (base-10).

Предыдущее представление:

Fold[#+##&,#~NumberDecompose~Reverse@Array[If[#<4,#,Tr[#0/@(#-Range@3)]]&,#]]&

Как это часто бывает (хотя и не выше), эта игра в гольф очень медленная на входах больше 20 или около того, потому что она генерирует (с неоптимизированной рекурсией) список трибов, длина которых является входом; замена финала #на более разумную границу Round[2Log@#+1]приводит к гораздо лучшей производительности.

Haskell, 95 байт

(a!b)c=a:(b!c)(a+b+c)
e#(r,c)|c-e<0=(2*r,c)|1<2=(2*r+1,c-e)
f n=fst$foldr(#)(0,n)$take n$(1!2)3

Пример использования: f 63-> 104. Попробуйте онлайн! ,

Как это работает: !строит последовательность 1-2-3-Tribonacci. Учитывая 1, 2и 3в качестве параметров запуска, мы берем первые nэлементы последовательности. Тогда мы сгиб правой функции , #которая вычитает следующий элемент eиз nи устанавливает бит в возвращаемом значении , rесли eэто необходимо или позволяет битовую неустановленные. Установка бита - это удвоение, rа добавление 1, оставление неустановленным - просто удвоение.

Желе , 31 байт

S=³
3RUµḣ3S;µ<³Ạµ¿µŒPÇÐfṀe@ЀµḄ

Попробуйте онлайн!

Я почти уверен, что есть намного более короткий способ достичь этого в желе.

Как?

S=³ - Link 1, compare sum to input: list
S   - sum
  ³ - 3rd command line argument which is 1st program argument.
 =  - equal?

3RUµḣ3S;µ<³Ạµ¿µŒPÇÐfṀe@ЀµḄ - Main link: n
3RU                         - range(3) upended -> [3,2,1]
   µ    µ   µ¿              - while
         <³                 - less than input (vectorises)
           Ạ                - all?
    ḣ3S;                    -     head(3), sum, and concatenate
                                  [3,2,1] -> [6,3,2,1] -> [11,6,3,2,1] -> ...
              µ             - monadic chain separation, call the result x
               ŒP           - power set of x - e.g. for [6,3,2,1] -> [[],[6],[3],[2],[1],[6,3],[6,2],[6,1],[3,2],[3,1],[2,1],[6,3,2],[6,3,1],[6,2,1],[3,2,1],[6,3,2,1]]
                  Ðf        - filter keep
                 Ç          -     last link (1) as a monad (those that sum to the input)
                    Ṁ       - maximum (e.g. an input of 63 would yield [[37,20,6],[37,20,3,2,1]], the maximum of which is [37,20,6], the one with the largest numbers used)
                         µ  - monadic chain separation (to have x as the right argument below)
                     e@Ѐ   - exists in with reversed arguments mapped over x (e.g. [37,20,6] with x = [68,37,20,11,6,3,2,1] yields [0,1,1,0,1,0,0,0])
                          Ḅ - convert from binary to integer.        

Perl 6 , 93 91 байт

-2 байта благодаря b2gills

{my@f=1,2,3,*+*+*...*>$^n;sum @f».&{$_~~any first *.sum==$n,@f.combinations}Z*(2 X**^∞)}

Как это устроено

• Во-первых, он генерирует последовательность 1-2-3-Tribonacci до первого элемента больше, чем вход:

  my @f = 1, 2, 3, *+*+* ... * > $^n;

• На основании этого он находит подмножество последовательности, которая складывается со входом:

  first *.sum==$n, @f.combinations

• На основании этого он создает список логических значений, определяющих, является ли каждый элемент последовательности частью суммы:

  @f».&{$_~~any ...}

• И, наконец, он интерпретирует этот список значений True = 1, False = 0 как основание 2 и возвращает его как (основание 10) число:

  sum ... Z* (2 X** ^∞)

JavaScript (ES6), 61 60 байт

n=>(g=(x,y,z)=>(n>x&&g(y,z,x+y+z)*2)+!(n<x||![n-=x]))(1,2,3)

Вычисляет числа 1-2-3-Tribonacci до тех пор, пока оно не достигнет исходного числа, а затем, когда рекурсия раскручивается, пытается вычесть каждое из них по очереди, удваивая результат по мере продвижения.

Редактировать: 1 байт сохранен благодаря @Arnauld.

Пакетный, 151 148 145 байтов

@set/ar=0,n=%1
@call:c 3 2 1
@echo %r%
@exit/b
:c
@set/as=%1+%2+%3
@if %n% gtr %3 call:c %s% %*
@set/ar*=2
@if %n% geq %3 set/an-=%3,r+=1

Порт моего JavaScript ответа. Изменить: 3 байта сохранены путем передачи аргументов моей подпрограммы в обратном порядке и еще 3 байта с использованием отдельных @s в каждой строке вместо @echo off.

Желе , 19 18 17 байт

Ḣx3+
BÇL¡2ị
²Ç€»ċ

Попробуйте онлайн!

Фон

Вместо того, чтобы пытаться преобразовать целое число в основание 1,2,3-Трибоначи, затем из двоичного в целое число, мы сделаем обратное: преобразовать целые числа в двоичное, затем из 1,2,3-основание Трионачи в целое число и вернем самый высокий, который соответствует входу. Это легко сделать.

Мы проиллюстрируем процесс для ввода 63 , в частности этап, на котором проверяется 104 . В двоичном, от самой значимой до наименее значащей цифры, 104 равно

 1  1  0  1  0  0  0
37 20 11  6  3  2  1

где вторая строка представляет позиционные значения этих цифр.

Мы можем расширить последовательность 1,2,3-Tribonacci вправо, наблюдая, что добавленные цифры соответствуют той же рекурсивной формуле. Для трех цифр это дает

 1  1  0  1  0  0  0  0  0  0
37 20 11  6  3  2  1  0  1  0

Теперь, чтобы вычислить значение базового числа 1,2,3-Трибоначи, мы можем использовать рекурсивную формулу. Поскольку каждое число является суммой трех чисел справа от него (в таблице выше), мы можем удалить первую цифру и добавить ее к первым трем цифрам оставшегося массива. После 7 шагов, которые равны количеству двоичных цифр в 104 , мы редко оставляем только три цифры.

 1  1  0  1  0  0  0  0  0  0
37 20 11  6  3  2  1  0  1  0

    2  1  2  0  0  0  0  0  0
   20 11  6  3  2  1  0  1  0

       3  4  2  0  0  0  0  0
      11  6  3  2  1  0  1  0

          7  5  3  0  0  0  0
          6  3  2  1  0  1  0

            12 10  7  0  0  0
             3  2  1  0  1  0

               22 19 12  0  0
                2  1  0  1  0

                  41 34 22  0
                   1  0  1  0

                     75 63 41
                      0  1  0

Теперь, поскольку первая и последняя оставшиеся цифры имеют позиционное значение 0 , результатом является средняя цифра, т. Е. 63 .

Как это устроено

²Ç€»ċ   Main link. Argument: n

²       Yield n². Since 1.839² = 3.381921 > 2, the range [1, ..., n²] will contain
        the answer. Better bounds, at the cost of additional bytes are possible.
 Ç€     Map the the second helper link over [1, ..., n²].
   »    Take the maximum of n and each result.
    ċ   Count the occurrences of n.


BÇL¡2ị  Second helper link. Left argument: k. Right argument: n

B       Convert k to binary. Let's call the result A.
  L     Length; count the number of binary digits. Let's call the result l.
 Ç ¡    Apply the first helper link l times to A.
    2ị  Retrieve the second element.


Ḣ×3+    First helper link. Argument: A (array)

Ḣ       Head; pop and yield the first element of A.
 x3     Repeat it thrice.
   +    Add the result, component by component, to the beheaded A.

Желе ( вилка ), 17 16 байт

ḣ3S;µ¡
3RṚdzæFṪḄ

Сохранено 1 байт благодаря @Dennis, который играл в гольф, даже не запустив его.

Это основано на развилке Jelly, где я разочарованно продолжаю работать над реализацией эффективного атома фробениусового решения. Для тех, кто заинтересован, я бы хотел сравниться со скоростью Mathematica, FrobeniusSolveи, к счастью, есть объяснение их метода в статье «Внесение изменений и поиск подмены: балансировка ранца» Даниэля Лихтблау.

объяснение

ḣ3S;µ¡  Helper link. Input: a list
    µ   Create monadic chain
ḣ3        Take the first 3 items
  S       Sum
   ;      Prepend to the list
     ¡  Repeat it n (initial argument from main) times

3RṚdzæFṪḄ  Main link. Input: integer n
3          The constant 3
 R         Range. Makes [1, 2, 3]
  Ṛ        Reverse. Makes [3, 2, 1]
   Ç       Call the helper link on that list.
           Generates the first (n+3) 123-Tribonacci values in reverse
    ³      Get n
     æF    Frobenius solve for n using the first n 123-Tribonacci values in reverse
       Ṫ   Tail. Take the last value. The results of Frobenius solve are ordered
           where the last result uses the least
        Ḅ  Unbinary. Convert digits from base 2 to base 10

постоянный ток , 110 102 байта

?se1sa2sb3sc_1sf[laddSdlbdsalcdsb++sclf1+sfle>y]dsyx0sk[lk2lf^+skler-se]sr[Lddle!<rlf1-dsf0!>z]dszxlkp

Ну, кажется , что великие умы действительно думают одинаково. Очевидно, алгоритм, который я придумал, чтобы обойти ограничения, по dcсовпадению точно такой же, который использовался в ответе @ LliwTelrac. Интересный.

Попробуйте онлайн!

Python 2 , 93 байта

n=input();y=k=n*n
while y>n:
 x=y=z=0;k-=1
 for t in bin(k):x+=t=='1';x,y,z=y+x,z+x,x
print k

Это порт моего желе ответа .

Попробуйте онлайн!

утилиты bash + BSD (OS X и т. д.), 53 байта

jot $[2#$1**4]|egrep -v '[2-9]|11(1|$)'|sed $[2#$1]!d

утилиты bash + GNU (работает также под BSD), 59 байт

seq -f2o%.fp $[2#$1**2]|dc|egrep -v '11(1|$)'|sed $[2#$1]!d

Вход и выход в обоих вышеупомянутых являются двоичными.

Попробуйте версию GNU на TIO. (Пример, связанный с, демонстрирует ввод 111111, который равен 63 в двоичном формате, и вывод 1101000, что составляет 104 в двоичном формате.)

Я не думаю, что TIO предлагает вариант BSD, но если у вас есть Mac, вы можете попробовать их оба там. (59-байтовая программа намного быстрее, чем 53-байтовая программа.)

К сожалению, seqего нельзя просто отбросить в решение BSD вместо jot, так как формат вывода for seqотличается для выходов выше 999999. (Это становится проблемой для входов около 32, так как 32 ^ 4> 1000000.)

Вы можете заменить jotвыше на, seq -f%.fчтобы заставить это работать с утилитами GNU, но для тех же 59 байтов, вы можете использовать вышеуказанное решение GNU, которое намного быстрее.