20
\$\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.
\$\endgroup\$
  • 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 '18 at 13:28

18 Answers 18

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

\$\endgroup\$
  • 4
    \$\begingroup\$ How the what... \$\endgroup\$ – AdmBorkBork Jun 15 '18 at 13:52
  • 4
    \$\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 '18 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 '18 at 15:18
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.

\$\endgroup\$
  • \$\begingroup\$ This would also be 26 bytes, but I don't understand why it doesn't work \$\endgroup\$ – H.PWiz Jun 15 '18 at 21:44
  • \$\begingroup\$ @H.PWiz I think it's because the empty list is a fixed point. \$\endgroup\$ – xnor Jun 15 '18 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 '18 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 '18 at 15:25
7
\$\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.

\$\endgroup\$
  • \$\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 Jun 15 '18 at 19:19
  • \$\begingroup\$ @sundar Added a proof. \$\endgroup\$ – xnor Jun 15 '18 at 23:18
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]
\$\endgroup\$
  • \$\begingroup\$ I had the same, but using ï :) \$\endgroup\$ – Emigna Jun 15 '18 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 '18 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 '18 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 '18 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 '18 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\$.

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

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

\$\endgroup\$
  • \$\begingroup\$ lambda n,r=(1+5**.5)/2:-~n//r<n/r saves 6 bytes. \$\endgroup\$ – Mr. Xcoder Jun 15 '18 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\$ – Zacharý Jun 15 '18 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.

\$\endgroup\$
  • \$\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 '18 at 18:10
1
\$\begingroup\$

Pyth, 8 bytes

/sM*.n3S

Try it here!

Returns 1 for lower and 0 for upper.

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

\$\endgroup\$
  • \$\begingroup\$ This also doesn't have any rounding error. \$\endgroup\$ – user202729 Jun 15 '18 at 14:41
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
\$\endgroup\$
  • 1
    \$\begingroup\$ I had this for 10 bytes too. \$\endgroup\$ – Shaggy Jun 15 '18 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.

\$\endgroup\$
  • 1
    \$\begingroup\$ ++i<=n on your old answer can be i++<n. \$\endgroup\$ – ovs Jun 15 '18 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 '18 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\$ – Zacharý Jun 15 '18 at 17:53
  • \$\begingroup\$ @Zacharý It indeed does, thanks! \$\endgroup\$ – Kevin Cruijssen Jun 15 '18 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.

\$\endgroup\$
  • 1
    \$\begingroup\$ "All" wasn't even true before you got outgolfed... \$\endgroup\$ – Neil Jun 16 '18 at 13:36
  • \$\begingroup\$ @Neil Good point. I must have missed your answer. \$\endgroup\$ – Sriotchilism O'Zaic Jun 16 '18 at 14:35
  • \$\begingroup\$ Although your answer is limited by the fact that javascript doesn't have an integral type? \$\endgroup\$ – Sriotchilism O'Zaic Jun 16 '18 at 14:37
  • \$\begingroup\$ Well, it will run out of memory well before then... \$\endgroup\$ – Neil Jun 16 '18 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.

\$\endgroup\$
  • \$\begingroup\$ This is probably the very first time φ is used in a Brachylog program. At long last! \$\endgroup\$ – Fatalize Mar 29 at 8:27
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
\$\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?
\$\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.

\$\endgroup\$
0
\$\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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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