# 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 <= n <= 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 so all usual golfing rules apply, and the shortest code (in bytes) wins.
• It's basically "golf the lower Wythoff sequence" because the upper Wythoff sequence requires 1 more op than the lower one (squaring phi). Jun 15, 2018 at 13:28

## JavaScript (ES6), 50 35 bytes

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

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.

• How the what... Jun 15, 2018 at 13:52
• I love how the explanation made me understand less +1. Partial boolean whoozits steal the identity of a man named Fibbonacci, who is then connected together with his grandchildren to fake the entry of construction. Jun 15, 2018 at 14:10
• I was curious to know how far this 33-byte version could work by using an approximation. The answer is apparently up to n = 375. Jun 15, 2018 at 15:18

# Python, 25 bytes

lambda n:-n*2%(5**.5+1)<2


Try it online!

Uses the very simple condition:

n is in the lower Wythoff sequence exactly if -n%phi<1.

Note that the modulo result is positive even though -n is negative, matching how Python does modulo.

Proof: Let a = -n%phi, which lies in the range 0 <= a < phi. We can split -n modulo phi as -n = -k*phi + a for some positive integer k. Rearrange that to n+a = k*phi.

If a<1, then n = floor(n+a) = floor(k*phi), and so is in the lower Wythoff sequence.

Otherwise, we have 1 <= a < phi so

n+1 = floor(n+a) = floor(k*phi)
n > n+a-phi = k*phi - phi = (k-1)*phi


so n falls in the gap between floor((k-1)*phi) and floor(k*phi) and is missed by the lower Wythoff sequence.

This corresponds to this code:

lambda n:-n%(5**.5/2+.5)<1


Try it online!

We save a byte by doubling to -(n*2)%(phi*2)<2.

• Could you explain how the formula comes about? I tried to derive it from the sequence definitions, but got lost in the woods. Jun 15, 2018 at 19:19
– xnor
Jun 15, 2018 at 23:18
• This exact same technique works in Ruby and JavaScript (at least), too Aug 23, 2020 at 12:15

(l!!)
l=0:do x<-l;[1-x..1]


Try it online!

No floats, unlimited precision. Thanks for H.PWiz for two bytes.

• This would also be 26 bytes, but I don't understand why it doesn't work Jun 15, 2018 at 21:44
• @H.PWiz I think it's because the empty list is a fixed point.
– xnor
Jun 15, 2018 at 21:50
• Ah, I hadn't considered that, and was comparing it with an "equivalent" method that used ~(x:t). Thanks Jun 15, 2018 at 21:52
• @H.PWiz / xnor Technically in Haskell the fixed point used is the denotationally smallest one, here bottom / undefined. The fact that there are two different defined ones as well is just accidental. Jun 17, 2018 at 15:25

# 05AB1E, 9 bytes

L5t>;*óså


Try it online!

0 means upper, 1 means lower. Try the first 100: Try it online!

    CODE   |      COMMAND      # Stack (Input = 4)
===========+===================#=======================
L          | [1..a]            # [1,2,3,4]
5t>;      | (sqrt(5) + 1)/2   # [phi, [1,2,3,4]]
*     | [1..a]*phi        # [[1.6,3.2,4.8,6.4]]
ó    | floor([1..a]*phi) # [[1,3,4,6]]
så  | n in list?        # []


Raw Command Dump:

----------------------------------
Depth: 0
Stack: []
Current command: L

----------------------------------
Depth: 0
Stack: [[1, 2, 3, 4]]
Current command: 5

----------------------------------
Depth: 0
Stack: [[1, 2, 3, 4], '5']
Current command: t

----------------------------------
Depth: 0
Stack: [[1, 2, 3, 4], 2.23606797749979]
Current command: >

----------------------------------
Depth: 0
Stack: [[1, 2, 3, 4], 3.23606797749979]
Current command: ;

----------------------------------
Depth: 0
Stack: [[1, 2, 3, 4], 1.618033988749895]
Current command: *

----------------------------------
Depth: 0
Stack: [[1.618033988749895, 3.23606797749979, 4.854101966249685, 6.47213595499958]]
Current command: ó

