Tout d'abord, parlons des séquences Beatty . Étant donné un nombre irrationnel positif r , nous pouvons construire une séquence infinie en multipliant les entiers positifs par r dans l'ordre et en prenant la parole de chaque calcul résultant. Par exemple,

Si r > 1, nous avons une condition spéciale. Nous pouvons former un autre nombre irrationnel s comme s = r / ( r - 1). Cela peut alors générer sa propre séquence Beatty, B _s . L'astuce est que B _r et B _s sont complémentaires , ce qui signifie que chaque entier positif se trouve exactement dans l'une des deux séquences.

Si nous fixons r = ϕ, le nombre d'or, alors nous obtenons s = r + 1 et deux séquences spéciales. La séquence Wythoff inférieure pour r :

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

et la séquence Wythoff supérieure pour s :

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

Il s'agit des séquences A000201 et A001950 sur OEIS, respectivement.

Le défi

Étant donné un entier d'entrée positif 1 <= n <= 1000, affichez l'une des deux valeurs distinctes indiquant si l'entrée se trouve dans la séquence Wythoff inférieure ou la séquence supérieure . Les valeurs de sortie peuvent être -1et 1, trueet false, upperet lower, etc.

Bien que votre algorithme soumis doive théoriquement fonctionner pour toutes les entrées, en pratique, il ne doit fonctionner qu'avec les 1000 premiers numéros d'entrée.

E / S et règles

• L'entrée et la sortie peuvent être fournies par n'importe quelle méthode pratique .
• L'entrée et la sortie peuvent être supposées correspondre au type de numéro natif de votre langue.
• Un programme complet ou une fonction sont acceptables. S'il s'agit d'une fonction, vous pouvez renvoyer la sortie plutôt que de l'imprimer.
• Les failles standard sont interdites.
• Il s'agit de code-golf, donc toutes les règles de golf habituelles s'appliquent et le code le plus court (en octets) gagne.

JavaScript (ES6), 50 35 octets

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>

Sorties 1pour inférieur et 0pour supérieur. Explication: Les listes partielles des valeurs booléennes peut être construit en utilisant une identité comme Fibonacci: étant donné deux listes, en commençant par 1et 10, chaque liste suivante est la concaténation des deux précédents, ce qui 101, 10110, 10110101etc. Dans ce cas , il est légèrement Golfier avoir une fausse 0e entrée 0et l'utiliser pour construire le deuxième élément de la liste.

Haskell , 26 octets

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

Essayez-le en ligne!

Pas de flotteurs, une précision illimitée. Merci pour H.PWiz pour deux octets.

Python , 25 octets

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

Essayez-le en ligne!

Utilise la condition très simple:

nest dans la séquence Wythoff inférieure exactement si -n%phi<1.

Notez que le résultat du modulo est positif même s'il -nest négatif, correspondant à la façon dont Python fait le modulo.

Preuve: Let a = -n%phi, qui se situe dans la plage 0 <= a < phi. Nous pouvons diviser le -nmodulo phicomme -n = -k*phi + apour un entier positif k. Réorganisez cela en n+a = k*phi.

Si a<1, alors n = floor(n+a) = floor(k*phi), et ainsi de suite dans la séquence inférieure de Wythoff.

Dans le cas contraire, nous avons 1 <= a < phidonc

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

ntombe donc dans l'écart entre floor((k-1)*phi)et floor(k*phi) et est manqué par la séquence inférieure de Wythoff.

Cela correspond à ce code:

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

Essayez-le en ligne!

Nous économisons un octet en doublant à -(n*2)%(phi*2)<2.

05AB1E , 9 octets

L5t>;*óså

Essayez-le en ligne!

0 signifie supérieur, 1 signifie inférieur. Essayez les 100 premiers: essayez-le en ligne!

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

Dump de commandes brutes:

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

Gelée , 5 octets

N%ØpỊ

Essayez-le en ligne!

1 octet enregistré grâce au golf Python de xnor .

Gelée , 6 octets

×€ØpḞċ

Essayez-le en ligne!

Renvoie 1 pour inférieur et 0 pour supérieur.

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

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

Essayez-le en ligne!

Ne produit rien pour le bas et 0pour le haut. Le passage à un schéma de sortie plus sensé coûterait 6 octets.

Python 2 , 39 33 32 octets

