Upper or Lower Wythoff?

20

1

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.

AdmBorkBork

Posted 2018-06-15T13:18:13.073

Reputation: 41 581

1It's basically "golf the lower Wythoff sequence" because the upper Wythoff sequence requires 1 more op than the lower one (squaring phi). – Magic Octopus Urn – 2018-06-15T13:28:13.033

Answers

12

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.

Neil

Posted 2018-06-15T13:18:13.073

Reputation: 95 035

4How the what... – AdmBorkBork – 2018-06-15T13:52:20.470

4I 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. – Magic Octopus Urn – 2018-06-15T14:10:30.037

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.

– Arnauld – 2018-06-15T15:18:07.313

7

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.

xnor

Posted 2018-06-15T13:18:13.073

Reputation: 115 687

Could you explain how the formula comes about? I tried to derive it from the sequence definitions, but got lost in the woods. – sundar - Reinstate Monica – 2018-06-15T19:19:18.117

@sundar Added a proof. – xnor – 2018-06-15T23:18:01.437

7

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.

xnor

Posted 2018-06-15T13:18:13.073

Reputation: 115 687

This would also be 26 bytes, but I don't understand why it doesn't work – H.PWiz – 2018-06-15T21:44:07.603

@H.PWiz I think it's because the empty list is a fixed point. – xnor – 2018-06-15T21:50:27.847

Ah, I hadn't considered that, and was comparing it with an "equivalent" method that used ~(x:t). Thanks – H.PWiz – 2018-06-15T21:52:05.863

@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. – Ørjan Johansen – 2018-06-17T15:25:08.187

5

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]

Magic Octopus Urn

Posted 2018-06-15T13:18:13.073

Reputation: 19 422

I had the same, but using ï :) – Emigna – 2018-06-15T13:34:14.463

@emigna I was surprised phi wasn't in the mathematical constants. 5t>; to a 2 byter may not be worth it though... – Magic Octopus Urn – 2018-06-15T13:34:47.753

Yeah, I was half-remembering that it might have been (but it's not). It seems like something we should add. – Emigna – 2018-06-15T13:36:03.310

@Emigna I'm fairly certain the Jelly answer is legitimately this but with a phi built-in hahah. – Magic Octopus Urn – 2018-06-15T13:37:04.163

Haha I had the same but using ï and ¢ lol :) All our solutions are so closely related – Mr. Xcoder – 2018-06-15T13:40:04.497

Would you please decompose and explain your solution? – Jeff Zeitlin – 2018-06-15T13:57:43.057

@JeffZeitlin done. P.S. adding an argument to any 05AB1E answer -d will result in the debug dump; this is essentially a decomposition of any answer.

– Magic Octopus Urn – 2018-06-15T14:08:46.153

"Try the first 100" the first 99 actually. The G should be ƒ in the header of TIO. ;) – Kevin Cruijssen – 2018-06-15T18:09:35.490

5

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

Mr. Xcoder

Posted 2018-06-15T13:18:13.073

Reputation: 39 774

I'm guessing one of those is a 1-byte constant for phi :P? – Magic Octopus Urn – 2018-06-15T13:36:37.097

2Nope, a two-byte one: Øp – Mr. Xcoder – 2018-06-15T13:36:55.010

Hehe, better than my 4-byte one in 05AB1E: 5t>; – Magic Octopus Urn – 2018-06-15T13:38:04.487

4

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

Rod

Posted 2018-06-15T13:18:13.073

Reputation: 17 588

lambda n,r=(1+5**.5)/2:-~n//r<n/r saves 6 bytes. – Mr. Xcoder – 2018-06-15T13:58:52.350

1Also, lambda n,r=.5+5**.5/2:-~n//r<n/r should work as well to shave one byte – Zacharý – 2018-06-15T17:56:28.753

4

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.

Nitrodon

Posted 2018-06-15T13:18:13.073

Reputation: 9 181

3

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.

sundar - Reinstate Monica

Posted 2018-06-15T13:18:13.073

Reputation: 5 296

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 – 2018-06-16T18:10:07.793

1

Pyth, 8 bytes

/sM*.n3S

Try it here!

Returns 1 for lower and 0 for upper.

Mr. Xcoder

Posted 2018-06-15T13:18:13.073

Reputation: 39 774

1

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.

Kevin Cruijssen

Posted 2018-06-15T13:18:13.073

Reputation: 67 575

1++i<=n on your old answer can be i++<n. – ovs – 2018-06-15T14:28:05.440

1

@ovs of course.. >.< I actually recommended this golf to someone else last week, lol.. Thanks.

– Kevin Cruijssen – 2018-06-15T14:31:44.953

1I think this should work for -1 byte:n->{var r=Math.sqrt(5)/2+.5;return(int)(-~n/r)<n/r;} – Zacharý – 2018-06-15T17:53:33.833

@Zacharý It indeed does, thanks! – Kevin Cruijssen – 2018-06-15T18:04:08.750

1

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.

JungHwan Min

Posted 2018-06-15T13:18:13.073

Reputation: 13 290

This also doesn't have any rounding error. – user202729 – 2018-06-15T14:41:26.940

1

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

Oliver

Posted 2018-06-15T13:18:13.073

Reputation: 7 160

1

I had this for 10 bytes too.

– Shaggy – 2018-06-15T16:14:57.003

1

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.

Post Rock Garf Hunter

Posted 2018-06-15T13:18:13.073

Reputation: 55 382

1"All" wasn't even true before you got outgolfed... – Neil – 2018-06-16T13:36:00.420

@Neil Good point. I must have missed your answer. – Post Rock Garf Hunter – 2018-06-16T14:35:50.540

Although your answer is limited by the fact that javascript doesn't have an integral type? – Post Rock Garf Hunter – 2018-06-16T14:37:05.543

Well, it will run out of memory well before then... – Neil – 2018-06-16T17:59:23.663

1

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.

Unrelated String

Posted 2018-06-15T13:18:13.073

Reputation: 5 300

This is probably the very first time φ is used in a Brachylog program. At long last! – Fatalize – 2019-03-29T08:27:22.147

0

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

Luis Mendo

Posted 2018-06-15T13:18:13.073

Reputation: 87 464

0

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?

streetster

Posted 2018-06-15T13:18:13.073

Reputation: 3 635

0

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.

Tau

Posted 2018-06-15T13:18:13.073

Reputation: 1 935

0

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

Stephen

Posted 2018-06-15T13:18:13.073

Reputation: 12 293

Asked: 2018-06-15T13:18:13.073

Viewed: 2 227 times

Active: 2019-03-29T17:21:02.693