Un entier positif n peut être représenté comme un rectangle avec des côtés entiers a , b tels que n = a * b . Autrement dit, la zone représente le nombre. En général, a et b ne sont pas uniques pour un n donné .

Comme on le sait, un rectangle est particulièrement agréable à l'œil (ou est-ce le cerveau?) Lorsque ses côtés sont dans le nombre d' or , φ = (sqrt (5) +1) / 2 ≈ 1.6180339887 ...

En combinant ces deux faits, le but de ce défi est de décomposer un entier n en produit de deux entiers a , b dont le rapport est aussi proche que possible de φ (avec la métrique habituelle sur ℝ). Le fait que φ soit irrationnel implique qu'il existe une paire de solutions unique ( a , b ).

Le défi

Étant donné un entier positif n , les entiers positifs de sortie a , b tels que a * b = n et la différence absolue entre a / b et φ sont minimisés.

À titre d'exemple, considérons n = 12. Les paires ( a , b ) qui satisfont a * b = n sont: (1, 12), (2,6), (3,4), (4,3), ( 6,2), (12,1). La paire dont le rapport est le plus proche de φ est (4,3), ce qui donne 4/3 = 1,333.

Règles

Les fonctions ou programmes sont acceptables.

Le numérateur ( a ) doit apparaître en premier dans la sortie, et le dénominateur ( b ) en second . En dehors de cela, les formats d'entrée et de sortie sont flexibles comme d'habitude. Par exemple, les deux nombres peuvent être sortis sous forme de chaînes avec tout séparateur raisonnable ou sous forme de tableau.

Le code devrait fonctionner en théorie pour des nombres arbitrairement grands. En pratique, il peut être limité par des restrictions de mémoire ou de type de données.

Il suffit de considérer une version approximative de φ , tant qu'elle est précise jusqu'à la troisième décimale ou mieux. C'est, la différence absolue entre le vrai φ et la valeur approximative ne doit pas dépasser 0,0005. Par exemple, 1,618 est acceptable.

Lorsque vous utilisez une version approximative et rationnelle de φ, il est peu probable que la solution ne soit pas unique. Dans ce cas, vous pouvez sortir n'importe quelle paire a , b qui satisfait au critère de minimisation.

Le code le plus court gagne.

Cas de test

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

Gelée, 16 15 14 octets

1 octet enregistré grâce à @miles.

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

Essayez-le en ligne!

Explication

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

Il doit y avoir un meilleur moyen de trouver les diviseurs ...

ho.a-.n3cFNfsIeTm,dcQdS

Suite de tests .

Matlab, 96 81 octets

Golfé (-15 octets), accessoires à 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)]

Ce n'est de loin pas une excellente solution, mais ma première tentative de code-golf. Ce que c'est drôle!

05AB1E , 21 octets

Code:

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

Utilise l' encodage CP-1252 . Essayez-le en ligne!

Mathematica, 51 octets

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

L' opérateur de suffixe de Mathematica pour la transposition (affiché en exposant Tdans Mathematica).

Mathematica a un intégré GoldenRatio, mais 1.618 est beaucoup plus court, surtout parce que le premier nécessite également N@.

Pyth, 21 20 18 octets

hoacFN.n3C_Bf!%QTS

Essayez-le en ligne. Suite de tests.

Explication

1. Obtenez la Splage inclu ive de 1 à l'entrée.
2. filter pour les nombres qui divisent l'entrée !%QT.
3. Obtenez [that list, that list reversed] _B. Les diviseurs inversés d'un nombre sont la même liste que le nombre divisé par chacun des diviseurs.
4. Transposer la liste pour obtenir des paires de [numerator, denominator].
5. S ort les paires par la adifférence absolue du rapport de la paire cFNet du nombre d'or .n3.
6. Obtenez la première paire (la plus basse) het imprimez.

Javascript (ES6), 73 octets

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

Nous recherchons des:

• a = le plus grand diviseur de n pour lequel n / φ> a²
• b = le plus petit diviseur de n pour lequel n / φ <b²

Ensuite, la solution est soit [a, n / a] ou [b, n / b] . Nous comparons n / φ - a² avec b² - n / φ pour trouver quelle expression est la plus proche de zéro.

La formule utilisée dans le code sont basées sur φ / 2 qui peut être écrit de manière plus courte que φ avec la même précision: .809vs 1.618.

Donc:

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

et:

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

Complexité

Le nombre d'itérations dépend fortement du nombre de facteurs de n. Le pire des cas se produit lorsque n est premier, car nous devons effectuer toutes les itérations de 1 à n pour trouver ses 2 seuls diviseurs. C'est ce qui se passe avec 199999. Par contre, 9699690 est à 19 lisses et on retrouve rapidement deux diviseurs de part et d'autre du point de rupture √ (n / φ) ≈ 2448.

Cas de test

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 octets

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>

Retourne en fait la paire ( a , b ) qui minimise la valeur absolue de a / b - b / a -1, mais cela fonctionne pour tous les cas de test au moins, bien que je suppose que je pourrais économiser 4 octets en utilisant le test 1.618 à la place .

Brachylog , 41 octets

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

Essayez-le en ligne!

Explication

• Prédicat principal:

  :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édicat 1: la sortie est un couple [A:B]tel queA*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édicat 2: Calculez la distance entre A/Bet φ.

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

• Prédicat 3: convertir un int en un flottant en inversant son inverse

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

Haskell (Lambdabot), 86 octets

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 octets

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

Produit un avis (cela n'interrompt pas l'exécution) sur $ i non affecté. Il doit donc être exécuté dans un environnement qui coupe les avis.

Python 3, 96 octets

Solution assez simple. Utilise cette réponse SO .

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]

Essayez-le en ligne

La même solution en Python 2 est d'un octet de plus.

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]