^{-6 octets grâce à M. Xcoder
-1 octet grâce à Zacharý}

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

Essayez-le en ligne!

Renvoie Falsepour inférieur et Truepour supérieur

Julia 0,6 , 16 octets

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

Essayez-le en ligne!

En jouant avec les chiffres, je suis tombé sur cette propriété: étage (n / φ) == étage ((n + 1) / φ) si n est dans la séquence Wythoff supérieure, et étage (n / φ) <étage ( (n + 1) / φ) si n est dans la séquence Wythoff inférieure. Je n'ai pas compris comment cette propriété se produit, mais elle donne les résultats corrects au moins jusqu'à n = 100000 (et probablement au-delà).

Ancienne réponse:

Julia 0,6 , 31 octets

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

Essayez-le en ligne!

Renvoie la séquence Wythoff trueinférieure et falsesupérieure.

Pyth , 8 octets

/sM*.n3S

Essayez-le ici!

Renvoie 1 pour inférieur et 0 pour supérieur.

Wolfram Language (Mathematica) , 26 octets

#~Ceiling~GoldenRatio<#+1&

Essayez-le en ligne!

Un entier nest dans la séquence Wythoff inférieure si ceil(n/phi) - 1/phi < n/phi.

La preuve c'est ceil(n/phi) - 1/phi < n/phi...

Suffisant:

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

2. Alors, ceil(n/phi) * phi < n + 1 .

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

4. Par conséquent, n <= ceil(n/phi) * phi < n + 1 .

5. Puisque net ceil(n/phi)sont des entiers, nous invoquons la définition de plancher et d'état floor(ceil(n/phi) * phi) == n, etn trouve dans la séquence Wythoff inférieure.

Nécessaire; preuve par contrapositive:

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

2. Alors, ceil(n/phi) * phi >= n + 1 .

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

4. Par conséquent n > (ceil(n/phi) - 1) * phi .

5. Puisque (ceil(n/phi) - 1) * phi < n < n + 1 <= ceil(n/phi) * phi, nn'est pas dans la séquence Wythoff inférieure.

Japt , 10 octets

Renvoie vrai pour inférieur et faux pour supérieur.

õ_*MQ fÃøU

Essayez-le en ligne!

Explication:

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

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

Port de @ Rod's Python 2 answer .
-1 octet grâce à @ Zacharý .

Essayez-le en ligne.

Ancien 77 76 octets réponse:

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

-1 octet grâce à @ovs 'pour quelque chose que je me suis recommandé la semaine dernière .. xD

Retourne 1pour plus bas; 0pour la tige.

Essayez-le en ligne.

Explication:

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*Phiest calculé en prenant (sqrt(5)+1)/2 * i, puis nous l'étageons en le convertissant en un entier pour tronquer la décimale.

Haskell , 153 139 126 79 bytes

Précision illimitée!

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

Essayez-le en ligne!

Explication

Au lieu d'utiliser une approximation du nombre d'or pour calculer le résultat, ils sont sujets à des erreurs lorsque la taille de l'entrée augmente. Cette réponse n'est pas. Au lieu de cela, il utilise la formule fournie sur l'OEIS qui aest la séquence unique telle que

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

où best le compliment ordonné.

Brachylog , 8 octets

≥ℕ;φ×⌋₁?

Essayez-le en ligne!

Le prédicat réussit si l'entrée se trouve dans la séquence Wythoff inférieure et échoue s'il se trouve dans la séquence Wythoff supérieure.

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

Si l'échec de la terminaison est une méthode de sortie valide, le premier octet peut être omis.

MATL , 8 octets

t:17L*km

Essayez-le en ligne!

Explication

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 octets

Solution:

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

Essayez-le en ligne!

Explication:

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 octets

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

L'entrée est en Ans.
La sortie est en cours Anset est automatiquement imprimée.
Imprime 1si l'entrée est dans la séquence inférieure ou 0si elle est dans la séquence supérieure.

$0<N<1000$ .

Exemple:

27
             27
prgmCDGFA
              1
44
             44
prgmCDGFA
              0

Explication:

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

Remarque: TI-BASIC est un langage à jetons. Le nombre de caractères n'est pas égal au nombre d'octets.

cQuents , 5 octets

?F$`g

Essayez-le en ligne!

Explication

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

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