-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.
If
a>=0
anda<b
are there ever multiple solutions? – Jonathan Allan – 2017-11-12T00:09:11.017I can't guarantee that there are or aren't multiple solutions. Both
1,4
and2,3
would give5
, 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. – Stewie Griffin – 2017-11-12T00:22:12.523I checked up to 7457, and I didn't find any multiple solutions, although I haven't thought of any obvious proof. – Ørjan Johansen – 2017-11-12T02:12:00.133
2
totally inspired by https://codegolf.stackexchange.com/q/147200/67961
– J42161217 – 2017-11-12T02:28:11.573... But certainly not a dupe. – user202729 – 2017-11-12T06:53:42.020
@ØrjanJohansen What do you means by "multiple solution"? Two pairs
(a1, b1)
and(a2, b2)
such thata1+b1=a2+b2
anda1≠a2
andb1≠b2
? – user202729 – 2017-11-12T06:55:35.370@user202729 Yes, but still with minimal sum. – Ørjan Johansen – 2017-11-12T17:12:23.197
3
The corresponding OEIS sequence for the lowest possible mean, A249783, has a wild looking graph.
– Peter Kagey – 2017-11-12T19:20:33.8731@ØrjanJohansen I added a proof to my answer that there are no duplicate solutions (since my answer depended on it). – cardboard_box – 2017-11-12T21:26:56.997