# Output the ALONED numbers

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 , so the shortest code in bytes wins.

• Just so you know, we have a sandbox where you can post incomplete challenges for feedback before posting it to the main site. – James Oct 21 '16 at 15:56
• Do we have to return a list of the numbers in ascending order or would an unordered list or a set be acceptable as well? – Dennis Oct 21 '16 at 20:50
• should be in ascending order. – officialaimm Oct 22 '16 at 2:56

# 05AB1E, 221715 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


## Python 2, 9079 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.

• In Python 2, range already gives a list. – xnor Oct 21 '16 at 20:53
• @xnor Thanks! Forgot about that. – DLosc Oct 21 '16 at 21:35

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

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


# Perl, 534945 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. # 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  • You need only check if k is a member, don't know if that saves you a bytes or not. – Magic Octopus Urn Oct 21 '16 at 20:03 • @carusocomputing Thanks! I initially checked only 2*k (if that's what you mean). Then I added k there because later on I reuse that array of two elements to remove both from the general array – Luis Mendo Oct 21 '16 at 20:33 ## Haskell, 716962 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. • Hehe, I was going to tell you that GCD was overkill, but you got it yourself. – Magic Octopus Urn Oct 21 '16 at 20:03 # Pyth - 19 bytes Will definitely be refactoring. u?Kf!%ThGtG-tGhKGtS  ## 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. # 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);

• Don´t the assignments to $a and $b need parentheses? Wicked! – Titus Oct 24 '16 at 11:22
• -1 byte with the trailing comma: (!$a?:print"$a,") -> print$a?"$a,":"". -2 bytes for both versions if you use the underscore as separator. – Titus Oct 24 '16 at 11:24
• -2 bytes: foreach(... as$v), $v-2 instead of $k and $v*2-2 instead of $k*2+2. – Titus Oct 24 '16 at 11:27 • @Titus I have tried it after you comment $a=&$r[$k]&&$b=&$r[$k*2+2] works like $a=$r[$k]and$b=$r[\$k*2+2]. I am sorry about I found no page which explains combinations with references and the && operator. But I need references not assignments. I'm not sure if a trailing comma or an other separator is allowed. – Jörg Hülsermann Oct 24 '16 at 13:14
• @Titus found it now php.net/manual/en/language.operators.precedence.php & bitwise and references haves a higher Precedence then the && operator – Jörg Hülsermann Oct 24 '16 at 13:58

## 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">
<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>
<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">
<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>
<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>

# 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


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


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


(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)
`