----------------------------------
Depth: 0
Stack: [[1, 3, 4, 6]]
Current command: s

----------------------------------
Depth: 0
Stack: [[1, 3, 4, 6], '4']
Current command: å
1
stack > 

• I had the same, but using ï :) Jun 15, 2018 at 13:34
• @emigna I was surprised phi wasn't in the mathematical constants. 5t>; to a 2 byter may not be worth it though... Jun 15, 2018 at 13:34
• Yeah, I was half-remembering that it might have been (but it's not). It seems like something we should add. Jun 15, 2018 at 13:36
• @Emigna I'm fairly certain the Jelly answer is legitimately this but with a phi built-in hahah. Jun 15, 2018 at 13:37
• Haha I had the same but using ï and ¢ lol :) All our solutions are so closely related Jun 15, 2018 at 13:40

# Jelly, 5 bytes

N%ØpỊ


Try it online!

Saved 1 byte thanks to xnor's Python golf.

### Jelly, 6 bytes

×€ØpḞċ


Try it online!

Returns 1 for lower and 0 for upper.

×€ØpḞċ – Full Program / Monadic Link. Argument: N.
×€     – Multiply each integer in (0, N] by...
Øp   – Phi.
Ḟ  – Floor each of them.
ċ – And count the occurrences of N in that list.


Checking $(0,\:N]\cap \mathbb{Z}$ is most definitely enough because $\varphi > 1$ and $N > 0$ and therefore $0 < N < N\varphi$.

• I'm guessing one of those is a 1-byte constant for phi :P? Jun 15, 2018 at 13:36
• Nope, a two-byte one: Øp Jun 15, 2018 at 13:36
• Hehe, better than my 4-byte one in 05AB1E: 5t>; Jun 15, 2018 at 13:38

# Brain-Flak, 78 bytes

([{}]()){<>{}((([()]))){{<>({}())}{}(([({})]({}{})))}<>([{}]{}<>)}<>({}()){{}}


Try it online!

Outputs nothing for lower and 0 for upper. Changing to a more sensible output scheme would cost 6 bytes.

# Python 2, 3933 32 bytes

-6 bytes thanks to Mr. Xcoder
-1 byte thanks to Zacharý

lambda n,r=.5+5**.5/2:-~n//r<n/r


Try it online!

Returns False for lower and True for upper

• lambda n,r=(1+5**.5)/2:-~n//r<n/r saves 6 bytes. Jun 15, 2018 at 13:58
• Also, lambda n,r=.5+5**.5/2:-~n//r<n/r should work as well to shave one byte Jun 15, 2018 at 17:56

# Julia 0.6, 16 bytes

n->n÷φ<-~n÷φ


Try it online!

While playing around with the numbers, I came across this property: floor(n/φ) == floor((n+1)/φ) if n is in the upper Wythoff sequence, and floor(n/φ) < floor((n+1)/φ) if n is in the lower Wythoff sequence. I haven't figured out how this property comes about, but it gives the correct results at least upto n = 100000 (and probably beyond).

# Julia 0.6, 31 bytes

n->n∈[floor(i*φ)for i∈1:n]


Try it online!

Returns true for lower and false for upper Wythoff sequence.

• As n/φ of the numbers up to n are lower and the others are upper, the average difference between successive lower numbers is φ; dividing the lower numbers by φ gives you a sequence where the average difference is 1; this makes it possible for the floor of that sequence to be the integers. My maths isn't good enough to take it any further though.
– Neil
Jun 16, 2018 at 18:10

# Arn, 9 bytes

2>6Yx!¦ü#


Try it!

# Explained

Unpacked: phi-1<%phi

I found another way of calculating this:

is true if n is in the Lower Wythoff Sequence

