Сначала поговорим о последовательностях Битти . Учитывая положительное иррациональное число r , мы можем построить бесконечную последовательность, умножив положительные целые числа на r по порядку и взяв слово для каждого полученного вычисления. Например,

Если r > 1, мы имеем специальное условие. Мы можем сформировать другое иррациональное число s как s = r / ( r - 1). Затем он может генерировать свою собственную последовательность Битти, B _s . Аккуратно фокус в том , что Б _г и Б _ы являются взаимодополняющими , а это означает , что каждое положительное целое число в точности одну из двух последовательностей.

Если мы установим r = ϕ, золотое сечение, то получим s = r + 1 и две специальные последовательности. Ниже последовательность Wythoff для г :

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

и верхняя последовательность Витоффа для s :

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

Это последовательности A000201 и A001950 в OEIS, соответственно.

Соревнование

Учитывая положительное входное целое число 1 <= n <= 1000, выведите одно из двух различных значений, указывающих, находится ли вход в нижней последовательности Wythoff или в верхней последовательности. Выходными значениями могут быть -1и 1, trueи false, upperи lower, и т. Д.

Хотя представленный алгоритм теоретически должен работать для всех входных данных, на практике он должен работать только с первыми 1000 входными числами.

I / O и правила

• Вход и выход могут быть заданы любым удобным способом .
• Можно предположить, что ввод и вывод соответствуют типу номера вашего языка.
• Либо полная программа или функция приемлемы. Если функция, вы можете вернуть вывод, а не распечатать его.
• Стандартные лазейки запрещены.
• Это код-гольф, поэтому применяются все обычные правила игры в гольф, и выигрывает самый короткий код (в байтах).

JavaScript (ES6), 50 35 байт

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>

Выходы 1для нижнего и 0верхнего. Объяснение: Частичные списки логических значений могут быть построены с использованием тождества, подобного Фибоначчи: с учетом двух списков, начиная с 1и 10, каждый последующий список является объединением двух предыдущих, приводя к 101, 10110и 10110101т. Д. В этом случае немного сложнее иметь фальшивая 0-я запись 0и использовать ее для создания второго элемента списка.

Haskell , 26 байтов

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

Попробуйте онлайн!

Нет поплавков, неограниченная точность. Спасибо за H.PWiz за два байта.

Python , 25 байт

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

Попробуйте онлайн!

Использует очень простое условие:

nнаходится в нижней последовательности Wythoff точно, если -n%phi<1.

Обратите внимание, что результат по модулю положительный, хотя -nи отрицательный, что соответствует Python по модулю.

Доказательство: пусть a = -n%phi, который лежит в диапазоне 0 <= a < phi. Мы можем разделить -nпо модулю phiкак -n = -k*phi + aдля некоторого натурального числа k. Переставь это на n+a = k*phi.

Если a<1, то n = floor(n+a) = floor(k*phi)и так в нижней последовательности Витоффа.

В противном случае у нас 1 <= a < phiтак

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

так nпадает в промежуток между floor((k-1)*phi)и floor(k*phi) и пропускается нижней последовательностью Витоффа.

Это соответствует этому коду:

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

Попробуйте онлайн!

Мы экономим байт, удваивая до -(n*2)%(phi*2)<2.

05AB1E , 9 байтов

L5t>;*óså

Попробуйте онлайн!

0 означает верхний, 1 означает нижний. Попробуйте первые 100: попробуйте онлайн!

    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]]

Необработанный командный дамп:

----------------------------------
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]

Желе , 5 байт

N%ØpỊ

Попробуйте онлайн!

Сохранено 1 байт благодаря гольфу xnor's Python .

Желе , 6 байт

×€ØpḞċ

Попробуйте онлайн!

Возвращает 1 для нижнего и 0 для верхнего.

×€Ø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.

$(0,\:N]\cap \mathbb{Z}$$\varphi > 1$$N > 0$$0 < N < N\varphi$

Brain-Flak , 78 байт

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

Попробуйте онлайн!

Ничего не выводит для нижнего и 0верхнего. Переход на более разумную схему вывода будет стоить 6 байт.

Python 2 , 39 33 32 байта

^{-6 байт благодаря г-ну Xcoder
-1 байт благодаря Захари}

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

Попробуйте онлайн!

Возвращает Falseдля нижнего и Trueверхнего

Юлия 0,6 , 16 байт

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

Попробуйте онлайн!

