Um número inteiro positivo n pode ser representado como um retângulo com lados inteiros a , b , de modo que n = a * b . Ou seja, a área representa o número. Em geral, um e b não são únicos para um dado n .

Como é sabido, um retângulo é especialmente agradável aos olhos (ou é o cérebro?) Quando seus lados estão na proporção áurea , φ = (sqrt (5) +1) / 2 ≈ 1,6180339887 ...

Combinando esses dois fatos, o objetivo desse desafio é decompor um número inteiro n no produto de dois números inteiros a , b cuja razão seja o mais próximo possível de φ (com a métrica usual em ℝ). O fato de φ ser irracional implica que existe um par de soluções exclusivo ( a , b ).

O desafio

Dado um número inteiro positivo n , números inteiros positivos de saída a , b de tal forma que um * b = n e a diferença absoluta entre a / b e φ é minimizado.

Como exemplo, considere n = 12. Os pares ( a , b ) que satisfazem a * b = n são: (1, 12), (2,6), (3,4), (4,3), ( 6,2), (12,1). O par cuja razão está mais próxima de φ é (4,3), o que dá 4/3 = 1,333.

Regras

Funções ou programas são aceitáveis.

O numerador ( a ) deve aparecer primeiro na saída e o denominador ( b ) em segundo . Fora isso, os formatos de entrada e saída são flexíveis, como de costume. Por exemplo, os dois números podem ser impressos como cadeias de caracteres com qualquer separador razoável ou como uma matriz.

O código deve funcionar em teoria para números arbitrariamente grandes. Na prática, pode ser limitado por restrições de memória ou tipo de dados.

É suficiente considerar uma versão aproximada de φ , desde que seja precisa até a terceira casa decimal ou melhor. Ou seja, a diferença absoluta entre o valor verdadeiro φ e o valor aproximado não deve exceder 0,0005. Por exemplo, 1.618 é aceitável.

Ao usar uma versão aproximada e racional de φ, há uma pequena chance de que a solução não seja única. Nesse caso, você pode emitir qualquer par a , b que satisfaça o critério de minimização.

O menor código vence.

Casos de teste

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éia, 16 15 14 bytes

Guardou 1 byte graças a @miles.

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

Experimente online!

Explicação

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

Pitão - 24 23 bytes

Tem que haver uma maneira melhor de encontrar os divisores ...

ho.a-.n3cFNfsIeTm,dcQdS

Conjunto de Teste .

Matlab, 96 81 bytes

Golfe (-15bytes), adereços para 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)]

Essa não é de longe uma ótima solução, mas minha primeira tentativa no código-golfe. Que divertido!

05AB1E , 21 bytes

Código:

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

Usa a codificação CP-1252 . Experimente online!

Mathematica, 51 bytes

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

O operador postfix do Mathematica para transposição (exibido como sobrescrito Tno Mathematica).

O Mathematica possui um built-in GoldenRatio, mas o 1.618 é muito mais curto, especialmente porque o primeiro também exige N@.

Pitão, 21 20 18 bytes

hoacFN.n3C_Bf!%QTS

Experimente online. Suíte de teste.

Explicação

1. Obtenha o Sintervalo inclusivo de 1 a entrada.
2. ffiltro para números que dividem a entrada !%QT.
3. Get [that list, that list reversed] _B. Os divisores invertidos de um número são a mesma lista que o número dividido por cada um dos divisores.
4. Transponha a lista para obter pares de [numerator, denominator].
5. S ort os pares pela adiferença bsolute da relação do par cFNe da razão dourada .n3.
6. Obtenha o primeiro par (mais baixo) he imprima.

Javascript (ES6), 73 bytes

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

Nós procuramos por:

• a = divisor mais alto de n para o qual n / φ> a²
• b = divisor mais baixo de n para o qual n / φ <b²

Então, a solução é [a, n / a] ou [b, n / b] . Comparamos n / φ - a² com b² - n / φ para descobrir qual expressão está mais próxima de zero.

A fórmula real usado no código são baseados em φ / 2, que pode ser escrita de uma forma mais curta do que φ com a mesma precisão: .809vs 1.618.

Assim sendo:

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

e:

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

Complexidade

O número de iterações depende muito do número de fatores de n. O pior caso ocorre quando n é primo, porque precisamos executar todas as iterações de 1 a n para encontrar seus únicos 2 divisores. É o que acontece com 199999. Por outro lado, 9699690 é 19 suave e rapidamente encontramos dois divisores em ambos os lados do ponto de ruptura √ (n / φ) ≈ 2448.

Casos de teste

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 bytes

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>

Na verdade, retorna o par ( a , b ) que minimiza o valor absoluto de a / b - b / a -1, mas isso funciona para todos os casos de teste pelo menos, embora eu ache que eu poderia salvar 4 bytes usando o teste 1.618 .

Braquilog , 41 bytes

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

Experimente online!

Explicação

• Predicado 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
  

• Predicado 1: Saída é um par [A:B]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
  

• Predicado 2: Calcule a distância entre A/Be φ.

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

• Predicado 3: Converter um int em um flutuador, invertendo seu inverso

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

Produz um aviso (isso não interrompe a execução) sobre $ i não atribuído; portanto, ele deve ser executado em um ambiente que silencia avisos.

Python 3, 96 bytes

Solução bastante simples. Faz uso desta resposta 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]

Experimente online

A mesma solução no Python 2 é um byte a mais.

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]