21

Considere la secuencia natural hasta 6 (ignore 1) :

2,3,4,5,6

Comenzamos a escanear desde la izquierda (en este caso desde 2), buscamos un número divisible por 2 (aquí 4) y luego eliminamos ambos números de la lista (aquí 2 y 4), de modo que la lista se reduce a:

3,5,6

Continuamos el mismo proceso, aquí el más a la izquierda es 3, por lo que buscamos un número divisible por 3. 6 es seguramente ese número y, por lo tanto, se eliminan 3 y 6,

Ahora, no se pueden realizar más búsquedas de este tipo. Por lo tanto, se convierte en la lista de números ALONED para n = 6.

OBJETIVO

Dado un número n mayor que 1, imprima todos los números alonados correspondientes.

ENTRADA

SALIDA

2
5
8,9,11,12,13,15
11,12,13,15,17,19,20
12,13,15,17,19,20,21

AÚN OTRO EJEMPLO RESUELTO

Para n = 22

=>2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22
=>3,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22 (remove 2 & 4)
=>5,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22 (remove 3 & 6)
=>7,8,9,11,12,13,14,15,16,17,18,19,20,21,22 (remove 5 & 10)
=>8,9,11,12,13,15,16,17,18,19,20,21,22 (remove 7 & 14)
=>9,11,12,13,15,17,18,19,20,21,22 (remove 8 & 16)
=>11,12,13,15,17,19,20,21,22 (remove 9 & 18)
=>12,13,15,17,19,20,21 (remove 11 & 22) (OUTPUT)

Este es el código de golf , por lo que gana el código más corto en bytes.

code-golf number officialaimm
fuente

77

Para que lo sepas, tenemos un sandbox donde puedes publicar desafíos incompletos para comentarios antes de publicarlos en el sitio principal.

DJMcMayhem

44

¿Tenemos que devolver una lista de los números en orden ascendente o también sería aceptable una lista no ordenada o un conjunto?

Dennis

debe estar en orden ascendente.

officialaimm

5

05AB1E , 22 17 15 14 bytes

L¦¹F¬·©¹›_i¦®K

Pruébalo en línea!

Explicación

L¦               # push the list [2..input]
  ¹F             # input nr of times do:
          i      # if
    ¬·©          # the first element in the list * 2
       ¹›_       # is less than or equal to input
                 # then
           ¦     # remove first element of list
            ®K   # and remove it's multiple

Emigna
fuente

6

Python 2, 90 79 73 bytes

^{-6 bytes gracias a xnor}

L=range(2,input()+1)
while L[0]*2<=L[-1]:L.remove(L[0]*2);L=L[1:]
print L

Toma el número de entrada en stdin. Ideone it!

Explicación

Construimos la lista inicial a partir del número de entrada y la almacenamos L. Luego, repita mientras el último número es mayor o igual a 2 veces el primer número y elimine 2 veces el primer número de la lista. Este siempre será el próximo número divisible por L[0]. L=L[1:]saca el primer número también. Cuando la condición ya no es verdadera, no se pueden realizar más eliminaciones y se imprime la lista.

DLosc
fuente

En Python 2, rangeya da una lista.

xnor

@xnor Gracias! Olvidé eso.

DLosc

5

Python, 61 bytes

lambda n:[i+1for i in range(n/2,n)if-~i&~i&4**n/3>>(-~i&i<1)]

Es un poco más fácil entender este código menos golfizado:

lambda n:[i for i in range(n/2+1,n+1)if((i&-i)**.5%1>0)^(i&~-i>0)]

Esto utiliza una caracterización directa de números alonados:

Un número ise aloned si, cuando se descompone como i = a * 2^bcon bimpar, ya sea

a>1y bes par, o

a==1y bes extraño

Los números alonados nson todos los números alonados ien el intervalo n/2 + 1 <= i <= n.

¿Por qué se sostiene esto? Al hacer el proceso para n, digamos que eliminamos un número impar aen la mitad inferior ( 1a n/2). Luego, 2*ase elimina sin importar en qué parte de la lista se encuentre. Entonces, 4*apermanece (si existió). Pero si está en la mitad inferior, el proceso de eliminación llegará y eliminará ambos 4*ay 8*a. Por lo tanto, vemos que un número medio superior se retira si es de la forma 2*a, 8*a... con extraña c, pero estancias si tiene forma a, 4*a, 8*a, ...

