The lowest initial numbers in a Fibonacci-like sequence

Question

Given a positive integer input N, output the two non-negative numbers, a and b, where a < b, with the lowest possible mean value that will result in the number N being part of the recurring relation sequence:

f(0) = a
f(1) = b
f(n) = f(n-2)+f(n-1)

In case there are more than one solution where the mean of a and b are minimal, then you should output the one with the lowest b. Proof that this is not possible is provided by cardboard_box.

Your can assume N is within the representative range of integers in your language / system.

Test cases

N = 1
a = 0, b = 1

N = 15
a = 0, b = 3

N = 21
a = 0, b = 1

N = 27
a = 0, b = 9   <- Tricky test case. [3, 7] is not optimal and [4, 3] is not valid

N = 100
a = 4, b = 10

N = 101
a = 1, b = 12

N = 102
a = 0, b = 3

N = 1000
a = 2, b = 10

Answer 1

Husk, 19 18 16 14 13 15 bytes

Thanks Zgarb for saving 1 byte.

ḟö£⁰ƒẊ++ÖΣṖ2Θḣ⁰

Try it online!

Explanation:

Disclaimer: I really don't understand the ȯƒẊ++ section of the code.

Edit: It appears to translate to the Haskell fix.(mapad2(+).).(++), where mapad2 is apply function to all adjacent pairs in a list. (Although, knowing Husk, in the context of this program it could mean something else)

            Θḣ⁰    Create the list [0..input]
          Ṗ2       Generate all possible sublists of length 2
        ÖΣ         Sort them on their sums
ḟ                  Find the first element that satisfies the following predicate.
    ƒẊ++             Given [a,b], magically generate the infinite Fibonacci-like
                     sequence from [a,b] without [a,b] at the start.
 ö£⁰                 Is the input in that list (given that it is in sorted order)?

Answer 2

JavaScript (Node.js), 92 90 89 91 83 82 bytes

-3 bytes -1 byte thanks to ThePirateBay

-8 -9 bytes thanks to Neil.

f=(n,a=1,b=0,c=(a,b)=>b<n?c(a+b,a):b>n)=>c(a,b)?b+2<a?f(n,a-1,b+1):f(n,b-~a):[b,a]

Try it online!

Note: this solution relies on the fact that there are never multiple minimal solutions.

Proof that there are never multiple solutions:

Let FIB(a,b,k) be the Fibonacci-like sequence starting with a,b:

FIB(a,b,0) = a
FIB(a,b,1) = b
FIB(a,b,k) = FIB(a,b,k-1) + FIB(a,b,k-2)

Lemma 1

The difference between Fibonacci-like sequences is itself Fibonacci-like, i.e. FIB(a1,b1,k) - FIB(a0,b0,k) = FIB(a1-a0,b1-b0,k). The proof is left to reader.

Lemma 2

For n >= 5, a solution a,b exists satisfying a+b < n:

if n is even, FIB(0,n/2,3) = n

if n is odd, FIB(1,(n-1)/2,3) = n

Proof

Cases where n < 5 can be checked exhaustively.

Suppose we have two minimal solutions for n >= 5, a0,b0 and a1,b1 with a0 + b0 = a1 + b1 and a0 != a1.

Then there exist k0,k1 such that FIB(a0,b0,k0) = FIB(a1,b1,k1) = n.

• Case 1: k0 = k1

  WLOG assume b0 < b1 (and therefore a0 > a1)

  Let DIFF(k) be the difference between the Fibonnaci-like sequences starting with a1,b1 and a0,b0:

  DIFF(k) = FIB(a1,b1,k) - FIB(a0,b0,k) = FIB(a1-a0,b1-b0,k) (Lemma 1)

  DIFF(0) = a1 - a0 < 0

  DIFF(1) = b1 - b0 > 0

  DIFF(2) = (a1+b1) - (a0+b0) = 0

  DIFF(3) = DIFF(1) + DIFF(2) = DIFF(1) > 0

  DIFF(4) = DIFF(2) + DIFF(3) = DIFF(3) > 0

  Once a Fibonnaci-like sequence has 2 positive terms, all subsequent terms are positive.

  Thus, the only time DIFF(k) = 0 is when k = 2, so the only choice for k0 = k1 is 2.

  Therefore n = FIB(a0,b0,2) = a0 + b0 = a1 + b1

  The minimality of these solutions contradicts Lemma 2.

