Primeiro, vamos falar sobre sequências Beatty . Dado um número irracional positivo r , podemos construir uma sequência infinita multiplicando os números inteiros positivos para r em ordem e tomando o piso de cada cálculo resultante. Por exemplo,

Se r > 1, temos uma condição especial. Podemos formar outro número irracional s como s = r / ( r - 1). Isso pode gerar sua própria sequência Beatty, B _s . O truque é que B _r e B _s são complementares , o que significa que todo número inteiro positivo está exatamente em uma das duas seqüências.

Se definirmos r = ϕ, a proporção áurea, obteremos s = r + 1 e duas seqüências especiais. o sequência Wythoff inferior para r :

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

e a sequência Wythoff superior para s :

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

Essas são as seqüências A000201 e A001950 no OEIS, respectivamente.

O desafio

Dado um número inteiro positivo, insira 1 <= n <= 1000um dos dois valores distintos indicando se a entrada está na sequência Wythoff inferior ou na sequência superior . Os valores de saída podem ser -1e 1, truee false, uppere lower, etc.

Embora o algoritmo enviado deva teoricamente funcionar para todas as entradas, na prática, ele só precisa funcionar com os primeiros 1000 números de entrada.

E / S e regras

• A entrada e saída podem ser fornecidas por qualquer método conveniente .
• Pode-se presumir que a entrada e a saída cabem no tipo de número nativo do seu idioma.
• Um programa completo ou uma função são aceitáveis. Se uma função, você pode retornar a saída em vez de imprimi-la.
• As brechas padrão são proibidas.
• Isso é código-golfe, portanto todas as regras usuais de golfe se aplicam e o código mais curto (em bytes) vence.

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>

Saídas 1para inferior e 0superior. Explicação: As listas parciais de valores booleanos pode ser construído usando uma Fibonacci semelhante de identidade: dado duas listas, começando com 1e 10, cada lista subsequente é a concatenação dos dois anteriores, resultando em 101, 10110, 10110101etc. Neste caso é ligeiramente Golfier ter uma 0ª entrada falsa 0e use-a para construir o segundo elemento da lista.

Haskell , 26 bytes

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

Experimente online!

Sem flutuadores, precisão ilimitada. Obrigado por H.PWiz por dois bytes.

Python , 25 bytes

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

Experimente online!

Usa a condição muito simples:

nestá na sequência Wythoff inferior exatamente se -n%phi<1.

Observe que o resultado do módulo é positivo, embora -nnegativo, correspondendo à forma como o Python faz o módulo.

Prova: Let a = -n%phi, que está no intervalo 0 <= a < phi. Podemos dividir o -nmódulo phiquanto -n = -k*phi + aa um número inteiro positivo k. Reorganize isso paran+a = k*phi .

Se a<1entãon = floor(n+a) = floor(k*phi) , e o mesmo estiver na sequência Wythoff inferior.

Caso contrário, temos 1 <= a < phiassim

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

assim ncai no hiato entre floor((k-1)*phi)e floor(k*phi) e é desperdiçada pela sequência Wythoff inferior.

Isso corresponde a este código:

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

Experimente online!

Salvamos um byte dobrando para -(n*2)%(phi*2)<2.

05AB1E , 9 bytes

L5t>;*óså

Experimente online!

0 significa superior, 1 significa inferior. Experimente os 100 primeiros: Experimente 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]]

Despejo de comando bruto:

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

Gelatina , 5 bytes

N%ØpỊ

Experimente online!

Economizou 1 byte graças ao golfe Python do xnor .

Gelatina , 6 bytes

×€ØpḞċ

Experimente online!

Retorna 1 para inferior e 0 para superior.

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

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

Experimente online!

Não produz nada para inferior e 0para superior. Mudar para um esquema de saída mais sensato custaria 6 bytes.

Python 2 , 39 33 32 bytes

^{-6 bytes graças ao Sr. Xcoder
-1 byte graças a Zacharý}

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

Experimente online!

Retorna Falsepara inferior e Truepara superior

Julia 0,6 , 16 bytes

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

Experimente online!

Enquanto brincava com os números, me deparei com essa propriedade: floor (n / φ) == floor ((n + 1) / φ) se n estiver na sequência Wythoff superior e floor (n / φ) <floor ( (n + 1) / φ) se n estiver na sequência Wythoff inferior. Ainda não descobri como essa propriedade ocorre, mas fornece os resultados corretos pelo menos até n = 100000 (e provavelmente além).

Resposta antiga:

Julia 0,6 , 31 bytes

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

Experimente online!

Retorna truepara a falsesequência Wythoff inferior e superior.

Pitão , 8 bytes

/sM*.n3S

Experimente aqui!

Retorna 1 para inferior e 0 para superior.

Wolfram Language (Mathematica) , 26 bytes

#~Ceiling~GoldenRatio<#+1&

Experimente online!

Um número inteiro nestá na sequência Wythoff inferior, se ceil(n/phi) - 1/phi < n/phi.

Prova de que ceil(n/phi) - 1/phi < n/phié ...

Suficiente:

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

2. Então ceil(n/phi) * phi < n + 1,.

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

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

5. Como ne ceil(n/phi)são números inteiros, chamamos a definição de piso e estado floor(ceil(n/phi) * phi) == ne nestá na sequência Wythoff inferior.

Necessário; prova por contrapositivo:

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

2. Então ceil(n/phi) * phi >= n + 1,.

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

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

5. Desde (ceil(n/phi) - 1) * phi < n < n + 1 <= ceil(n/phi) * phi, nnão está na seqüência Wythoff inferior.

Japonês , 10 bytes

Retorna verdadeiro para inferior e falso para superior.

õ_*MQ fÃøU

Experimente online!

Explicação:

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

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

Porto da resposta do @ Rod's Python 2 .
-1 byte graças a @ Zacharý .

Experimente online.

Resposta antiga 77 76 bytes:

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

-1 byte graças a @ovs 'por algo que eu me recomendei semana passada .. xD

Retorna 1para menor; 0para superior.

Experimente online.

Explicação:

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é calculado usando-se (sqrt(5)+1)/2 * i, e então o projetamos convertendo-o em um número inteiro para truncar o decimal.

Haskell , 153 139 126 79 bytes

Precisão ilimitada!

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

Experimente online!

Explicação

Em vez de usar uma aproximação da proporção áurea para calcular o resultado, eles são propensos a erros à medida que o tamanho da entrada aumenta. Esta resposta não. Em vez disso, usa a fórmula fornecida no OEIS quea é a sequência única, de modo que

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

Onde bestá o elogio ordenado.

Braquilog , 8 bytes

≥ℕ;φ×⌋₁?

Experimente online!

O predicado será bem-sucedido se a entrada estiver na sequência Wythoff inferior e falhará se estiver na sequência Wythoff superior.

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

Se a falha ao finalizar for um método de saída válido, o primeiro byte poderá ser omitido.

MATL , 8 bytes

t:17L*km

Experimente online!

Explicação

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

Solução:

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

Experimente online!

Explicação:

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 bytes

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

A entrada é no Ans.
A saída está dentro Anse é impressa automaticamente.
Imprime 1se a entrada estiver na sequência inferior ou 0se estiver na sequência superior.

Coincidentemente, este programa será executado apenas por $0<N<1000$ .

Exemplo:

27
             27
prgmCDGFA
              1
44
             44
prgmCDGFA
              0

Explicação:

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

Nota: TI-BASIC é um idioma tokenizado. Contagem de caracteres não é igual à contagem de bytes.

cQuents , 5 bytes

?F$`g

Experimente online!

Explicação

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

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