La excepción es for a=1, que no comienza en la lista y, por lo tanto, no se elimina. Como resultado, la cadena de eliminación comienza a=2y la regla para potencias de 2 se cambia.

lambda n:[i for i in range(n/2+1,n+1)if((i&-i)**.5%1>0)^(i&~-i>0)]

En el código anterior, (i&-i)**.5%1>0verifica si icarece de la forma i = a * 2^bcon bimpar, por el truco de bits para extraer el mayor factor de potencia de dos, 2^b = i&-iy luego verifica si el resultado no es un cuadrado perfecto. Entonces, i&~-i>0es otro truco para comprobar si ino es una potencia perfecta de 2. Estas condiciones se corrigen.

Hay algunas mejoras más aquí

lambda n:[i+1for i in range(n/2,n)if-~i&~i&4**n/3>>(-~i&i<1)]

Primero, cambiamos el índice del rango 1 hacia abajo para acortar a range(n/2,n)desde range(n/2+1,n+1), compensando reemplazando todo icon i+1(o ~-i).

Ya sea una potencia de 2 es el número es una potencia de 4(2 ^ bcon el bpar) se puede comprobar y-ción con 2**c/3algún grande c. Esto se debe a que 2**c/3tiene una representación binaria 10101...101con unos en los bits de posición par. Usando c=2*nsuficientes. Para negar el resultado cuando ies una potencia de 2, reducimos a la mitad este número en ese caso, colocando 1las posiciones impares en su lugar.

xnor
fuente

4

Groovy, 65 58 Bytes

Idea de algoritmo de DSLoc , que notó que solo necesita eliminar los dobles.

{n->a=(2..n);(2..(n/2)).each{if(it in a){a-=[it,it*2]}};a}

Aquí hay un desglose:

{
    n->
    a=(2..n);             // Store [2,...,n].
    (2..(n/2)).each {     // From 2 to half of n.
        if(it in a){      // If it's there...
            a-=[it,it*2]  // Remove it and its double, store in a.
        }
    };
    a                     // Return a.
}

Urna de pulpo mágico
fuente

4

Perl, 53 49 45 44 bytes

Incluye +1 para -n

Dé el número de entrada en STDIN:

perl -M5.010 aloned.pl <<< 22

aloned.pl:

#!/usr/bin/perl -n
@F[$F[$_*2]/2,$_*2,1]=0,$_&&say for@F=0..$_

Verificar directamente los números posibles es más largo:

