Latar Belakang

Urutan 1-2-3-Tribonacci

Bayangkan sesaat Anda bisa membuat urutan fibonacci dengan mengganti rumus iterasi standar dengan yang berikut:

Pada dasarnya, alih-alih menjumlahkan dua terakhir untuk mendapatkan yang berikutnya, Anda menjumlahkan tiga terakhir. Ini adalah dasar untuk urutan 1-2-3-Tribonacci.

Kriteria Brown

Kriteria Brown menyatakan bahwa Anda dapat mewakili nilai integer apa pun sebagai jumlah anggota dari suatu urutan asalkan:

1. 

2. Untuk semua yang nlebih besar dari 1,

Apa artinya ini untuk tantangan

Anda dapat menggambarkan bilangan bulat positif sebagai jumlah anggota dari urutan 1-2-3-Tribonacci yang dibentuk oleh kondisi awal berikut:

Ini dikenal sebagai, untuk setiap nilai dalam urutan ini, rasio antara istilah tidak pernah lebih besar dari 2 (rasio rata-rata keluar sekitar 1,839).

Cara menulis dalam sistem representasi numerik ini

Katakanlah Anda menggunakan representasi little-endian. Sejajarkan anggota urutan seperti ini:

1  2  3  6 11 20 37 68

Kemudian, Anda mengambil nomor Anda untuk diwakili (untuk pengujian kami, katakan saja itu 63) dan temukan nilai-nilai yang diberikan 1-2-3-Tribonacci yang berjumlah 63 (menggunakan nilai terbesar pertama!) . Jika nomor tersebut merupakan bagian dari jumlah, tulis 1 di bawahnya, 0 jika tidak.

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

Anda dapat melakukan ini untuk bilangan bulat apa pun yang diberikan - cukup verifikasi bahwa Anda menggunakan nilai terbesar di bawah input yang Anda berikan terlebih dahulu!

Definisi (akhirnya)

Tulis program atau fungsi yang akan melakukan hal berikut ini dengan beberapa input bilangan bulat positif n(ditulis dalam basis standar apa pun) antara 1 dan nilai maksimum bahasa Anda:

1. Ubah nilainya menjadi representasi numerik 1-2-3-Tribonacci yang ditentukan.
2. Menggunakan representasi seperti biner ini, dan membacanya seolah-olah biner. Ini berarti bahwa digitnya tetap sama, tetapi yang mereka maksud berubah.
3. Ambil nomor biner ini dan ubah menjadi basis nomor asli.
4. Keluarkan atau kembalikan nomor baru ini.

Namun, selama outputnya valid, Anda tidak perlu mengikuti langkah-langkah ini. Jika Anda secara ajaib menemukan beberapa rumus yang lebih pendek (dan secara matematis setara), silakan menggunakannya.

Contohnya

Biarkan fungsi fmenjadi fungsi yang dijelaskan oleh definisi, dan biarkan []mewakili langkah-langkah yang diambil (sebagai little-endian, meskipun seharusnya tidak masalah) (Anda tidak perlu mengikuti proses ini, ini hanya proses yang dijelaskan):

>>> 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 byte

Terima kasih kepada @theonlygusti karena membantu bermain golf 5 byte

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}

Bagaimana itu bekerja

Pertama, fungsi ini menghasilkan semua angka tribarbon sampai menemukan yang lebih besar dari input

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

Selanjutnya, itu membalikkan pencarian daftar angka. Jika angka kurang dari input, itu menambah 2 ^ (indeks nomor itu) ke nilai kembali dan mengurangi input dengan angka itu.

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

Akhirnya mengembalikan hasilnya.

Cobalah secara Online

Python 2 , 110 102 byte

-3 byte terima kasih kepada Rod (trik rapi untuk casting boolean ike int dengan +ibegitu repr `+i`bekerja)

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)

Cobalah online!

JavaScript (ES6), 97 93 byte

