21
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Neil Sep 11 '16 at 13:02
  • \$\begingroup\$ @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 \$\endgroup\$ – Luis Mendo Sep 11 '16 at 14:34
  • \$\begingroup\$ Not sure that I can cram a whole proof into a comment, but the outline is as follows: the whole rectangle represents a/b. Removing the unit square leaves the small rectangle on the right which represents b/a. A golden rectangle therefore achieves a difference of 1. \$\endgroup\$ – Neil Sep 11 '16 at 15:11
  • \$\begingroup\$ If a and b aren't adjacent numbers in the Fibbonacci sequence, is there any point including them in the test? \$\endgroup\$ – Strawberry Sep 12 '16 at 15:24
  • \$\begingroup\$ That said, 1618 x 1000 seems like a good candidate (or, by reference, 809 x 500) \$\endgroup\$ – Strawberry Sep 12 '16 at 15:27

12 Answers 12

6
\$\begingroup\$

Jelly, 16 15 14 bytes

Saved 1 byte thanks to @miles.

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

Try it online!

Explanation

÷/ạØ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.
\$\endgroup\$
  • \$\begingroup\$ You can save a byte by interleaving the reverse of the divisor list with itself. Using ÷/ạØp¶ÆDżṚ$ÇÞḢ for 14 bytes, it returns a list [a, b] given n as an argument. \$\endgroup\$ – miles Sep 12 '16 at 20:18
  • \$\begingroup\$ @miles Cool! I apparently completely missed on /. (This is what I did in my Pyth solution.) Will edit when I get on my laptop. \$\endgroup\$ – PurkkaKoodari Sep 12 '16 at 20:23
7
\$\begingroup\$

Pyth - 24 23 bytes

There has to be a better way to find the divisors...

ho.a-.n3cFNfsIeTm,dcQdS

Test Suite.

\$\endgroup\$
  • 6
    \$\begingroup\$ Not any shorter, but much faster: hoa.n3cFNm,d/Qdm*Fdty+1P. Tests \$\endgroup\$ – TheBikingViking Sep 11 '16 at 20:14
6
\$\begingroup\$

Matlab, 96 81 bytes

Golfed (-15bytes), props to 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)]

This is by far not a great solution, but my first attempt at code-golf. What fun!

\$\endgroup\$
  • 2
    \$\begingroup\$ Agreed that it's fun! Welcome to the site! \$\endgroup\$ – DJMcMayhem Sep 12 '16 at 3:20
  • 1
    \$\begingroup\$ You can replace not by ~ to save a few bytes. Also, using the second output of min you can get rid of find: a=find(~(mod(n,1:n)));[~,c]=min(abs(a./(n./a)-1.618));[a(c) n/a(c)] \$\endgroup\$ – Luis Mendo Sep 12 '16 at 10:34
  • \$\begingroup\$ Well spotted - that shaves off quite some symbols! \$\endgroup\$ – ptev Sep 12 '16 at 11:22
  • 1
    \$\begingroup\$ You can make it shorter by using n=input(''); instead of function w(n); then you have an extra pair of () around the mod. \$\endgroup\$ – flawr Sep 13 '16 at 10:00
5
\$\begingroup\$

05AB1E, 21 bytes

Code:

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

Uses the CP-1252 encoding. Try it online!

\$\endgroup\$
5
\$\begingroup\$

Mathematica, 51 bytes

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

The is Mathematica's postfix operator for transposition (displayed as a superscript T in Mathematica).

Mathematica has a built-in GoldenRatio, but 1.618 is a lot shorter, especially because the former also requires N@.

\$\endgroup\$
5
\$\begingroup\$

Pyth, 21 20 18 bytes

hoacFN.n3C_Bf!%QTS

Try it online. Test suite.

Explanation

  1. Get the incluSive range from 1 to input.
  2. filter for numbers for that divide the input !%QT.
  3. Get [that list, that list reversed] _B. The reversed divisors of a number is the same list as the number divided by each of the divisors.
  4. Transpose the list to get pairs of [numerator, denominator].
  5. Sort the pairs by the absolute difference of the ratio of the pair cFN and the golden ratio .n3.
  6. Get the first (lowest) pair h and print.
