9
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ does 12 -> [4, 0] count? \$\endgroup\$ – Flame Nov 2 '18 at 19:10
  • \$\begingroup\$ F is a sequence of positive integers, and 0 isn't positive, so that's not valid. \$\endgroup\$ – recursive Nov 2 '18 at 19:10
  • \$\begingroup\$ 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. \$\endgroup\$ – Dennis Nov 2 '18 at 20:58
  • \$\begingroup\$ @Dennis: Technical correctness being the best kind, I've tweaked that part. \$\endgroup\$ – recursive Nov 2 '18 at 21:28
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Giuseppe Nov 2 '18 at 23:28
3
\$\begingroup\$

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

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

Perl 6, 52 bytes

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

Try it online!

Brute-force solution.

\$\endgroup\$
1
\$\begingroup\$

Haskell, 81 80 bytes

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

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ head[...] can be [...]!!0. \$\endgroup\$ – Laikoni Nov 3 '18 at 9:07
0
\$\begingroup\$

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++;
    }
}
\$\endgroup\$

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