Di sini, kami menggunakan reduce()fungsi rekursif. Kami berasumsi bahwa outputnya adalah 31-bit (yang merupakan jumlah unsigned terbesar yang dapat dengan mudah digunakan JS untuk operasi bitwise).

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)

Dari segi kinerja, ini jelas tidak terlalu efisien.

Untuk yang penasaran:

• Rasio antara jumlah panggilan untuk F()untuk reduce()iterasi N + 1 vs iterasi N dengan cepat konvergen menuju Tribon Constant (≈ 1,83929). Oleh karena itu, setiap bit tambahan dalam biaya output kira-kira dua kali lebih banyak dari waktu sebelumnya.
• Dengan 31 bit, F()fungsinya disebut baik 124 juta kali.

Uji

NB: Ini mungkin membutuhkan waktu 1 atau 2 detik untuk selesai.

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 byte

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

LinearRecurrence[{1,1,1},{1,2,3},#]menghasilkan daftar, dengan panjang yang sama dengan input, dari angka tribal 1-2-3. (Yang {1,1,1}mewakili jumlah dari tiga istilah sebelumnya, sementara {1,2,3}adalah nilai awal.) Lalu#~NumberDecompose~ menemukan cara paling serakah untuk menulis input sebagai jumlah elemen dari daftar (ini adalah fungsi yang sama yang akan menguraikan jumlah uang menjadi beberapa kelipatan dari mata uang yang tersedia, misalnya). Akhirnya, Fold[#+##&,...]ubah daftar biner yang dihasilkan menjadi integer (basis-10).

Pengajuan sebelumnya:

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

Seperti yang sering terjadi (meskipun tidak di atas), versi golf ini sangat lambat pada input yang lebih besar dari 20 atau lebih, karena menghasilkan (dengan rekursi yang tidak dioptimalkan) daftar suku yang panjangnya adalah input; mengganti final #dengan ikatan yang lebih masuk akal seperti Round[2Log@#+1]menghasilkan kinerja yang jauh lebih baik.

Haskell, 95 byte

(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

Contoh penggunaan: f 63-> 104.Cobalah online! .

Cara kerjanya: !membangun urutan 1-2-3-Tribonacci. Diberikan 1, 2dan 3sebagai parameter awal, kami mengambil nelemen pertama dari urutan. Kemudian kita lipat dari fungsi #yang tepat yang mengurangi elemen berikutnya edari ndan menetapkan bit dalam nilai kembali rjika ediperlukan atau membiarkan bit tidak disetel. Mengatur bit adalah menggandakan rdan menambahkan 1, membiarkannya tidak disetel hanya menggandakan.

Jelly , 31 byte

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

Cobalah online!

Saya hampir yakin ada cara yang jauh lebih pendek untuk mencapai ini di Jelly.

Bagaimana?

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 byte

-2 byte berkat b2gills

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

Bagaimana itu bekerja

• Pertama, ini menghasilkan urutan 1-2-3-Tribonacci hingga elemen pertama yang lebih besar dari input:

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

• Berdasarkan itu ia menemukan subset dari urutan yang menambahkan hingga input:

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

• Berdasarkan itu ia membangun daftar boolean yang menentukan apakah setiap elemen dari urutan adalah bagian dari jumlah:

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

• Dan akhirnya menafsirkan daftar nilai True = 1, False = 0 sebagai basis 2 dan mengembalikannya sebagai nomor (basis 10):

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

JavaScript (ES6), 61 60 byte

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

Hitung angka 1-2-3-Tribonacci sampai mencapai angka asli, kemudian saat rekursi tersebut menghilang, cobalah untuk mengurangi masing-masing secara bergantian, menggandakan hasilnya saat berjalan.

Sunting: Disimpan 1 byte berkat @Arnauld.

Batch, 151 148 145 byte

@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

Port jawaban JavaScript saya. Sunting: Disimpan 3 byte dengan meneruskan argumen subrutin saya dalam urutan terbalik dan 3 byte lainnya dengan menggunakan masing-masing @s pada setiap baris alih-alih @echo off.

Jelly , 19 18 17 byte

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

Cobalah online!

Latar Belakang

Alih-alih mencoba mengubah bilangan bulat menjadi 1,2,3-Basis Tribonacci, lalu dari biner ke bilangan bulat, kami akan melakukan yang sebaliknya: konversi bilangan bulat menjadi biner, lalu dari 1,2,3-Basis Trigram ke bilangan bulat, dan kembali yang tertinggi yang cocok dengan input. Ini mudah dicapai.

Kami akan mencontohkan proses input 63 , khususnya langkah di mana 104 diuji. Dalam biner, dari digit paling signifikan ke paling signifikan, 104 sama dengan

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

di mana baris kedua mewakili nilai posisi digit tersebut.

Kita dapat memperluas deret 1,2,3-Tribonacci ke kanan, mengamati bahwa digit yang ditambahkan sesuai dengan rumus rekursif yang sama. Untuk tiga digit, ini memberi

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

Sekarang, untuk menghitung nilai angka dasar 1,2,3-Tribonacci, kita dapat menggunakan rumus rekursif. Karena setiap angka adalah jumlah dari tiga angka di sebelah kanannya (dalam tabel di atas), kita dapat menghapus digit pertama dan menambahkan ini ke tiga digit pertama dari array yang tersisa. Setelah 7 langkah, yang sama dengan jumlah digit biner 104 , kami jarang pergi dengan hanya tiga digit.

 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

Sekarang, karena digit pertama dan terakhir yang tersisa keduanya memiliki nilai posisi 0 , hasilnya adalah digit tengah, yaitu 63 .

Bagaimana itu bekerja

²Ç€»ċ   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.

Jelly ( garpu ), 17 16 byte

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

Disimpan 1 byte berkat @ Dennis yang bermain golf tanpa menjalankannya.

Ini bergantung pada garpu Jelly di mana saya mengecewakan masih bekerja pada implementasi atom pemecahan Frobenius yang efisien. Bagi mereka yang tertarik, saya ingin mencocokkan kecepatan Mathematica FrobeniusSolvedan untungnya ada penjelasan tentang metode mereka dalam makalah "Membuat Perubahan dan Menemukan Repfigits: Menyeimbangkan Ransel" oleh Daniel Lichtblau.

Penjelasan

ḣ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

dc , 110 102 byte

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

Yah, sepertinya pikiran hebat memang berpikir sama. Ternyata, algoritma yang saya buat untuk mengatasi keterbatasan dcini adalah kebetulan yang sama persis yang digunakan dalam jawaban @ LliwTelrac. Menarik.

Cobalah online!

Python 2 , 93 byte

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

Ini adalah pelabuhan jawaban Jelly saya .

Cobalah online!

bash + BSD Utilities (OS X, dll.), 53 byte

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

bash + Utilitas GNU (berfungsi di bawah BSD juga), 59 byte

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

Input dan output di kedua di atas adalah dalam biner.

Cobalah versi GNU di TIO. (Contoh terkait dengan menunjukkan input 111111, yang 63 dalam biner, dan output 1101000, yang 104 dalam biner.)

Saya rasa TIO tidak menawarkan opsi BSD, tetapi jika Anda memiliki Mac, Anda dapat mencobanya di luar. (Program 59-byte jauh lebih cepat daripada program 53-byte.)

Sayangnya, seqtidak bisa begitu saja dimasukkan ke dalam solusi BSD jot, karena format output untukseq berbeda untuk output di atas 999999. (Ini mulai menjadi masalah untuk input sekitar 32, karena 32 ^ 4> 1000000.)

Anda dapat mengganti di jotatas dengan seq -f%.fagar ini berfungsi dengan utilitas GNU, tetapi untuk 59 byte yang sama, Anda dapat menggunakan solusi GNU di atas, yang jauh lebih cepat.