\$\endgroup\$
5
\$\begingroup\$

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

We look for:

  • a = highest divisor of n for which n / φ > a²
  • b = lowest divisor of n for which n / φ < b²

Then, the solution is either [ a, n / a ] or [ b, n / b ]. We compare n / φ - a² with b² - n / φ to find out which expression is closest to zero.

The actual formula used in the code are based on φ / 2 which can be written in a shorter way than φ with the same precision: .809 vs 1.618.

Therefore:

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

and:

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

Complexity

The number of iterations heavily depends on the number of factors of n. The worst case occurs when n is prime, because we have to perform all iterations from 1 to n to find its only 2 divisors. This is what happens with 199999. On the other hand, 9699690 is 19-smooth and we quickly find two divisors on either sides of the breaking point √(n/φ) ≈ 2448.

Test cases

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 ]

\$\endgroup\$
4
\$\begingroup\$

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>

Actually returns the (a, b) pair which minimises the absolute value of a/b-b/a-1, but this works for all the test cases at least, although I guess I could save 4 bytes by using the 1.618 test instead.

\$\endgroup\$
3
\$\begingroup\$

Brachylog, 41 bytes

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

Try it online!

Explanation

  • Main predicate:

    :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
    
  • Predicate 1: Output is a couple [A:B] such that 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
    
  • Predicate 2: Compute the distance between A/B and φ.

    :3a            Convert A and B to floats
       /           Divide A by B
        :$A-       Subtract φ
            $|     Absolute value
    
  • Predicate 3: Convert an int to a float by inverting its inverse

    /              1/Input
     /             Output = 1/(1/Input)
    
\$\endgroup\$
  • \$\begingroup\$ Out of curiosity: is φ a predefined literal in Brachylog? Or where is it defined in the code? \$\endgroup\$ – Luis Mendo Sep 13 '16 at 10:38
  • 1
    \$\begingroup\$ Oh, I just saw: $A \$\endgroup\$ – Luis Mendo Sep 13 '16 at 10:40
  • 2
    \$\begingroup\$ @LuisMendo A for Au ;) \$\endgroup\$ – Fatalize Sep 13 '16 at 11:26
  • \$\begingroup\$ Aaah, very nice! \$\endgroup\$ – Luis Mendo Sep 13 '16 at 13:03
2
\$\begingroup\$

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]
\$\endgroup\$
2
\$\begingroup\$

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;

Produces a notice (this doesn't interrupt execution) about unassigned $i so should be run in an environment that silences notices.

\$\endgroup\$
  • \$\begingroup\$ Counting the PHP open tag is not needed when the code can be run as php -r '…' (where -r is for free). And definitely no need for the long form, as short_open_tag is on by default. \$\endgroup\$ – manatwork Sep 12 '16 at 9:55
  • \$\begingroup\$ As far as I know $argv doesn't work with -r so this can't be run like that anyway. That said changing it to readline() or fgets(STDIN) if you're on windows and running without the tag is probably shorter anyway. \$\endgroup\$ – user59178 Sep 12 '16 at 13:56
  • \$\begingroup\$ -r and $argv are working well together: pastebin.com/vcgb5pT2 \$\endgroup\$ – manatwork Sep 12 '16 at 14:19
  • \$\begingroup\$ Huh. Well it doesn't work for me, I just get undefined variable notices, I wonder if it's a setting or if it's just windows as per usual. \$\endgroup\$ – user59178 Sep 12 '16 at 15:41
  • \$\begingroup\$ You can still replace <?php with <? to save three bytes. \$\endgroup\$ – Paul Schmitz Sep 12 '16 at 18:24
1
\$\begingroup\$

Python 3, 96 bytes

Pretty simple solution. Makes use of this SO answer.

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]

Try it online

The same solution in Python 2 is one byte longer.

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]
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.