map{/$/;$_/=4until$_%4;$_%2^$_<3&&say$`}$_/2+1..$_

Esto verifica todos los números en el rango medio superior. Mantenga los números que tienen un número par de 2 como factores primos, excepto si el número es una potencia de 2 y luego impar (porque 1 queda fuera de la serie original). Sin embargo, este método debería funcionar bien para otros idiomas.

Ton Hospel
fuente

3

MATL , 18 bytes

Tomó prestada la idea de "multiplicar por 2" de la respuesta 05AB1E de @ Emigna .

q:Qt"t1)tEhym?6MX-

Pruébalo en línea!

Explicación

q:Q        % Input n implicitly. Push [2 3 ... n]
t"         % Duplicate. For each: repeat n-1 times
  t1)      %   Duplicate. Get first element from current array, say k
  tEh      %   Append twice that value: gives array [k 2*k]
  y        %   Push another copy of current array
  m?       %   If both k and 2*k are members of the array 
    6M     %     Push [k 2*k] again
     X-    %     Set difference: remove from current array
           %   End if implicitly
           % End for each implicitly
           % Display implicitly

Luis Mendo
fuente

Solo necesita verificar si k es un miembro, no sé si eso le ahorra bytes o no.

Urna mágica de pulpo

@carusocomputing ¡Gracias! Inicialmente verifiqué solo 2 * k (si eso es lo que quieres decir). Luego agregué k allí porque más tarde reutilizo esa matriz de dos elementos para eliminar ambos de la matriz general

Luis Mendo

3

Haskell, 71 69 62 56 bytes

g(a:b)|s<-filter(/=2*a)b=[a|s==b]++g s
g x=x
q n=g[2..n]

Ejemplo de uso: q 22-> [12,13,15,17,19,20,21].

Si hay un múltiplo del primer número a, entonces es 2*a. Mantener asi 2*ano está en la lista y agregar una llamada recursiva con ay 2*aeliminado de la lista.

nimi
fuente

Jeje, iba a decirte que GCD era excesivo, pero lo conseguiste tú mismo.

Urna mágica de pulpo

2

Pyth - 19 bytes

Será sin duda ser refactorización.

u?Kf!%ThGtG-tGhKGtS

Test Suite .

Maltysen
fuente

2

Rubí, 124

Comparando puntajes con otras respuestas, este es obviamente el enfoque equivocado:

->n{a={};b=[*2..n].each{|k|a[k]=7}
b.map{|i|g=b.select{|x|a[i]&&a[x]&&x%i<1}
a[g[0]]=a[g[1]]=!g[1]}
a.select{|k,v|v&k}.keys}

El bit algo inteligente aquí es el a[g[0]]=a[g[1]]=!g[1]que establece los valores de hash en verdadero / falso según sea necesario.

No es que Charles
fuente

2

PHP, 98 bytes

foreach($r=range(2,$argv[1])as$v)$a=&$r[$v-2]&&$b=&$r[$v*2-2]?$b=$a="":(!$a?:print$x?",$a":$x=$a);

8 Bytes guardados por @Titus Gracias

Si se permite una coma final, se puede acortar 9 bytes en (!$a?:print"$a,");lugar de(!$a?:print$x?",$a":$x=$a);

Jörg Hülsermann
fuente

¿Las tareas $ay no $bnecesitan paréntesis? ¡Malvado!

Titus

-1 byte con la coma final: (!$a?:print"$a,")-> print$a?"$a,":"". -2 bytes para ambas versiones si usa el guión bajo como separador.

Titus

-2 Bytes: foreach(... as$v), $v-2en lugar de $ky $v*2-2en lugar de $k*2+2.

Titus

@Titus Lo he probado después de que tu comentario $a=&$r[$k]&&$b=&$r[$k*2+2]funcione como $a=$r[$k]and$b=$r[$k*2+2]. Lamento no haber encontrado ninguna página que explique las combinaciones con las referencias y el &&operador. Pero necesito referencias, no asignaciones. No estoy seguro de si se permite una coma final u otro separador.

Jörg Hülsermann

@Titus lo encontró ahora php.net/manual/en/language.operators.precedence.php & bitwise y las referencias tienen una precedencia más alta que el &&operador

Jörg Hülsermann

1

Javascript, 149 bytes

function a(n){o=Array.from(Array((n+1)).keys());o.shift();o.shift();for(i=1;i<o.length;i++){if(o[i]%o[0]==0){o.splice(i,1);o.shift();i=0;}}return o;}

Aquí hay un ejemplo de trabajo. Todo el HTML y la función wrapper () son solo interactivos.

Mostrar fragmento de código

<!DOCTYPE html>
<html lang="en">
  <head>
<meta charset="UTF-8">
<title>Aloned</title>
<script>
  function wrapper(){document.getElementById("o").innerHTML = a(parseInt(document.getElementById("i").value));}
  function a(n){o=Array.from(Array((n+1)).keys());o.shift();o.shift();for(i=1;i<o.length;i++){if(o[i]%o[0]==0){o.splice(i,1);o.shift();i=0;}}return o;}
</script>
  </head>
  <body>
<p>Enter an integer:</p>
<p><input type="text" id="i" value="5" /></p>
<p><input type="button" value="Alone It!" onclick="wrapper()" /></p>
<div id="o"></div>
  </body>
</html>

Expandir fragmento

Este fragmento de código no protegido tiene algunos comentarios y le permite ver interactivamente los pasos para cualquier entrada dada.

Mostrar fragmento de código

<!DOCTYPE html>
<html lang="en">
  <head>
<meta charset="UTF-8">
<title>Aloned</title>
<script>
  function wrapper()
  {
    document.getElementById("o").innerHTML = aloned(parseInt(document.getElementById("i").value));
  }
  function aloned(n)
  {
    // From nils peterson's comment on benmcdonald's answer
    // http://stackoverflow.com/questions/3895478
    // Creates an array from 0 to n.
    o=Array.from(Array((n+1)).keys());
    
    // Remove 0 and 1 from the start of the array.
    o.shift();
    o.shift();
    
    // s and t are just used to display the output each iteration.
    var s = String(o);
    
    // Go through every item in the array (except the first).
    for(i = 1; i < o.length; i++)
    {
      // Check for an item evenly divisible by the first item.
      if (o[i]%o[0]==0)
      {
        var t=" (remove "+o[0]+" and "+o[i]+")";
        
        // Splice removes the current item, shift removes the first item.
        o.splice(i,1);
        o.shift();
        
        // Reset the array, so we're looping from the beginning again.
        i=0;
        
        s = s + "<br />" + String(o) + t;
      }
    }
    return s + " (OUTPUT)";
  }
</script>
  </head>
  <body>
<p>Enter an integer:</p>
<p><input type="text" id="i" value="5" /></p>
<p><input type="button" value="Alone It!" onclick="wrapper()" /></p>
<div id="o"></div>
  </body>
</html>

Expandir fragmento

MichaelS
fuente

1

JavaScript (ES6), 92 bytes

f=(n,R=[...Array(n-1)].map((_,i)=>i+2),[i,...r]=R)=>~r.indexOf(i*=2)?f(n,r.filter(x=>x-i)):R

Pensé que había publicado esto ayer, pero obviamente no ...

Aquí hay otra versión:

f=(n,R=[...Array(n-1)].map((_,i)=>i+2),[i,...r]=R,q=r.filter(x=>x-i*2))=>q+""!=r+""?f(n,q):R

ETHproducciones
fuente

1

Java 7, 210 bytes

import java.util.*;List c(int n){List<Integer>l=new ArrayList();int i=1;for(;i++<n;l.add(i));for(i=1;i++<n;)for(int x:l)if(i!=x&x%i<1&l.indexOf(i)>=0){l.remove((Integer)i);l.remove((Integer)x);break;}return l;}

Definitivamente se puede jugar un poco más usando un enfoque diferente, probablemente usando una matriz con algunos trucos. Debido al reparto, la interrupción, la lista de tipos y las comprobaciones de if es un poco más larga de lo esperado, pero funciona.

Ungolfed y código de prueba:

Pruébalo aquí

import java.util.*;
class M{
  static List c(int n){
    List<Integer> l = new ArrayList();
    int i = 1;
    for(; i++ < n; l.add(i));
    for(i = 1; i++ < n;){
      for(int x : l){
        if(i != x & x%i < 1 & l.indexOf(i) >= 0){
          l.remove((Integer)i);
          l.remove((Integer)x);
          break;
        }
      }
    }
    return l;
  }

  public static void main(String[] a){
    System.out.println(Arrays.toString(c(2).toArray()));
    System.out.println(Arrays.toString(c(6).toArray()));
    System.out.println(Arrays.toString(c(15).toArray()));
    System.out.println(Arrays.toString(c(20).toArray()));
    System.out.println(Arrays.toString(c(22).toArray()));
  }
}

Salida:

[2]
[5]
[8, 9, 11, 12, 13, 15]
[11, 12, 13, 15, 17, 19, 20]
[12, 13, 15, 17, 19, 20, 21]

Kevin Cruijssen
fuente

1

Raqueta 191 bytes

(let loop((fl(range 2(add1 n)))(fg #f))(define i(first fl))(for((j(rest fl))
#:when(= 0(modulo j i))#:final(= 0(modulo j i)))
(set! fl(remove*(list i j)fl))(set! fg #t))(if fg(loop fl #f)fl))

Ungolfed (comentarios después de ';'):

(define (f n)
  (let loop ((fl (range 2 (add1 n)))  ; create a full list of numbers
             (fg #f))                 ; flag to show if main list is modified
    (define i (first fl))
    (for ((j (rest fl)) #:when (= 0 (modulo j i))  ; test divisibility
                        #:final (= 0 (modulo j i)))
      (set! fl (remove* (list i j) fl))  ; remove these from main list
      (set! fg #t))
    (if fg (loop fl #f)              ; if main list modified, check again,
        fl)))                         ; else print modified list.

Pruebas:

(f 2)
(f 6)
(f 15)
(f 20)
(f 22)

Salida:

'(2)
'(5)
'(8 9 11 12 13 15)
'(11 12 13 15 17 19 20)
'(12 13 15 17 19 20 21)

rnso
fuente

Salida de los números ALONED

Respuestas:

05AB1E , 22 17 15 14 bytes

Python 2, 90 79 73 bytes

Explicación

Python, 61 bytes

Groovy, 65 58 Bytes

Perl, 53 49 45 44 bytes

MATL , 18 bytes

Explicación

Haskell, 71 69 62 56 bytes

Pyth - 19 bytes

Rubí, 124

PHP, 98 bytes

Javascript, 149 bytes

JavaScript (ES6), 92 bytes

Java 7, 210 bytes

Raqueta 191 bytes