Consider a sequence F of positive integers where F(n) = F(n-1) + F(n-2) for n >= 2. The Fibonacci sequence is almost one example of this type of sequence for F(0) = 0, F(1) = 1, but it's excluded because of the positive integer requirement. Any two initial values will yield a different sequence. For example F(0) = 3, F(1) = 1 produces these terms.

3, 1, 4, 5, 9, 14, 23, 37, 60, 97, ...

Challenge

The task is to find F(0) and F(1) that minimize F(0) + F(1) given some term of a sequence F(n). Write a function or complete program to complete the task.

Input

Input is a single positive integer, F(n). It may be accepted as a parameter or from standard input. Any reasonable representation is allowed, including direct integer or string representations.

Invalid inputs need not be considered.

Output

The output will be two positive integers, F(0) and F(1). Any reasonable format is acceptable. Here are some examples of reasonable formats.

• Written on separate lines to standard output


• Formatted on standard output as a delimited 2-element list


• Returned as a tuple or 2-element array of integers from a function

Examples

60 -> [3, 1]
37 -> [3, 1]
13 -> [1, 1]
26 -> [2, 2]
4 -> [2, 1]
5 -> [1, 1]
6 -> [2, 2]
7 -> [2, 1]
12 -> [3, 2]
1 -> [1, 1]

Scoring

This is code golf. The score is calculated by bytes of source code.

Sandbox

Japt, 34 bytes

_Ì<U?[ZÌZx]gV:ZÌ
õ ïUõ)ñx æ_gV ¥U

Try it online!

The empty first line is important.

Explanation:

_ Declare a function V:
 Ì<U? :ZÌ If the second number is >= n, return it
 [ZÌZx]gV Otherwise call V again with the second number and the sum


õ ïUõ) Get all pairs of positive integers where both are less than n
 ñx Sort them by their sum
 æ_gV ¥U Return the first (lowest sum) one where V returns n

Jelly, 13 bytes

pWạṚ$</¿€SÞḢ

Try it online!

How it works

pWạṚ$</¿€SÞḢ Main link. Argument: n

 W Wrap; yield [n].
p Cartesian product; promote the left argument n to [1, ..., n] and take
 the product of [1, ..., n] and n, yielding [[1, n], ..., [n, n]].
 € Map the link to the left over the pairs [k, n].
 ¿ While...
 </ reducing the pair by less-than yields 1:
 ạ Cumulatively reduce the pair by absolute difference.
 Ṛ Reverse the result.
 In essence, starting with [a, b] := [k, n], we keep executing
 [a, b] := [b, |a - b|], until the pair is no longer increasing.
 SÞ Sort the resulting pairs by their sums.
 Ḣ Head; extract the first pair.

JavaScript (216 characters)

function f(r)for(var n=1;;)var f=p(n);for(var u in f)if(s(f[u][0],f[u][1],r))return f[u];n++function p(r)for(var n=,f=1;0<r;)n.push([r,f]),r--,f++;return nfunction s(r,n,f)return n==f

https://jsfiddle.net/twkz2gyb/

(Ungolfed code):

// For a given input n, return all combinations of positive integers that sum to n.
function findPairs(n) 
 var arr = ;
 var b = 1;
 while(n > 0) 
 arr.push([n, b]);
 n--;
 b++;
 
 return arr;


// Run a sequence for a and b, and continue fibonacci'ing until r is found(or quit if past r).
function sequence(a, b, r) 
 if(b === r) 
 return true;
 else if(b > r) 
 return null;
 
 var nextFibo = a + b;
 return sequence(b, nextFibo, r);


// For a given n, find the first 2 numbers of the fibonacci sequence with the smallest sum that result in n.
function find(n) 
 var i = 1;
 while(i < 10) 
 var pairs = findPairs(i);
 for(var p in pairs) 
 var result = sequence(pairs[p][0], pairs[p][1], n);
 if(result) 
 return pairs[p];
 
 
 i++;
 

Haskell, 81 bytes

f x=head[(a,s-a)|s<-[2..],a<-[1..s-1],let u=s-a:zipWith(+)u(a:u),x`elem`take x u]

Try it online!

Perl 6, 52 bytes

->n(1..n X 1..n).max:(n∈(

Try it online!

Brute-force solution.