This example merely uses this formula (it was shorter than 1>((n_)%phi). And here is how it works:

    phi  Builtin for the Golden Ratio
-      Minus
1    Literal one
<        Is less than
_    Variable initialized to STDIN, implied
%      Modulo
phi


Returns true if lower, false if upper

• Yeah sorry, I posted this before I made an online interpreter. A link has been added Aug 24, 2020 at 12:43
• Great to know! Nice answer. Aug 24, 2020 at 12:53

# Wolfram Language (Mathematica), 26 bytes

#~Ceiling~GoldenRatio<#+1&


Try it online!

An integer n is in the lower Wythoff Sequence iff ceil(n/phi) - 1/phi < n/phi.

## Proof that ceil(n/phi) - 1/phi < n/phi is...

Sufficient:

1. Let ceil(n/phi) - 1/phi < n/phi.

2. Then, ceil(n/phi) * phi < n + 1.

3. Note n == n/phi * phi <= ceil(n/phi) * phi.

4. Hence, n <= ceil(n/phi) * phi < n + 1.

5. Since n and ceil(n/phi) are integers, we invoke the definition of floor and state floor(ceil(n/phi) * phi) == n, and n is in the lower Wythoff sequence.

Necessary; proof by contrapositive:

1. Let ceil(n/phi) - 1/phi >= n/phi.

2. Then, ceil(n/phi) * phi >= n + 1.

3. Note n + phi > (n/phi + 1) * phi > ceil(n/phi) * phi

4. Hence n > (ceil(n/phi) - 1) * phi.

5. Since (ceil(n/phi) - 1) * phi < n < n + 1 <= ceil(n/phi) * phi, n is not in the lower Wythoff sequence.

• This also doesn't have any rounding error. Jun 15, 2018 at 14:41

## APL (Dyalog Extended), 2119 13 bytes

⊢∊∘⌊⍳×1+∘÷⍣=≢


-6 bytes from Adám after conversion to tacit function.

Try it online!

{⍵∊⌊((1+∘÷⍣=1)×⍳⍵)}


Uses the same approach as Magic Octopus Urn's answer.

-2 bytes from ZippyMagician.

Prints 1 for upper and 0 for lower sequence.

## Explanation

{⍵∊⌊((2÷¯1+5*÷2)×⍳⍵)}
⍳⍵   Generate list of 1 to n
(2÷¯1+5*÷2)×     Multiply it by the golden ratio
⌊                  Floor the entire list
⍵∊                   is n in the list?


Try it online!

• -2 bytes Aug 22, 2020 at 19:53
• I'll keep that snippet somewhere, thanks! Aug 31, 2020 at 10:53
• 13 bytes: ⊢∊∘⌊⍳×1+∘÷⍣=≢ Try it online!
Aug 31, 2020 at 16:40
• I should get a lot more experience with trains and tacit functions. Aug 31, 2020 at 16:46

# Pyth, 8 bytes

/sM*.n3S


Try it here!

Returns 1 for lower and 0 for upper.

# Japt, 10 bytes

Returns true for lower and false for upper.

õ_*MQ fÃøU


Try it online!

## Explanation:

õ_*MQ fÃøU
// Implicit U = Input
õ            // Range [1...U]
_           // Loop through the range, at each element:
*MQ        //   Multiply by the Golden ratio
f      //   Floor
Ã     // End Loop
øU   // Return true if U is found in the collection

• I had this for 10 bytes too. Jun 15, 2018 at 16:14

# Java 10, 7753 52 bytes

n->{var r=Math.sqrt(5)/2+.5;return(int)(-~n/r)<n/r;}


Port of @Rod's Python 2 answer.
-1 byte thanks to @Zacharý.

Try it online.

n->{for(int i=0;i++<n;)if(n==(int)((Math.sqrt(5)+1)/2*i))return 1;return 0;}


-1 byte thanks to @ovs' for something I recommended myself last week.. xD

Returns 1 for lower; 0 for upper.

Try it online.

Explanation:

n->{                    // Method with integer as both parameter and return-type
for(int i=0;++i<=n;)  //  Loop i in the range [1, n]
if(n==(int)((Math.sqrt(5)+1)/2*i))
//   If n is equal to floor(Phi * i):
return 1;         //    Return 1
return 0;}            //  Return 0 if we haven't returned inside the loop already


i*Phi is calculated by taking (sqrt(5)+1)/2 * i, and we then floor it by casting it to an integer to truncate the decimal.

• ++i<=n on your old answer can be i++<n.
– ovs
Jun 15, 2018 at 14:28
• @ovs of course.. >.< I actually recommended this golf to someone else last week, lol.. Thanks. Jun 15, 2018 at 14:31
• I think this should work for -1 byte:n->{var r=Math.sqrt(5)/2+.5;return(int)(-~n/r)<n/r;} Jun 15, 2018 at 17:53
• @Zacharý It indeed does, thanks! Jun 15, 2018 at 18:04

Unlimited Precision!

l=length
f a c|n<-2*l a-c,n<0||l a<a!!n=c:a|1>0=a
g x=x==(foldl f[][1..x+1])!!0


Try it online!

## Explanation

Instead of using an approximation of the golden ratio to calculate the result meaning they are prone to errors as the size of the input rises. This answer does not. Instead it uses the formula provided on the OEIS that a is the unique sequence such that

∀n . b(n) = a(a(n))+1


where b is the ordered compliment.

• "All" wasn't even true before you got outgolfed...
– Neil
Jun 16, 2018 at 13:36
• @Neil Good point. I must have missed your answer. Jun 16, 2018 at 14:35
• Although your answer is limited by the fact that javascript doesn't have an integral type? Jun 16, 2018 at 14:37
• Well, it will run out of memory well before then...
– Neil
Jun 16, 2018 at 17:59

# Brachylog, 8 bytes

≥ℕ;φ×⌋₁?


Try it online!

The predicate succeeds if the input is in the lower Wythoff sequence and fails if it is in the upper Wythoff sequence.

 ℕ          There exists a whole number
≥           less than or equal to
the input such that
;φ×       multiplied by phi
⌋₁     and rounded down
?    it is the input.


If failure to terminate is a valid output method, the first byte can be omitted.

• This is probably the very first time φ is used in a Brachylog program. At long last! Mar 29, 2019 at 8:27

# cQuents, 5 bytes

?F$g  Try it online! ## Explanation ? output true if in sequence, false if not in sequence each term in the sequence equals: F floor ($               index *
g                     golden ratio
)                                 ) implicit


