Latar Belakang

Sebagian besar dari Anda tahu angka Fibonacci . Beberapa dari Anda mungkin tahu bahwa semua bilangan bulat positif dapat direpresentasikan sebagai jumlah dari satu atau lebih angka Fibonacci yang berbeda, menurut Teorema Zeckendorf . Jika jumlah istilah dalam Representasi Zeckendorf optimal dari integer nsendiri merupakan nomor Fibonacci, kami akan memanggil nFibonacci "diam-diam".

Sebagai contoh:

139 = 89 + 34 + 13 + 3
This is a total of 4 integers. Since 4 is not a Fibonacci number, 139 is not secretly Fibonacci

140 = 89 + 34 + 13 + 3 + 1
This is a total of 5 integers. Since 5 is a Fibonacci number, 140 is secretly Fibonacci

Catatan

• Representasi Zeckendorf yang optimal dapat ditemukan menggunakan algoritma serakah. Cukup ambil angka Fibonacci terbesar <= n dan kurangi dari n hingga Anda mencapai 0
• Semua angka Fibonacci dapat direpresentasikan sebagai jumlah dari 1 angka Fibonacci (sendiri). Karena 1 adalah angka Fibonacci, semua angka Fibonacci juga merupakan Fibonacci diam-diam.

Tantangan

Tantangan Anda adalah menulis program atau fungsi yang mengambil bilangan bulat dan mengembalikan apakah bilangan bulat itu adalah Fibonacci.

Memasukkan

Anda dapat mengambil input dalam format apa pun yang masuk akal. Anda dapat berasumsi bahwa input akan berupa bilangan bulat positif tunggal.

Keluaran

Keluarkan salah satu dari dua hasil berbeda untuk apakah input tersebut diam-diam merupakan Fibonacci. Contohnya termasuk True/ False, 1/ 0, dll.

Mencetak gol

Ini kode-golf , jadi jawaban tersingkat dalam byte menang! Celah standar dilarang.

Uji Kasus

Truthy (secretly Fibonacci)
1
2
4
50
140
300099

Falsey (NOT secretly Fibonacci)
33
53
54
139
118808

JavaScript (Node.js) , 54 byte

x=>g(g(x))<2;g=(x,i=1,j=1)=>j>x?x&&g(x-i)+1:g(x,j,i+j)

Cobalah online!

Python 2 , 77 byte

def f(n):z=[bin(x).count('1')for x in range(n*n+1)if x&2*x<1];print z[z[n]]<2

Cobalah online!

Ini menggunakan teorema bahwa kedua deskripsi OEIS A003714 adalah setara:

Angka Fibbinary: jika $n = F(i_1) + F(i_2) + \dots + F(i_k)$ adalah representasi Zeckendorf dari $n$ (yaitu, tulis $n$ dalam sistem angka Fibonacci) maka $a(n) = 2^{i_1} + 2^{i_2} + \dots + 2^{i_k}$ . Juga angka yang representasi binernya tidak mengandung dua angka yang berdekatan $1$ini

Kami menghasilkan cukup * angka-angka seperti itu, dan kemudian digunakan zsebagai pemetaan dari bilangan bulat non-negatif ke “berapa banyak istilah dalam representasi Zeckendorf dari $n$ ?” Dengan menghitung 1 dalam biner.

Maka tetap untuk memeriksa apakah z[n]adalah angka Fibonacci, yaitu z[z[n]] == 1.

^{* Setidaknya, $n^2+1$ terasa seperti cukup, dan eksperimen itu tampaknya cukup. Saya akan membuktikannya nanti.}

Jelly , 15 byte

‘ÆḞ€fRṪạµƬL’Ɗ⁺Ị

Tautan monadik yang menerima bilangan bulat non-negatif yang menghasilkan 1jika "Fibonacci Diam-diam" dan 0sebaliknya.

Cobalah online! (terlalu tidak efisien untuk kasus uji yang lebih besar)

Bagaimana?

‘ÆḞ€fRṪạµƬL’Ɗ⁺Ị - Link: integer, I
        µƬ      - perform the monadic link to the left as a function of the current I,
                - collecting up all the inputs until the results are no longer unique:
‘               -   increment I -> I+1
 ÆḞ€            -   nth Fibonacci number for €ach n in [1,I+1]
     R          -   range from 1 to I
    f           -   filter discard (discard Fibonacci numbers not in the range, i.e. > I)
      Ṫ         -   tail (get the largest)
       ạ        -   absolute difference with I
                - This gives us a list from I decreasing by Fibonacci numbers to 0
                - e.g. for 88 we get [88,33,12,4,1,0]
                -      because (88-33)+(33-12)+(12-4)+(4-1)+(1-0)=55+21+8+3+1=88 
          L     - length (the number of Fibonacci numbers required plus one)
           ’    - decrement (the number of Fibonacci numbers required)
            Ɗ   - treat the last three links (which is everything to the left) as a monad:
             ⁺  - ...and repeat it
                - i.e. get the number of Fibonacci numbers required for the number of
                -      Fibonacci numbers required to represent I.
                -      This is 1 if I is Secretly Fibonacci, and greater if not)
              Ị - insignificant? (is the absolute value of that <= 1?)

