Output the ALONED numbers

Question

Consider the natural sequence up-to 6 (disregard 1):

2,3,4,5,6

We start scanning from the left (in this case from 2), search for a number divisible by 2 (here 4) and then remove both the numbers from the list (here 2 & 4), such that the list reduces to:

3,5,6

We continue the same process, here leftmost is 3, so we search for number divisible by 3. 6 is surely that number and thus 3 and 6 are removed,

5 

Now, no further such searches can be made Thus, this becomes the list of ALONED numbers for n=6.

OBJECTIVE

1. Given a number n greater than 1, print all the corresponding aloned numbers.

INPUT

2
6
15
20
22

OUTPUT

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

YET ANOTHER WORKED OUT EXAMPLE

For 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)

This is code-golf, so the shortest code in bytes wins.

Answer 1

Python 2, 90 79 73 bytes

^{-6 bytes thanks to xnor}

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

Takes the input number on stdin. Ideone it!

Explanation

We construct the initial list from the input number and store it in L. Next, loop while the last number is greater than or equal to 2 times the first number and remove 2 times the first number from the list. This will always be the next number divisible by L[0]. L=L[1:] takes off the first number as well. When the condition is no longer true, no further removals can be made, and the list is printed.

Answer 2

05AB1E, 22 17 15 14 bytes

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

Try it online!

Explanation

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

Answer 3

Python, 61 bytes

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

It's a bit easier to understand this less golfed code:

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

This uses a direct characterization of aloned numbers:

A number i is aloned if, when decomposed as i = a * 2^b with b odd, either

• a>1 and b is even, or
• a==1 and b is odd

The aloned numbers for n are all aloned numbers i in the interval n/2 + 1 <= i <= n.

Why does this hold? When doing the process for n, say we remove an odd number a in the lower half (1 to n/2). Then, 2*a is removed no matter where in the list it is. So, 4*a remains (if it existed). But if it's in the lower half, the deletion process will get to it and remove both 4*a and 8*a. So, we see that an upper-half number gets removed if it's of form 2*a, 8*a ... with odd c, but stays if it has form a, 4*a, 8*a, ...

The exception is for a=1, which does not start in the list and so is not removed. As a result, the removal chain starts with a=2, and the rule for powers of 2 is flipped.

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

In the code above, (i&-i)**.5%1>0 checks whether i lacks the form i = a * 2^b with b odd, by the bit-trick to extract the greatest power-of-two factor, 2^b = i&-i, then checking if the result is not a perfect square. Then, i&~-i>0 is another bit trick to check if i is not a perfect power of 2. These conditions are then xor'ed.

There's some more improvements here

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

First, we shift the range 1 index down to to shorten to range(n/2,n) from range(n/2+1,n+1), compensating by replacing all i with i+1 (or ~-i).

Whether a power of 2 is number is a power of 4 (2^b with b even) can be checked by and-ing with 2**c/3 for some large c. This is because 2**c/3 has binary representation 10101...101 with ones in the even-positioned bits. Using c=2*n suffices. To negate result when i is a power of 2, we halve this number is that case, putting 1's in the odd positions instead.

Answer 4

Groovy, 65 58 Bytes

Algorithm idea from DSLoc, who noticed you need only to remove the doubles.

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

Here's a breakdown:

{
    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.
}

Answer 5

Perl, 53 49 45 44 bytes

Includes +1 for -n

Give input number on STDIN:

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

aloned.pl:

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

Directly checking the possible numbers is longer:

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

This checks all numbers in the upper half range. Keep numbers that have an even number of 2 as prime factors except if the number is a power of 2 then odd (because 1 is left out of the original series). This method should however work well for other languages.

Answer 6

MATL, 18 bytes

Borrowed the "multiply by 2" idea from @Emigna's 05AB1E answer.

q:Qt"t1)tEhym?6MX-

Try it online!

Explanation

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

Answer 7

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]

Usage example: q 22 -> [12,13,15,17,19,20,21].

If there's a multiple of the first number a, then it's 2*a. Keep a if 2*a is not in the list and append a recursive call with a and 2*a removed from the list.

Answer 8

Pyth - 19 bytes

Will definitely be refactoring.

u?Kf!%ThGtG-tGhKGtS

Test Suite.

Answer 9

Ruby, 124

Comparing scores to other answers, this is obviously the wrong approach:

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

The somewhat clever bit here is a[g[0]]=a[g[1]]=!g[1] which sets the hash's values to true/false as necessary.

Answer 10

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 save by @Titus Thank You

If a trailing comma is allowed then it can be shorten 9 Bytes (!$a?:print"$a,"); instead of (!$a?:print$x?",$a":$x=$a);

Answer 11

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;}

Here's a working example. All the HTML and the wrapper() function is just so it's actually interactive.

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

This ungolfed code snippet has some comments and lets you interactively see the steps for any given input.

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

Answer 12

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

I thought I had posted this yesterday, but obviously not...

Here's another version:

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

Answer 13

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;}

Can definitely be golfed some more by using a different approach, probably by using an array with some tricks. Due to the cast, break, typed-list and if-checks it is a bit longer than expected, but it works.

Ungolfed & test code:

Try it here.

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()));
  }
}

Output:

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

Answer 14

Racket 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 (comments after ';'):

(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.

Testing:

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

Output:

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