Играя с числами, я наткнулся на это свойство: floor (n / φ) == floor ((n + 1) / φ), если n находится в верхней последовательности Wythoff, и floor (n / φ) <floor ( (n + 1) / φ), если n находится в нижней последовательности Витоффа. Я не выяснил, как возникает это свойство, но оно дает правильные результаты, по крайней мере, до n = 100000 (и, вероятно, за его пределами).

Старый ответ:

Юлия 0,6 , 31 байт

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

Попробуйте онлайн!

Возвращает trueдля нижней и falseверхней последовательности Wythoff.

Pyth , 8 байт

/sM*.n3S

Попробуй это здесь!

Возвращает 1 для нижнего и 0 для верхнего.

Wolfram Language (Mathematica) , 26 байтов

#~Ceiling~GoldenRatio<#+1&

Попробуйте онлайн!

Целое число nнаходится в нижней последовательности Wythoff iff ceil(n/phi) - 1/phi < n/phi.

Доказательство того, что ceil(n/phi) - 1/phi < n/phi...

Достаточная:

1. Пусть ceil(n/phi) - 1/phi < n/phi.

2. Тогда ceil(n/phi) * phi < n + 1.

3. Примечание n == n/phi * phi <= ceil(n/phi) * phi.

4. Следовательно, n <= ceil(n/phi) * phi < n + 1.

5. Так как nи ceil(n/phi)являются целыми числами, мы вызываем определение floor и state floor(ceil(n/phi) * phi) == nи nнаходятся в нижней последовательности Wythoff.

Необходимо; доказательство контрацептивом:

1. Пусть ceil(n/phi) - 1/phi >= n/phi.

2. Тогда ceil(n/phi) * phi >= n + 1.

3. Заметка n + phi > (n/phi + 1) * phi > ceil(n/phi) * phi

4. Отсюда n > (ceil(n/phi) - 1) * phi.

5. Так как (ceil(n/phi) - 1) * phi < n < n + 1 <= ceil(n/phi) * phi, nне в нижней последовательности Wythoff.

Japt , 10 байт

Возвращает true для нижнего и false для верхнего.

õ_*MQ fÃøU

Попробуйте онлайн!

Объяснение:

õ_*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

Java 10, 77 53 52 байта

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

Порт @ Род Пита 2 ответ .
-1 байт благодаря @ Zacharý .

Попробуйте онлайн.

Старый 77 76 байт ответ:

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

-1 байт, спасибо @ovs 'за то, что я рекомендовал себе на прошлой неделе .. xD

Возврат 1за понижение; 0для верхнего.

Попробуйте онлайн.

Объяснение:

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вычисляется путем взятия (sqrt(5)+1)/2 * i, а затем мы помещаем его в пол, приводя его к целому числу, чтобы усечь десятичное число.

Хаскелл , 153 139 126 79 байтов

Неограниченная точность!

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

Попробуйте онлайн!

объяснение

Вместо того, чтобы использовать приближение золотого сечения для вычисления результата, это означает, что они подвержены ошибкам при увеличении размера входных данных. Этот ответ не дает. Вместо этого он использует формулу, представленную в OEIS, которая aявляется уникальной последовательностью, такой, что

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

где bзаказанный комплимент.

Брахилог , 8 байт

≥ℕ;φ×⌋₁?

Попробуйте онлайн!

Предикат успешно выполняется, если вход находится в нижней последовательности Wythoff, и не работает, если он находится в верхней последовательности Wythoff.

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

Если сбой завершения является допустимым методом вывода, первый байт может быть опущен.

MATL , 8 байт

t:17L*km

Попробуйте онлайн!

объяснение

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

К (ок) , 20 байтов

Решение:

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

Попробуйте онлайн!

Объяснение:

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?

TI-BASIC (TI-84), 18 байтов

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

Вход находится в Ans.
Выход находится Ansи автоматически распечатывается.
Печать1 если вход находится в нижней последовательности или 0если в верхней последовательности.

$0<N<1000$ .

Пример:

27
             27
prgmCDGFA
              1
44
             44
prgmCDGFA
              0

Объяснение:

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

Примечание: TI-BASIC - это токенизированный язык. Количество символов не равно количеству байтов.

cQuents , 5 байтов

?F$`g

Попробуйте онлайн!

объяснение

?         output true if in sequence, false if not in sequence
          each term in the sequence equals:

 F        floor (
  $               index * 
   `g                     golden ratio
     )                                 ) implicit