Bilangan bulat positif n dapat direpresentasikan sebagai persegi panjang dengan sisi bilangan bulat a , b sedemikian rupa sehingga n = a * b . Artinya, area mewakili angka. Secara umum, a dan b tidak unik untuk yang diberikan n .

Seperti diketahui, persegi panjang secara khusus menyenangkan mata (atau apakah itu otak?) Ketika sisinya berada dalam rasio emas , φ = (sqrt (5) +1) / 2 ≈ 1.6180339887 ...

Menggabungkan dua fakta ini, tujuan dari tantangan ini adalah untuk menguraikan bilangan bulat n menjadi produk dari dua bilangan bulat a , b yang rasionya sedekat mungkin dengan φ (dengan metrik biasa pada ℝ). Fakta bahwa φ tidak rasional menyiratkan bahwa ada pasangan solusi yang unik ( a , b ).

Tantangan

Dengan bilangan bulat positif n , bilangan bulat keluaran positif a , b sehingga a * b = n dan perbedaan absolut antara a / b dan φ diminimalkan.

Sebagai contoh, perhatikan n = 12. Pasangan ( a , b ) yang memenuhi a * b = n adalah: (1, 12), (2,6), (3,4), (4,3), ( 6,2), (12,1). Pasangan yang rasionya paling dekat dengan φ adalah (4,3), yang memberikan 4/3 = 1,333.

Aturan

Fungsi atau program dapat diterima.

The pembilang ( a ) harus muncul pertama pada output, dan penyebut ( b ) kedua . Selain itu, format input dan output fleksibel seperti biasa. Sebagai contoh, dua angka bisa berupa string dengan pemisah yang masuk akal, atau sebagai array.

Kode harus bekerja secara teori untuk jumlah besar yang sewenang-wenang. Dalam praktiknya, ini mungkin dibatasi oleh memori atau batasan tipe data.

Cukup untuk mempertimbangkan versi perkiraan φ , asalkan akurat hingga desimal ketiga atau lebih baik. Artinya, perbedaan absolut antara φ benar dan nilai perkiraan tidak boleh melebihi 0,0005. Misalnya, 1.618 dapat diterima.

Saat menggunakan perkiraan, versi rasional φ ada kemungkinan kecil bahwa solusinya tidak unik. Dalam hal ini Anda dapat menampilkan pasangan apa pun a , b yang memenuhi kriteria minimalisasi.

Kode terpendek menang.

Uji kasus

1        ->  1    1
2        ->  2    1 
4        ->  2    2
12       ->  4    3
42       ->  7    6
576      ->  32   18
1234     ->  2    617
10000    ->  125  80
199999   ->  1    199999
9699690  ->  3990 2431

Jelly, 16 15 14 byte

Disimpan 1 byte berkat @miles.

÷/ạØp
ÆDżṚ$ÇÞḢ

Cobalah online!

Penjelasan

÷/ạØp         Helper link, calculates abs(a/b - phi). Argument: [a, b]
÷/            Reduce by division to calculate a/b.
  ạØp         Calculate abs(a/b - phi).

ÆDżṚ$ÇÞḢ      Main link. Argument: n
ÆD            Get divisors of n.
  żṚ$         Pair the items of the list with those of its reverse. The reversed
              divisors of a number is the same list as the number divided by each
              of the divisors.
     ÇÞ       Sort by the output of the helper link of each pair.
       Ḣ      Get the first element [a, b] and implicitly print.

Pyth - 24 23 byte

Harus ada cara yang lebih baik untuk menemukan pembagi ...

ho.a-.n3cFNfsIeTm,dcQdS

Test Suite .

Matlab, 96 81 byte

Golf (-15bytes), alat peraga untuk Luis Mendo

function w(n);a=find(~(mod(n,1:n)));[~,c]=min(abs(a./(n./a)-1.618));[a(c) n/a(c)]

Asli:

function w(n)
a=find(not(mod(n,1:n)));b=abs(a./(n./a)-1.618);c=find(not(b-min(b)));[a(c) n/a(c)]

Sejauh ini ini bukan solusi yang bagus, tetapi upaya pertama saya di kode-golf. Apanya yang seru!

05AB1E , 21 byte

Kode:

ÑÂø©vy`/})5t>;-ÄWQ®sÏ

Menggunakan pengkodean CP-1252 . Cobalah online!

Mathematica, 51 byte

#&@@SortBy[{x=Divisors@#,#/x},Abs[#/#2-1.618]&]&

Ini adalah operator postfix Mathematica untuk transposisi (ditampilkan sebagai superscript Tdalam Mathematica).

Mathematica memiliki built-in GoldenRatio, tetapi 1.618 jauh lebih pendek, terutama karena yang pertama juga membutuhkan N@.

Pyth, 21 20 18 byte

hoacFN.n3C_Bf!%QTS

Cobalah online. Suite uji.

Penjelasan

1. Dapatkan Srentang inklusif dari 1 hingga input.
2. filter untuk angka untuk membagi input !%QT.
3. Dapatkan [that list, that list reversed] _B. Pembagi nomor yang dibalik adalah daftar yang sama dengan nomor yang dibagi oleh masing-masing pembagi.
4. Ubah urutan daftar untuk mendapatkan pasangan [numerator, denominator].
5. S ort pasangan dengan aperbedaan bsolute dari rasio dari pasangan cFNdan rasio emas .n3.
6. Dapatkan pasangan ( hcetak ) pertama dan cetak.

Javascript (ES6), 73 byte

n=>{for(b=0,k=n/.809;n%++b||k>b*b*2&&(a=b););return[b=k-a*a>b*b?b:a,n/b]}

Kami mencari:

• a = pembagi tertinggi n yang n / φ> a²
• b = pembagi terendah n yang n / φ <b²

Kemudian, solusinya adalah [a, n / a] atau [b, n / b] . Kami membandingkan n / φ - a² dengan b² - n / φ untuk mengetahui ekspresi mana yang paling dekat dengan nol.

Rumus yang sebenarnya digunakan dalam kode didasarkan pada φ / 2 yang dapat ditulis dengan cara lebih pendek dari φ dengan presisi yang sama: .809vs 1.618.

Karena itu:

n / φ> a² ⇔ n / (φ / 2)> 2a²

dan:

n / φ - a²> b² - n / φ ⇔ 2n / φ - a²> b² ⇔ n / (φ / 2) - a²> b²

Kompleksitas

Jumlah iterasi sangat tergantung pada jumlah faktor n. Kasus terburuk terjadi ketika n adalah prima, karena kita harus melakukan semua iterasi dari 1 ke n untuk menemukan hanya 2 pembagi. Inilah yang terjadi dengan 199999. Di sisi lain, 9699690 adalah 19-halus dan kami dengan cepat menemukan dua pembagi di kedua sisi titik pemecah √ (n / φ) ≈ 2448.

Uji kasus

let f =
n=>{for(b=0,k=n/.809;n%++b||k>b*b*2&&(a=b););return[b=k-a*a>b*b?b:a,n/b]}

console.log(JSON.stringify(f(12)));       // [ 3, 4 ]
console.log(JSON.stringify(f(42)));       // [ 6, 7 ]
console.log(JSON.stringify(f(576)));      // [ 18, 32 ]
console.log(JSON.stringify(f(1234)));     // [ 2, 617 ]
console.log(JSON.stringify(f(10000)));    // [ 80, 125 ]
console.log(JSON.stringify(f(199999)));   // [ 1, 199999 ]
console.log(JSON.stringify(f(9699690)));  // [ 2431, 3990 ]

JavaScript (ES6), 83 byte

f=
n=>{p=r=>Math.abs(r/n-n/r-1);for(r=i=n;--i;)r=n%i||p(i*i)>p(r*r)?r:i;return[r,n/r]}
;

<input type=number min=1 oninput=[a.value,b.value]=f(+this.value)><input readonly id=a><input readonly id=b>

Sebenarnya mengembalikan pasangan ( a , b ) yang meminimalkan nilai absolut dari a / b - b / a -1, tetapi ini bekerja untuk semua kasus uji setidaknya, meskipun saya kira saya bisa menghemat 4 byte dengan menggunakan tes 1,618 sebagai gantinya .

Brachylog , 41 byte

:1fL:2a:Lzoht
,A:B#>.*?!,.=
:3a/:$A-$|
//

Cobalah online!

Penjelasan

• Predikat utama:

  :1fL           L is the list of all couples [A:B] such that A*B = Input (see Pred. 1)
      :2a        Compute the distance between all As/Bs and φ (see Pred. 2)
         :Lz     Zip those distances to L
            o    Sort the zip on the distances
             ht  Take the couple [A:B] of the first element of the sorted list
  

• Predikat 1: Output adalah pasangan [A:B]sedemikian rupaA*B = Input

  ,A:B           The list [A:B]
      #>         Both A and B are strictly positive
        .        Output = [A:B]
         *?      A*B = Input
           !,    Discard other choice points
             .=  Assign a value to A and B that satisfy the constraints
  

• Predikat 2: Hitung jarak antara A/Bdan φ.

  :3a            Convert A and B to floats
     /           Divide A by B
      :$A-       Subtract φ
          $|     Absolute value
  

• Predikat 3: Konversi int menjadi float dengan membalikkan kebalikannya

  /              1/Input
   /             Output = 1/(1/Input)
  

Haskell (Lambdabot), 86 byte

f(x,y)=abs$(x/y)-1.618
q n=minimumBy((.f).compare.f)[(x,y)|x<-[1..n],y<-[1..n],x*y==n]

php, 103 byte

<?php for($s=$a=$argv[1];++$i<$a;)if($a%$i==0&&$s>$t=abs($i*$i/$a-1.618)){$n=$i;$s=$t;}echo"$n ".$a/$n;

Menghasilkan pemberitahuan (ini tidak mengganggu eksekusi) tentang $ i yang belum ditetapkan sehingga harus dijalankan di lingkungan yang membungkam pemberitahuan.

Python 3, 96 byte

Solusi yang cukup sederhana. Manfaatkan jawaban SO ini .

lambda n:min([((i,n//i),abs(1.618-i/(n//i)))for i in range(1,n+1)if n%i<1],key=lambda x:x[1])[0]

Cobalah online

Solusi yang sama di Python 2 adalah satu byte lebih lama.

lambda n:min([((i,n/i),abs(1.618-1.*i/(n/i)))for i in range(1,n+1)if n%i<1],key=lambda x:x[1])[0]