Dodatnia liczba całkowita n może być reprezentowana przez prostokąt z bokami liczb całkowitych a , b takimi, że n = a * b . Oznacza to, że obszar reprezentuje liczbę. Na ogół, i b nie są unikatowe dla danego n .

Jak dobrze wiadomo, prostokąt jest szczególnie przyjemny dla oka (czy jest to mózg?), Gdy jego boki są w złotym stosunku , φ = (sqrt (5) +1) / 2 ≈ 1.6180339887 ...

Łącząc te dwa fakty, celem tego wyzwania jest rozkład liczby całkowitej n na iloczyn dwóch liczb całkowitych a , b, których stosunek jest jak najbardziej zbliżony do φ (przy zwykłej metodzie na ℝ). Fakt, że φ jest irracjonalny, oznacza, że ​​istnieje unikalna para rozwiązań ( a , b ).

Wyzwanie

Biorąc pod uwagę dodatnią liczbę całkowitą n , wyjściowe dodatnie liczby całkowite a , b są takie, że a * b = n i absolutna różnica między a / b i φ jest zminimalizowana.

Jako przykład rozważmy n = 12. Pary ( a , b ), które spełniają a * b = n, to: (1, 12), (2,6), (3,4), (4,3), ( 6,2), (12,1). Para, której stosunek jest najbliższy φ, wynosi (4,3), co daje 4/3 = 1,333.

Zasady

Funkcje lub programy są dopuszczalne.

Licznik ( ) powinien pojawić się pierwszy na wyjściu, a mianownik ( b ) drugi . Poza tym formaty wejściowe i wyjściowe są jak zwykle elastyczne. Na przykład dwie liczby mogą być wyprowadzane jako ciągi znaków z dowolnym rozsądnym separatorem lub jako tablica.

Kod powinien działać teoretycznie dla dowolnie dużych liczb. W praktyce może to być ograniczone pamięcią lub ograniczeniami typu danych.

To wystarczy, aby rozważyć przybliżoną wersję cp , tak długo, jak to jest dokładne aż do trzeciej po przecinku lub lepszej. Oznacza to, że bezwzględna różnica między prawdziwą φ a przybliżoną wartością nie powinna przekraczać 0,0005. Na przykład 1.618 jest akceptowalny.

Podczas korzystania z przybliżonej, racjonalnej wersji φ istnieje niewielkie prawdopodobieństwo, że rozwiązanie nie jest unikalne. W takim przypadku możesz wygenerować dowolną parę a , b, która spełnia kryterium minimalizacji.

Najkrótszy kod wygrywa.

Przypadki testowe

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

Galaretka, 16 15 14 bajtów

Zapisano 1 bajt dzięki @miles.

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

Wypróbuj online!

Wyjaśnienie

÷/ạØ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 bajty

Musi być lepszy sposób na znalezienie dzielników ...

ho.a-.n3cFNfsIeTm,dcQdS

Pakiet testowy .

Matlab, 96 81 bajtów

Gra w golfa (-15 bajtów), rekwizyty dla Luisa Mendo

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

Oryginalny:

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)]

To zdecydowanie nie jest świetne rozwiązanie, ale moja pierwsza próba gry w golfa. Co za zabawa!

05AB1E , 21 bajtów

Kod:

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

Wykorzystuje kodowanie CP-1252 . Wypróbuj online!

Mathematica, 51 bajtów

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

Jest to operator postfiksu Mathematica do transpozycji (wyświetlany jako indeks górny Tw Mathematica).

Mathematica ma wbudowane GoldenRatio, ale 1.618 jest znacznie krótszy, zwłaszcza, że ​​ten pierwszy również wymaga N@.

Pyth, 21 20 18 bajtów

hoacFN.n3C_Bf!%QTS

Wypróbuj online. Zestaw testowy.

Wyjaśnienie

1. Uzyskaj Szakres włączenia od 1 do wejścia.
2. filter dla liczb dzielących dane wejściowe !%QT.
3. Dostać [that list, that list reversed] _B. Odwrócone dzielniki liczby są tą samą listą, co liczba podzielona przez każdy z dzielników.
4. Transponuj listę, aby uzyskać pary [numerator, denominator].
5. S ort pary przez absolute różnicę stosunku pary cFNi złotego podziału .n3.
6. Zdobądź pierwszą (najniższą) parę hi wydrukuj.

JavaScript (ES6), 73 bajty

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]}

Szukamy:

• a = najwyższy dzielnik n, dla którego n / φ> a²
• b = najniższy dzielnik n, dla którego n / φ <b²

Następnie rozwiązaniem jest [a, n / a] lub [b, n / b] . Porównujemy n / φ - a² z b² - n / φ aby dowiedzieć się, które wyrażenie jest najbliższe zeru.

Rzeczywista formuła zastosowana w kodzie oparta jest na φ / 2, które można zapisać w krótszy sposób niż φ z tą samą precyzją: .809vs1.618 .

W związku z tym:

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

i:

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

Złożoność

Liczba iteracji silnie zależy od liczby czynników n. Najgorszy przypadek występuje, gdy n jest liczbą pierwszą, ponieważ musimy wykonać wszystkie iteracje od 1 do n, aby znaleźć tylko 2 dzielniki. Tak dzieje się w przypadku 199999. Z drugiej strony 9699690 ma 19-gładkie i szybko znajdujemy dwa dzielniki po obu stronach punktu przerwania √ (n / φ) ≈ 2448.

Przypadki testowe

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 bajty

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>

Właściwie zwraca parę ( a , b ), która minimalizuje wartość bezwzględną a / b - b / a -1, ale działa to przynajmniej dla wszystkich przypadków testowych, chociaż myślę, że mógłbym zaoszczędzić 4 bajty za pomocą testu 1.618 zamiast tego .

Brachylog , 41 bajtów

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

Wypróbuj online!

Wyjaśnienie

• Główny predykat:

  :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
  

• Predykat 1: Dane wyjściowe to kilka [A:B]takich, żeA*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
  

• Predykat 2: Oblicz odległość między A/Bi φ.

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

• Predykat 3: Konwertuj liczbę całkowitą na liczbę zmiennoprzecinkową, odwracając jej odwrotność

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

Haskell (Lambdabot), 86 bajtów

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 bajty

<?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;

Powoduje powiadomienie (nie przerywa wykonywania) o nieprzypisanym $ i, dlatego powinno być uruchamiane w środowisku, które wycisza powiadomienia.

Python 3, 96 bajtów

Całkiem proste rozwiązanie. Wykorzystuje tę SO odpowiedź .

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]

Wypróbuj online

To samo rozwiązanie w Pythonie 2 jest dłuższe o jeden bajt.

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]