R , 83 byte

function(n){T=1:0
while(n>T)T=c(T[1]+T[2],T)
while(n){n=n-T[T<=n][1]
F=F+1}
F%in%T}

Cobalah online!

C # (.NET Core) , 124 115 98 byte

a=>{int n=0,b,c;for(;a>0;a-=b,n++)for(b=c=1;c<=a;b=c-b)c+=b;for(b=c=1;c<n;c+=b)b=c-b;return c==n;}

Cobalah online!

-3 byte: diubah saat loop ke untuk (terima kasih kepada Olivier Grégoire )
-6 byte: beralih kembali untuk menggunakan variabel, diinisialisasi b dan c di luar loop (terima kasih kepada Kevin Cruijssen )
-17 byte: perubahan kondisi di loop kedua untuk bergerak jika keluar dari loop dan bergabung dengan return, variabel b dan c digunakan kembali dalam loop terakhir (terima kasih kepada raznagul )

Tidak Disatukan:

a => {
    int n = 0, b, c;                        // initialize variables

    for(; a > 0; a -= b, n++)               // increase n until a is 0
        for(b = c = 1; c <= a; b = c - b)   // set b and c to 1 for each a; set second largest Fibonacci number until largest Fibonacci number reaches a
            c += b;                         // set largest Fibonacci number of current sequence

    for(b = c = 1; c < n; c += b)           // while e is less than or equal to n, continue incrementing largest (e) Fibonacci number in the sequence
        b = c - b;                          // increment second-largest (d) Fibonacci number

    return c == n;                          // if c equals n, a is a secret Fibonacci number
}

Perl 6 , 58 byte

{(1,&[+]...*>$_)∋($_,{$^n-(1,&[+]...^*>$n).tail}...0)-1}

Cobalah online!

1, &[+] ... * > $_ hanyalah urutan Fibonacci, berhenti di tempat yang nyaman dan tidak terbatas (nomor input).

$_, { $^n - (1, &[+] ...^ * > $n).tail } ... 0adalah urutan angka, dimulai dengan angka input, dan setiap elemen berturut-turut diperoleh dengan mengurangi angka Fibonacci terbesar kurang dari atau sama dengan elemen sebelumnya dari elemen sebelumnya. Urutan berakhir ketika 0tercapai. Sebagai contoh, jika $_ini 140, maka urutan ini adalah 140, 51, 17, 4, 1, 0.

Mengurangkan satu dari urutan ini memperlakukannya sebagai angka, panjangnya, dan perbedaannya adalah jumlah angka Fibonacci yang, ditambah bersama-sama, memberikan nomor input. Kemudian nomor ini diperiksa untuk keanggotaan dalam urutan Fibonacci pertama.

Perl 6 , 48 byte

{4>($_,{$_,{$_-(1,&[+]...*>$_)[*-2]}...^0}...1)}

Cobalah online!

Mengubah input menjadi daftar Representasi Zeckendorf berulang kali hingga mencapai satu nomor dan kemudian memeriksa apakah panjang urutannya kurang dari 4.

Fungsi Zenckendorf di tengah sebagian besar dari jawaban Sean dengan beberapa perbaikan.

Penjelasan:

{4>($_,{$_,{$_-(1,&[+]...*>$_)[*-2]}...^0}...1)}
{                                              } # Anonymous code block
                                          ...     # Define a sequence:
    $_  # That starts at the input
      ,{                                 }  # Each element is defined by:
                                   ... # Another sequence that:
        $_,   # Starts at the previous element
            $_-   # The previous element minus
                1,&[+]...*     # The Fibonacci sequence
                          >$_  # Ending when it is larger than the previous element
               (             )[*-2]  # The second from last element
          {                        }...^0  # Run until 0, discarding the last element
         # This returns the length of the Zeckendorf Representation
                                         ...1  # Run this until it is length 1
 4>(                                         )  # Return true if the length of the sequence is smaller than 4

Sebagai contoh, urutan untuk 2yaitu 2 1karena 2sudah merupakan angka Fibonacci. Urutan untuk 140adalah 140 5 1, dan karena 5 adalah angka Fibonacci, ini mengembalikan nilai true. Urutan untuk33 adalah 33 4 2 1, dan karena 4bukan angka Fibonacci, urutannya adalah panjang 4.

05AB1E , 14 byte

ΔDÅFθ-¼}¾ÅF¾<å

Cobalah online . Tidak ada paket tes untuk semua kasus uji, karena counter_variabletidak dapat diatur ulang ke 0 .. Namun saya memverifikasi semua dengan tangan, dan semuanya benar.

