Положительное целое число n можно представить в виде прямоугольника с целочисленными сторонами a , b, такого что n = a * b . То есть область представляет число. В общем, a и b не являются уникальными для данного n .

Как известно, прямоугольник особенно приятен глазу (или это мозг?), Когда его стороны находятся в золотом сечении , φ = (sqrt (5) +1) / 2 ≈ 1.6180339887 ...

Объединяя эти два факта, цель этой задачи состоит в том, чтобы разложить целое число n в произведение двух целых чисел a , b , отношение которых максимально приближено к φ (с обычной метрикой на ℝ). Тот факт, что φ иррационально, означает, что существует единственная пара решений ( a , b ).

Соревнование

Для заданного натурального числа n выведите натуральные числа a , b, такие что a * b = n, а абсолютная разница между a / b и φ сведена к минимуму.

В качестве примера рассмотрим n = 12. Пары ( a , b ), которые удовлетворяют a * b = n : (1, 12), (2,6), (3,4), (4,3), ( 6,2), (12,1). Пара, отношение которой ближе всего к φ, равно (4,3), что дает 4/3 = 1,333.

правила

Функции или программы приемлемы.

Числитель ( ) должен появиться первым на выходе, а знаменатель ( б ) второй . Кроме этого, форматы ввода и вывода, как обычно, гибкие. Например, два числа могут быть выведены в виде строк с любым разумным разделителем или в виде массива.

Код должен работать теоретически для сколь угодно больших чисел. На практике это может быть ограничено памятью или типом данных.

Достаточно рассмотреть приблизительную версию φ , если она точна с точностью до третьего знака после запятой или лучше. То есть абсолютная разница между истинным φ и приблизительным значением не должна превышать 0,0005. Например, 1.618 является приемлемым.

При использовании приблизительной, рациональной версии φ существует небольшая вероятность того, что решение не является уникальным. В этом случае вы можете вывести любую пару a , b, которая удовлетворяет критерию минимизации.

Самый короткий код выигрывает.

Контрольные примеры

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

Желе, 16 15 14 байт

Сохранено 1 байт благодаря @miles.

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

Попробуйте онлайн!

объяснение

÷/ạØ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 байта

Должен быть лучший способ найти делители ...

ho.a-.n3cFNfsIeTm,dcQdS

Тестовый пакет .

Matlab, 96 81 байт

Гольф (-15 байт), реквизит Луис Мендо

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

Оригинал:

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

Это далеко не отличное решение, но моя первая попытка использовать код-гольф. Как весело!

05AB1E , 21 байт

Код:

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

Использует кодировку CP-1252 . Попробуйте онлайн!

Mathematica, 51 байт

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

Является постфиксного Mathematica в транспозиции (отображается в виде верхнего индекса Tв Mathematica).

Mathematica имеет встроенный GoldenRatio, но 1.618 намного короче, особенно потому, что первый также требует N@.

Pyth, 21 20 18 байт

hoacFN.n3C_Bf!%QTS

Попробуйте онлайн. Тестирование.

объяснение

1. Получить включаемый Sдиапазон от 1 до ввода.
2. filter для чисел для этого делят ввод !%QT.
3. Получить [that list, that list reversed] _B . Обратные делители числа - это тот же список, что и число, деленное на каждый из делителей.
4. Транспонировать список, чтобы получить пары [numerator, denominator] .
5. S ort пары по aабсолютной разности отношения пары cFNи золотого сечения.n3 .
6. Получить первую (низшую) пару hи распечатать.

Javascript (ES6), 73 байта

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

Мы ищем:

• a = старший делитель n, для которого n / φ> a²
• b = самый низкий делитель n, для которого n / φ <b²

Тогда решение будет либо [a, n / a], либо [b, n / b] . Мы сравниваем n / φ - a² с b² - n / φ чтобы выяснить, какое выражение ближе всего к нулю.

Текущая формула , используемая в коде основана на ф / 2 , который может быть записан в более коротком пути , чем ф с той же точностью: .809против 1.618.

Следовательно:

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

и:

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

сложность

Количество итераций сильно зависит от количества факторов n. Наихудший случай возникает, когда n простое, потому что мы должны выполнить все итерации от 1 до n, чтобы найти только 2 его делителя. Это то, что происходит с 199999. С другой стороны, 9699690 является 19-гладким, и мы быстро находим два делителя по обе стороны от точки разрыва √ (n / φ) ≈ 2448.

Контрольные примеры

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 байта

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>

На самом деле возвращает пару ( a , b ), которая минимизирует абсолютное значение a / b - b / a -1, но это работает как минимум для всех тестовых случаев, хотя я думаю, что я мог бы сэкономить 4 байта, используя вместо этого тест 1.618 ,

Брахилог , 41 байт

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

Попробуйте онлайн!

объяснение

• Основной предикат:

  :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
  

• Предикат 1: Выходная пара [A:B]такая, чтоA*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
  

• Предикат 2: Вычислить расстояние между A/B и φ.

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

• Предикат 3: преобразовать int в число с плавающей точкой, инвертировав его обратное

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

Haskell (Lambdabot), 86 байт

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 байта

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

Создает уведомление (это не прерывает выполнение) о неназначенном $ i, поэтому его следует запускать в среде, в которой уведомления отключены.

Python 3, 96 байт

Довольно простое решение. Использует этот так ответ .

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]

Попробуйте онлайн

То же решение в Python 2 на один байт длиннее.

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]