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

• Jonathan Allan: If a>=0 and a<b are there ever multiple solutions?
• Stewie Griffin: I can't guarantee that there are or aren't multiple solutions. Both 1,4 and 2,3 would give 5, and they have the same mean. I guess it's possible to find cases similar to that one, where these are the lowest mean values. If you can show/prove that there aren't multiple solutions then you don't need to check for that condition.
• ZaMoC: totally inspired by codegolf.stackexchange.com/q/147200/67961
• Peter Kagey: The corresponding OEIS sequence for the lowest possible mean, A249783, has a wild looking graph.
• cardboard_box: @ØrjanJohansen I added a proof to my answer that there are no duplicate solutions (since my answer depended on it).

Answer 1

Husk, (削除) 19 (削除ここまで) (削除) 18 (削除ここまで) (削除) 16 (削除ここまで) (削除) 14 (削除ここまで) (削除) 13 (削除ここまで) 15 bytes

Thanks Zgarb for saving 1 byte.

ḟö0ドルƒẊ++ÖΣṖ2Θḣ0

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)

 Θḣ0 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.
 ö0ドル Is the input in that list (given that it is in sorted order)?

• Zgarb: Save a byte with ö
• H.PWiz: I'm sure I tried that...

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.

• user72349: 89 bytes
• Neil: 77 bytes
• cardboard_box: @Neil That minimizes b instead of minimizing a+b, and thus your solution gives f(27) = [3,7] but the optimal solution is f(27)=[0,9]. After reverting the breaking changes we're down to 83 bytes.
• Neil: I think you can save another byte by using b-~a instead of a+b+1.
• Ørjan Johansen: There's a small error in your second case: a2 >= a1 + b1 isn't correct when k1-k0=1. Instead you can use a2 >= b1 > a0 and b2 >= a1+b1 = a0+b0, and then the rest follows.

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.

• Giuseppe: 160 bytes -- in general, you should save bytes wherever you can, so saving 4 bytes by removing nice naming is not only acceptable or encouraged but in some sense required by code-golf. Even so, nice answer, +1.

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ṭμ¡3e
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.

• Jonathan Allan: ...a leading increment should resolve @StewieGriffin's observation.
• Jonathan Allan: I have a feeling you can drop the Ḣ
• Jonathan Allan: We only need to find the seed that makes the input, x, appear latest. If x were found at the third index for multiple then it works for 0,x and would therefore also work at either 1,(x-1)/2 (x odd) or 2,x/2-1 (x even) whereupon x would appear later in the result, so that wont happen. For a later collision the mean can only be the same if the third terms are the same too, but then one must have a lower difference between the initial terms (else they'd be the same) and hence will have x found at a later index. As such we can do ṫ-Sṭµ¡i³¶ḶŒcÇÐṀ saving four bytes.
• Jonathan Allan: ...oops, plus the increment: ṫ-Sṭµ¡i³¶‘ḶŒcÇÐṀ
• Erik the Outgolfer: @StewieGriffin That test-case didn't exist when I answered :p

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

• Ørjan Johansen: Try it online!

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%

• cardboard_box: This (also) gives 3 7 on input 27. The correct solution is 0 9.
• Neil: @cardboard_box Still not seeing where the question requires that...
• cardboard_box: In the first sentence: "with the lowest possible mean value".
• Neil: @cardboard_box Ah, sorry, that was too easy to overlook.
• Neil: @cardboard_box OK should be fixed now.