Penjelasan:

Δ      }          # Loop until the top of the stack no longer changes
 D                #  Duplicate the top of the stack
                  #  (implicitly the input in the first iteration)
  ÅF              #  Get a list of all Fibonacci numbers lower than this number
    θ             #  Get the last item (largest one)
     -            #  Subtract it from the number
      ¼           #  Increase the counter_variable by 1 every iteration
        ¾         # After the loop, push the counter_variable
         ÅF       # Get all Fibonacci numbers below this counter_variable
           ¾<     # Push the counter_variable again, and subtract 1
             å    # Check if this value is in the list of Fibonacci numbers
                  # (and output implicitly)

CATATAN: counter_variableAkan 5untuk input 139dan 6untuk input 140, karena agar Δ-loop untuk memeriksa stack tetap sama, tentu saja iterasi tambahan.

Haskell , 64 byte

s=(<2).r.r
f=1:scanl(+)1f
r 0=0
r z=1+r(z-last(takeWhile(<=z)f))

Cobalah online!

Retina 0.8.2 , 61 byte

.+
$*
M`((?>\2?)(\1|\G.))*..|.
.+
$*
^(((?>\3?)(\2|^.))*.)?.$

Cobalah online! Tautan termasuk kasus uji. Penjelasan:

.+
$*

Konversikan ke unary.

M`((?>\2?)(\1|\G.))*..|.

Hitung jumlah angka Fibonacci yang dibutuhkan.

Pergantian pertama berkaitan dengan angka Fibonacci yang setidaknya 2. Pada pass pertama, \2belum ada, tapi untungnya itu opsional, jadi kami tidak harus mencocokkannya. \1juga tidak ada, tapi untungnya kami memiliki alternatif \G.yang cocok dengan satu karakter di awal pertandingan. Keduanya \2dan \1karenanya mengambil nilai 1.

Pada operan berikutnya, \2ada, jadi kami mencoba mencocokkannya. Kali ini jika gagal maka \1juga gagal (karena lebih besar dari \2), tetapi jika berhasil, yang (?>)mencegah backtracking, jadi jika \2cocok tetapi \1tidak kita tidak coba saja \1. ( \G1selalu gagal karena kami telah maju melewati awal tambalan.) Akhirnya \2mengambil nilai sebelumnya \1sementara \1mengambil jumlah dari dua nilai.

Karena itu, kami mencocokkan angka Fibonacci sebanyak yang kami bisa, menambahkan seiring berjalannya waktu. Karena jumlah parsial urutannya 1, 2, 3, 5...adalah 0, 1, 3, 6, 11...2 lebih sedikit dari angka Fibonacci, kita selesaikan dengan mencocokkan 2 di akhir.

Ini jelas gagal untuk mencocokkan 1 sendiri sehingga pergantian menangani kasus itu.

.+
$*

Konversikan ke unary.

^(((?>\3?)(\2|^.))*.)?.$

Uji apakah ini adalah angka Fibonacci. Ini menggunakan ide yang sama dengan tes pertama tetapi menggunakan ^alih-alih\G dan kami juga harus mencocokkan dengan tepat, sehingga menggunakan tangkapan opsional sebagai pengganti pergantian sebagai pegolf (tetapi meningkatkan jumlah tangkapan 1).

Retina , 35 byte

.+
*
2}C`((?>\2?)(\1|\G.))*..|.
^1$

Cobalah online! Tautan termasuk kasus uji. Penjelasan:

.+
*

Konversikan ke unary.

C`((?>\2?)(\1|\G.))*..|.

Hitung jumlah angka Fibonacci yang dibutuhkan. (Looping konversi dan penghitungan menghemat satu byte lebih dari mendapatkan penghitungan di unary di tempat pertama.)

2}

Lakukan langkah-langkah sebelumnya dua kali total. Ini mengambil hitungan angka Fibonacci yang diperlukan untuk menjumlahkan ke jumlah angka Fibonacci.

^1$

Jika angka itu diam-diam Fibonacci maka hasilnya adalah 1.

Python 2 , 146 137 byte

lambda a:len(g(len(g(a))))<2
f=lambda n:n<3or f(n-2)+f(n-1)
def g(a,n=1):j=f(n-1);return[j]if a-j<1else[j]+g(a-j)if a-f(n)<0else g(a,n+1)

Cobalah online!

f () adalah fungsi rekursif yang mengembalikan nilai angka Fibonacci ke-n. Diambil dari jawaban ini .

g () adalah fungsi rekursif yang mengembalikan Representasi Zeckendorf dari angka yang diberikan sebagai daftar bilangan bulat.

Karena semua angka Fibonacci akan memiliki panjang pengembalian satu item dari g (), h () memeriksa apakah panjang g () dari g (n) == 1.

EDIT: Disimpan 9 byte berkat nedla2004 . Saya selalu lupa bahwa lambdas tidak selalu merupakan solusi terbaik ...