# Find the minimal initial values [duplicate]

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

• does 12 -> [4, 0] count? – Flame Nov 2 '18 at 19:10
• F is a sequence of positive integers, and 0 isn't positive, so that's not valid. – recursive Nov 2 '18 at 19:10
• Nitpick: the Fibonacci sequence may be defined by $F[0] = 0, F[1] = 1$ or $F[1] = F[2] = 1$. Many of the sequence's well-known properties rely on this indexing. – Dennis Nov 2 '18 at 20:58
• @Dennis: Technical correctness being the best kind, I've tweaked that part. – recursive Nov 2 '18 at 21:28
• I knew this challenge looked familiar but I couldn't find it. I've closed it, although I forgot that my vote was a hammer. – Giuseppe Nov 2 '18 at 23:28

# 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.


# 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


# Perl 6, 52 bytes

->\n{(1..n X 1..n).max:{(n∈(|\$_,*+*...*>n))/.sum}}


Try it online!

Brute-force solution.

f x=[(a,s-a)|s<-[2..],a<-[1..s-1],let u=s-a:zipWith(+)u(a:u),xelemtake x u]!!0


Try it online!

• head[...] can be [...]!!0. – Laikoni Nov 3 '18 at 9:07

# JavaScript, 216 bytes

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 n}function s(r,n,f){return n==f||(f<n?null:s(n,r+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++;
}
}