# MATL, 8 bytes

t:17L*km


Try it online!

### Explanation

t      % Implicit input. Duplicate
:      % Range
17L    % Push golden ratio (as a float)
*      % Multiply, element-wise
k      % Round down, element-wise
m      % Ismember. Implicit output


# K (oK), 20 bytes

Solution:

x in_(.5*1+%5)*1+!x:


Try it online!

Explanation:

x in_(.5*1+%5)*1+!x: / the solution
x: / save input as x
!   / generate range 0..x
*      / multiply by
(       )       / do this together
%5        / square-root of 5
.5*            / multiply by .5
_                / floor
x in                 / is input in this list?


# TI-BASIC (TI-84), 18 bytes

max(Ans=iPart((√(5)+1)/2randIntNoRep(1,Ans


Input is in Ans.
Output is in Ans and is automatically printed.
Prints 1 if input is in the lower sequence or 0 if it's in the upper sequence.

Coincidentally, this program will only run for $$\0 .

Example:

27
27
prgmCDGFA
1
44
44
prgmCDGFA
0


Explanation:

max(Ans=iPart((√(5)+1)/2randIntNoRep(1,Ans    ;full program, example input: 5
randIntNoRep(1,Ans    ;generate a list of random integers in [1,Ans]
; {1, 3, 2, 5, 4}
(√(5)+1)/2                      ;calculate phi and then multiply the resulting
;list by phi
; {1.618 4.8541 3.2361 8.0902 6.4721}
iPart(                                ;truncate
; {1 4 3 8 6}
Ans=                                      ;compare the input to each element in the list
;and generate a list based off of the results
; {0 0 0 0 0}
max(                                          ;get the maximum element in the list and
;implicitly print it


Note: TI-BASIC is a tokenized language. Character count does not equal byte count.

# MathGolf, 5 bytes

╒φ*i╧


Try it online.

Explanation:

╒      # Push a list in the range [1, (implicit) input-integer]
φ*    # Multiply each value by the golden ratio 1.618033988749895
i   # Floor each by casting it to an integer
╧  # Check if the (implicit) input-integer is in this list
# (after which the entire stack joined together is output implicitly as result)