21
1
A positive integer n can be represented as a rectangle with integer sides a, b such that n = a * b. That is, the area represents the number. In general, a and b are not unique for a given n.
As is well known, a rectangle is specially pleasing to the eye (or is it the brain?) when its sides are in the golden ratio, φ = (sqrt(5)+1)/2 ≈ 1.6180339887...
Combining these two facts, the purpose of this challenge is to decompose an integer n into the product of two integers a, b whose ratio is as close as possible to φ (with the usual metric on ℝ). The fact that φ is irrational implies that there is a unique solution pair (a, b).
The challenge
Given a positive integer n, output positive integers a, b such that a * b = n and the absolute difference between a/b and φ is minimized.
As an example, consider n = 12. The pairs (a, b) that satisfy a * b = n are: (1, 12), (2,6), (3,4), (4,3), (6,2), (12,1). The pair whose ratio is closest to φ is (4,3), which gives 4/3 = 1.333.
Rules
Functions or programs are acceptable.
The numerator (a) should appear first in the output, and the denominator (b) second. Other than that, input and output formats are flexible as usual. For example, the two numbers can be output as strings with any reasonable separator, or as an array.
The code should work in theory for arbitrarily large numbers. In practice, it may be limited by memory or data-type restrictions.
It's sufficient to consider an approximate version of φ, as long as it is accurate up to the third decimal or better. That is, the absolute difference between the true φ and the approximate value should not exceed 0.0005. For example, 1.618 is acceptable.
When using an approximate, rational version of φ there's a small chance that the solution is not unique. In that case you can output any pair a, b that satisfies the minimization criterion.
Shortest code wins.
Test cases
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
Surely most answers will be using some sort of rational approximation to φ, unless you accept e.g. the answer with the result of a/b-b/a is as close to 1 as possible. – Neil – 2016-09-11T13:02:41.600
@Neil I'm not sure I understand your comment. Your idea of minimizing
|a/b-b/a-1|
is promising, although a proof would be in order – Luis Mendo – 2016-09-11T14:34:55.223Not sure that I can cram a whole proof into a comment, but the outline is as follows: the whole rectangle represents
– Neil – 2016-09-11T15:11:00.490a/b
. Removing the unit square leaves the small rectangle on the right which representsb/a
. A golden rectangle therefore achieves a difference of 1.If a and b aren't adjacent numbers in the Fibbonacci sequence, is there any point including them in the test? – Strawberry – 2016-09-12T15:24:08.977
That said, 1618 x 1000 seems like a good candidate (or, by reference, 809 x 500) – Strawberry – 2016-09-12T15:27:53.337
@Strawberry I don't follow. Why would it only make sense to include Fibonacci numbers? – Luis Mendo – 2016-09-12T15:33:31.063
Thinking about it, it doesn't. The fibonnaci sequence is a subset of the group of 'quite golden' numbers. – Strawberry – 2016-09-12T15:34:34.853