• Case 2: k0 != k1:

  WLOG assume k0 < k1.

  We have FIB(a1,b1,k1) = n

  Let a2 = FIB(a1,b1,k1-k0)

  Let b2 = FIB(a1,b1,k1-k0+1)

  Then FIB(a2,b2,k0) = FIB(a1,b1,k1) = FIB(a0,b0,k0) (exercise for the reader)

  Since FIB(a1,b1,k) is non-negative for k >= 0, it is also non-decreasing.

  This gives us a2 >= b1 > a0 and b2 >= a1+b1 = a0+b0.

  Then let DIFF(k) = FIB(a2,b2,k) - FIB(a0,b0,k) = FIB(a2-a0,b2-b0,k) (Lemma 1)

  DIFF(0) = a2 - a0 > 0

  DIFF(1) = b2 - b0 >= (a0 + b0) - b0 = a0 >= 0

  DIFF(2) = DIFF(0) + DIFF(1) >= DIFF(0) > 0

  DIFF(3) = DIFF(1) + DIFF(2) >= DIFF(2) > 0

  Once again, DIFF has 2 positive terms and therefore all subsequent terms are positive.

  Thus, the only time when it's possible that DIFF(k) = 0 is k = 1, so the only choice for k0 is 1.

  FIB(a0,b0,1) = n

  b0 = n

  This contradicts Lemma 2.

Answer 3

Haskell, 76 72 74 bytes

EDIT:

• -4 bytes: @H.PWiz suggested using / instead of div, although this requires using a fractional number type.
• +2 bytes: Fixed a bug with Enum ranges by adding -1.

f takes a value of Double or Rational type and returns a tuple of same. Double should suffice for all values that are not large enough to cause rounding errors, while Rational is theoretically unlimited.

f n|let a?b=b==n||b<n&&b?(a+b)=[(a,s-a)|s<-[1..],a<-[0..s/2-1],a?(s-a)]!!0

