Upper or Lower Wythoff? First, let's talk about Beatty sequences. Given a positive irrational number r, we can construct an infinite sequence by multiplying the positive integers to r in order and taking the floor of each resulting calculation. For example,


If r > 1, we have a special condition. We can form another irrational number s as s = r / (r - 1). This can then generate its own Beatty sequence, Bs. The neat trick is that Br and Bs are complementary, meaning that every positive integer is in exactly one of the two sequences.

If we set r = ϕ, the golden ratio, then we get s = r + 1, and two special sequences. The lower Wythoff sequence for r:

1, 3, 4, 6, 8, 9, 11, 12, 14, 16, 17, 19, 21, 22, 24, 25, 27, 29, ... 


and the upper Wythoff sequence for s:

2, 5, 7, 10, 13, 15, 18, 20, 23, 26, 28, 31, 34, 36, 39, 41, 44, 47, ... 


These are sequences A000201 and A001950 on OEIS, respectively.

The Challenge

Given a positive input integer 1 &lt;= n &lt;= 1000, output one of two distinct values indicating whether the input is in the lower Wythoff sequence or the upper sequence. The output values could be -1 and 1, true and false, upper and lower, etc.

Although your submitted algorithm must theoretically work for all inputs, in practice it only has to work with the first 1000 input numbers.

I/O and Rules


The input and output can be given by any convenient method.
The input and output can be assumed to fit in your language's native number type.
Either a full program or a function are acceptable. If a function, you can return the output rather than printing it.
Standard loopholes are forbidden.
This is code-golf so all usual golfing rules apply, and the shortest code (in bytes) wins.
JavaScript (ES6), 50 35 bytes



f=(n,s="1",t=0)=&gt;s[n-1]||f(n,s+t,s)
&lt;input type=number min=1 oninput=o.textContent=this.value&amp;amp;&amp;amp;f(this.value)&gt;&lt;pre id=o&gt;




Outputs 1 for lower and 0 for upper. Explanation: Partial lists of boolean values can be constructed using a Fibonacci-like identity: given two lists, starting with 1 and 10, each subsequent list is the concatenation of the previous two, resulting in 101, 10110, 10110101 etc. In this case it's slightly golfier to have a fake 0th entry of 0 and use that to construct the second element of the list.