Eine positive ganze Zahl n kann als Rechteck mit ganzzahligen Seiten a , b dargestellt werden, so dass n = a * b ist . Das heißt, der Bereich repräsentiert die Nummer. Im Allgemeinen sind a und b für ein gegebenes n nicht eindeutig .

Bekanntlich gefällt ein Rechteck dem Auge (oder dem Gehirn?) Besonders gut, wenn sich seine Seiten im goldenen Schnitt befinden : φ = (sqrt (5) +1) / 2 ≈ 1.6180339887 ...

Kombiniert man diese beiden Tatsachen, besteht der Zweck dieser Aufgabe darin, eine ganze Zahl n in das Produkt zweier ganzer Zahlen a , b zu zerlegen , deren Verhältnis so nahe wie möglich an φ liegt (mit der üblichen Metrik für ℝ). Die Tatsache, dass φ irrational ist, impliziert, dass es ein eindeutiges Lösungspaar ( a , b ) gibt.

Die Herausforderung

Bei einer positiven ganzen Zahl n werden positive ganze Zahlen a , b ausgegeben , so dass a * b = n und die absolute Differenz zwischen a / b und φ minimiert wird.

Als Beispiel n = 12 betrachten. Die Paare ( a , b ), die a * b = n erfüllen, sind: (1, 12), (2,6), (3,4), (4,3), ( 6,2), (12,1). Das Paar, dessen Verhältnis φ am nächsten kommt, ist (4,3), was 4/3 = 1,333 ergibt.

Regeln

Funktionen oder Programme sind akzeptabel.

Der Zähler ( a ) sollte zuerst in der Ausgabe erscheinen und der Nenner ( b ) an zweiter Stelle . Ansonsten sind Ein- und Ausgabeformate wie gewohnt flexibel. Beispielsweise können die beiden Zahlen als Zeichenfolgen mit einem geeigneten Trennzeichen oder als Array ausgegeben werden.

Der Code sollte theoretisch für beliebig große Zahlen funktionieren. In der Praxis kann dies durch Speicher- oder Datentypbeschränkungen begrenzt sein.

Es ist ausreichend, eine ungefähre Version von φ zu berücksichtigen , sofern diese bis zur dritten Dezimalstelle oder besser genau ist . Das heißt, die absolute Differenz zwischen dem wahren φ und dem ungefähren Wert sollte 0,0005 nicht überschreiten. Zum Beispiel ist 1,618 akzeptabel.

Bei Verwendung einer ungefähren, rationalen Version von φ ist die Wahrscheinlichkeit gering, dass die Lösung nicht eindeutig ist. In diesem Fall können Sie jedes Paar a , b ausgeben , das das Minimierungskriterium erfüllt.

Kürzester Code gewinnt.

Testfälle

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 Bytes

1 Byte dank @miles gespeichert.

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

Probieren Sie es online!

Erläuterung

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

Es muss einen besseren Weg geben, die Teiler zu finden ...

ho.a-.n3cFNfsIeTm,dcQdS

Test Suite .

Matlab, 96 81 Bytes

Golf (-15 Bytes), Requisiten für Luis Mendo

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

Original:

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

Dies ist bei weitem keine großartige Lösung, aber mein erster Versuch, Code-Golf zu spielen. Was für ein Spaß!

05AB1E , 21 Bytes

Code:

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

Verwendet die CP-1252- Codierung. Probieren Sie es online!

Mathematica, 51 Bytes

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

Das ist Mathematicas Postfix - Operator für die Umsetzung (als Exponent angezeigt Tin Mathematica).

Mathematica hat eine eingebaute GoldenRatio, aber 1.618 ist viel kürzer, vor allem, weil der erstere auch erfordert N@.

Pyth, 21 20 18 Bytes

hoacFN.n3C_Bf!%QTS

Probieren Sie es online aus. Testsuite.

Erläuterung

1. Ermitteln Sie den Einschlussbereich Svon 1 bis Eingang.
2. fZahlen teilen die Eingabe !%QT.
3. Bekommen [that list, that list reversed] _B. Die umgekehrten Teiler einer Zahl sind dieselbe Liste wie die Zahl, die durch jeden der Teiler geteilt wird.
4. Transponiere die Liste, um Paare zu erhalten [numerator, denominator].
5. S ort die Paare durch die aabsolute Differenz des Verhältnisses des Paares cFNund des goldenen Verhältnisses .n3.
6. Holen Sie sich das erste (niedrigste) Paar hund drucken Sie.

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

Wir suchen nach:

• a = höchster Teiler von n, für den n / φ> a² ist
• b = niedrigster Teiler von n, für den n / φ <b² ist

Dann lautet die Lösung entweder [a, n / a] oder [b, n / b] . Wir vergleichen n / φ - a² mit b² - n / φ , um herauszufinden, welcher Ausdruck am nächsten an Null liegt.

Die tatsächliche Formel im Code verwendet wird , basiert auf φ / 2 , die in einem kürzeren Weg als φ mit der gleichen Präzision geschrieben werden können: .809vs 1.618.

Deshalb:

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

und:

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

Komplexität

Die Anzahl der Iterationen hängt stark von der Anzahl der Faktoren von n ab. Der schlimmste Fall tritt auf, wenn n eine Primzahl ist, weil wir alle Iterationen von 1 bis n ausführen müssen, um die einzigen 2 Teiler zu finden. Dies ist, was mit 199999 passiert. Andererseits ist 9699690 19-glatt und wir finden schnell zwei Teiler auf beiden Seiten der Bruchstelle √ (n / φ) ≈ 2448.

Testfälle

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>

Gibt tatsächlich das ( a , b ) -Paar zurück, das den absoluten Wert von a / b - b / a -1 minimiert , aber dies funktioniert zumindest für alle Testfälle, obwohl ich 4 Bytes sparen könnte, indem ich stattdessen den 1.618-Test verwende .

Brachylog , 41 Bytes

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

Probieren Sie es online!

Erläuterung

• Hauptprädikat:

  :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
  

• Prädikat 1: Output ist ein [A:B]solches PaarA*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
  

• Prädikat 2: Berechnen Sie den Abstand zwischen A/Bund φ.

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

• Prädikat 3: Konvertieren Sie ein int in ein float, indem Sie das inverse invertieren

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

Haskell (Lambdabot), 86 Bytes

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 Bytes

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

Erzeugt einen Hinweis (dies unterbricht die Ausführung nicht) zu nicht zugewiesenem $ i und sollte daher in einer Umgebung ausgeführt werden, in der Benachrichtigungen stummgeschaltet werden.

Python 3, 96 Bytes

Ziemlich einfache Lösung. Nutzt diese SO-Antwort .

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]

Probieren Sie es online aus

Dieselbe Lösung in Python 2 ist ein Byte länger.

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]