25
\$\begingroup\$

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,
Beatty sequence of r

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.
Improve this question
\$\endgroup\$
1
  • 1
    \$\begingroup\$ It's basically "golf the lower Wythoff sequence" because the upper Wythoff sequence requires 1 more op than the lower one (squaring phi). \$\endgroup\$
    – Magic Octopus Urn
    Jun 15, 2018 at 13:28

21 Answers 21

Reset to default
13
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
3
  • 4
    \$\begingroup\$ How the what... \$\endgroup\$
    – AdmBorkBork
    Jun 15, 2018 at 13:52
  • 5
    \$\begingroup\$ 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. \$\endgroup\$
    – Magic Octopus Urn
    Jun 15, 2018 at 14:10
  • \$\begingroup\$ 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. \$\endgroup\$
    – Arnauld
    Jun 15, 2018 at 15:18
9
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ Could you explain how the formula comes about? I tried to derive it from the sequence definitions, but got lost in the woods. \$\endgroup\$
    – Sundar R
    Jun 15, 2018 at 19:19
  • \$\begingroup\$ @sundar Added a proof. \$\endgroup\$
    – xnor
    Jun 15, 2018 at 23:18
  • \$\begingroup\$ This exact same technique works in Ruby and JavaScript (at least), too \$\endgroup\$
    – pxeger
    Aug 23, 2020 at 12:15
7
\$\begingroup\$

Haskell, 26 bytes

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

Try it online!

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

Improve this answer
\$\endgroup\$
4
  • \$\begingroup\$ This would also be 26 bytes, but I don't understand why it doesn't work \$\endgroup\$
    – H.PWiz
    Jun 15, 2018 at 21:44
  • \$\begingroup\$ @H.PWiz I think it's because the empty list is a fixed point. \$\endgroup\$
    – xnor
    Jun 15, 2018 at 21:50
  • \$\begingroup\$ Ah, I hadn't considered that, and was comparing it with an "equivalent" method that used ~(x:t). Thanks \$\endgroup\$
    – H.PWiz
    Jun 15, 2018 at 21:52
  • \$\begingroup\$ @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. \$\endgroup\$
    – Ørjan Johansen
    Jun 17, 2018 at 15:25
5
\$\begingroup\$

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?        # [[1]]

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

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\$.

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ I'm guessing one of those is a 1-byte constant for phi :P? \$\endgroup\$
    – Magic Octopus Urn
    Jun 15, 2018 at 13:36
  • 2
    \$\begingroup\$ Nope, a two-byte one: Øp \$\endgroup\$
    – Mr. Xcoder
    Jun 15, 2018 at 13:36
  • \$\begingroup\$ Hehe, better than my 4-byte one in 05AB1E: 5t>; \$\endgroup\$
    – Magic Octopus Urn
    Jun 15, 2018 at 13:38
4
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
4
\$\begingroup\$

Python 2, 39 33 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

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ lambda n,r=(1+5**.5)/2:-~n//r<n/r saves 6 bytes. \$\endgroup\$
    – Mr. Xcoder
    Jun 15, 2018 at 13:58
  • 1
    \$\begingroup\$ Also, lambda n,r=.5+5**.5/2:-~n//r<n/r should work as well to shave one byte \$\endgroup\$
    – Adalynn
    Jun 15, 2018 at 17:56
3
\$\begingroup\$

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).

Old answer:

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.

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ 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. \$\endgroup\$
    – Neil
    Jun 16, 2018 at 18:10
3
\$\begingroup\$

Arn, 9 bytes

2>6Yx!¦ü#

Try it!

Explained

Unpacked: phi-1<%phi

I found another way of calculating this:

n % phi > phi + 1
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

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ Please do add in a link to your language's online intepreter. Would be helpful for checking the solution. \$\endgroup\$
    – Razetime
    Aug 24, 2020 at 2:27
  • \$\begingroup\$ Yeah sorry, I posted this before I made an online interpreter. A link has been added \$\endgroup\$
    – ZippyMagician
    Aug 24, 2020 at 12:43
  • \$\begingroup\$ Great to know! Nice answer. \$\endgroup\$
    – Razetime
    Aug 24, 2020 at 12:53
2
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ This also doesn't have any rounding error. \$\endgroup\$
    – DELETE_ME
    Jun 15, 2018 at 14:41
2
+100
\$\begingroup\$

APL (Dyalog Extended), 21 19 13 bytes

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

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

Try it online!

Old answer:

{⍵∊⌊((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!

Improve this answer
\$\endgroup\$
4
  • 1
    \$\begingroup\$ -2 bytes \$\endgroup\$
    – ZippyMagician
    Aug 22, 2020 at 19:53
  • \$\begingroup\$ I'll keep that snippet somewhere, thanks! \$\endgroup\$
    – Razetime
    Aug 31, 2020 at 10:53
  • \$\begingroup\$ 13 bytes: ⊢∊∘⌊⍳×1+∘÷⍣=≢ Try it online! \$\endgroup\$
    – Adám
    Aug 31, 2020 at 16:40
  • \$\begingroup\$ I should get a lot more experience with trains and tacit functions. \$\endgroup\$
    – Razetime
    Aug 31, 2020 at 16:46
1
\$\begingroup\$

Pyth, 8 bytes

/sM*.n3S

Try it here!

Returns 1 for lower and 0 for upper.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
1
  • 1
    \$\begingroup\$ I had this for 10 bytes too. \$\endgroup\$
    – Shaggy
    Jun 15, 2018 at 16:14
1
\$\begingroup\$

Java 10, 77 53 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.

Old 77 76 bytes answer:

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.

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

Haskell, 153 139 126 79 bytes

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.

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

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.

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ This is probably the very first time φ is used in a Brachylog program. At long last! \$\endgroup\$
    – Fatalize
    Mar 29, 2019 at 8:27
1
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

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
               1+    / add 1
              *      / multiply by
     (       )       / do this together
           %5        / square-root of 5
         1+          / add 1
      .5*            / multiply by .5
    _                / floor
x in                 / is input in this list?
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

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<N<1000\$ .

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.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

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)
Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.