Try it online! (with H.PWiz's header adjustments to input/output Rationals in integer format)

How it works

• ? is a locally nested operator in the scope of f. a?b recursively steps through the Fibonacci-like sequence starting with a,b until b>=n, returning True iff it hits n exactly.
• In the list comprehension:
  • s iterates through all numbers from 1 upwards, representing the sum of a and b.
  • a iterates through the numbers from 0 to s/2-1. (If s is odd the end of range rounds up.)
  • a?(s-a) tests if the sequence starting with a,s-a hits n. If so, the list comprehension includes the tuple (a,s-a). (That is, b=s-a, although it was too short to be worth naming.)
  • !!0 selects the first element (hit) in the comprehension.

Answer 4

APL (Dyalog), 75 71 64 59 53 48 44 43 bytes

2 bytes saved thanks to @Adám

12 bytes saved thanks to @ngn

⊃o/⍨k∊¨+\∘⌽⍣{k≤⊃⍺}¨o←a/⍨</¨a←,⍉|-\¨⍳2⍴1+k←⎕

Try it online!

Uses ⎕IO←0.

How? This had gone real nuts.

k←⎕ - assign input to k

⍳2⍴1+k←⎕ - Cartesian product of the range 0 to k with itself

|-\¨ - substract each right pair element from the left, and get absolute values

a←,⍉ - transpose, flatten and assign to a

o←a/⍨</¨a - keep only pairs where the left element is smaller than the right, and assign to o

o now contains list of all pairs with a < b, ordered by their arithematical mean

+\∘⌽⍣{k≤⊃⍺}¨o - for each pair in o, apply fibonacci (reverse the pair and cumsum) until k or higher term is reached

k∊¨ - then decide if k is this last term (meaning it is contained in the sequence)

o/⍨ - and keep pairs in o where the previous check applies

⊃ - return the first result.

Answer 5

Python 2, 127 109 107 bytes

-2 bytes thanks to ovs (changing and to *)

g=lambda x,a,b:a<=b<x and g(x,b,a+b)or b==x
f=lambda n,s=1,a=0:g(n,a,s-a)*(a,s-a)or f(n,s+(a==s),a%s+(a<s))

Try it online!

Any bonus points for n,a,s-a?

Explanation:

• The first line declares a recursive lambda, g, which verifies whether a, b expanded as a Fibonacci sequence will reach x. It also checks that a <= b, one of the criteria of the question. (This would allow cases where a == b, but in such a case 0, a would have already been discovered and returned).
  • The chained inequality a<=b<x performs two handy tasks at once: verifying a <= b, and that b < x.
  • If b < x yields True, the function calls itself again with the next two numbers in the Fibonacci sequence: b, a+b. This means the function will keep working out new terms until...
  • If b < x yields False, then we have reached the point where we need to check if b==x. If so, this will return True, signifying that the initial pair a, b will eventually reach x. Otherwise, if b > x, the pair is invalid.
• The second line declares another recursive lambda, f, which finds the solution for a given value n. It recursively tries new initial pairs, a, b, until g(n, a, b) yields True. This solution is then returned.
  • The function recursively counts up initial Fibonacci pairs using two variables, s (initially 1) and a (initially 0). On each iteration, a is incremented, and a, s-a is used as the first pair. However, when a hits s, it is reset back to 0, and s is incremented. This means the pairs are counted up in the following pattern:

    s=1 (0, 1) (1, 0)
    s=2 (0, 2) (1, 1)  (2, 0)
    s=3 (0, 3) (1, 2), (2, 1), (3, 0)
    

    Obviously, this contains some invalid pairs, however these are eliminated instantly when passed to g (see first bullet point).
  • When values a and s are found such that g(n, a, s-a) == True, then this value is returned. As the possible solutions are counted up in order of 'size' (sorted by mean, then min value), the first solution found will always be the smallest, as the challenge requests.

Answer 6

R, 183 bytes 160 bytes

n=scan();e=expand.grid(n:0,n:0);e=e[e[,2]>e[,1],];r=e[mapply(h<-function(n,a,b,r=a+b)switch(sign(n-r)+2,F,T,h(n,b,r)),n,e[,1],e[,2]),];r[which.min(rowSums(r)),]

Try it online!

Thanks to Giuseppe for golfing off 23 bytes

Code explanation

n=scan()                        #STDIO input
e=expand.grid(n:0,n:0)          #full outer join of integer vector n to 0
e=e[e[,2]>e[,1],]               #filter so b > a
r=e[mapply(
  h<-function(n,a,b,r=a+b)switch(sign(n-r)+2,F,T,h(n,b,r)),
                                #create a named recursive function mid-call 
                                #(requires using <- vs = to denote local variable creation 
                                #rather than argument assignment
  n,e[,1],e[,2]),]              #map n, a and b to h() which returns a logical
                                #which is used to filter the possibilities
r[which.min(rowSums(r)),]       #calculate sum for each possibility, 
                                #get index of the minimum and return
                                #because each possibility has 2 values, the mean and 
                                #sum will sort identically.

Answer 7

Mathematica, 117 bytes

If[#==1,{0,1},#&@@SortBy[(S=Select)[S[Range[0,s=#]~Tuples~2,Less@@#&],!FreeQ[LinearRecurrence[{1,1},#,s],s]&],Mean]]&

Try it online!

Answer 8

Jelly, 19 bytes

ṫ-Sṭµ¡³e
0rŒcÇÐfSÐṂ

Try it online!

-1 byte thanks to the proof by cardboard_box. In case it's disproved, you can append UṂṚ to the end of the second line for 22 bytes in total.

Answer 9

GolfScript - 88 77 bytes

~:N[,{1+:a,{[.;a]}/}/][{[.~{.N<}{.@+}while\;N=]}/]{)1=\;},{(\;~+}$(\;);~~' '\

I did not check for multiple solutions, thanks to cardboard_box!

Explanation

~:N                           # Reads input
[,{1+:a,{[.;a]}/}/]           # Creates an array of pairs [a b]
[{[.~{.N<}{.@+}while\;N=]}/]  # Compute solutions
{)1=\;},         # Pairs that are not solutions are discarded
{(\;~+}$         # Sorts by mean
(\;);~~' '\      # Formats output

Answer 10

Batch, 160 158 bytes

@set/aa=b=0
:g
@if %a% geq %b% set/ab-=~a,a=0
@set/ac=a,d=b
:l
@if %c% lss %1 set/ad+=c,c=d-c&goto l
@if %c% gtr %1 set/aa+=1,b-=1&goto g
@echo %a% %b%