21
\$\begingroup\$

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.

\$\endgroup\$
  • 7
    \$\begingroup\$ Just so you know, we have a sandbox where you can post incomplete challenges for feedback before posting it to the main site. \$\endgroup\$ – DJMcMayhem Oct 21 '16 at 15:56
  • 4
    \$\begingroup\$ 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? \$\endgroup\$ – Dennis Oct 21 '16 at 20:50
  • \$\begingroup\$ should be in ascending order. \$\endgroup\$ – officialaimm Oct 22 '16 at 2:56

14 Answers 14

5
\$\begingroup\$

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
\$\endgroup\$
6
\$\begingroup\$

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.

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

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.

\$\endgroup\$
4
\$\begingroup\$

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.
}
\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ You need only check if k is a member, don't know if that saves you a bytes or not. \$\endgroup\$ – Magic Octopus Urn Oct 21 '16 at 20:03
  • \$\begingroup\$ @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 \$\endgroup\$ – Luis Mendo Oct 21 '16 at 20:33
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Hehe, I was going to tell you that GCD was overkill, but you got it yourself. \$\endgroup\$ – Magic Octopus Urn Oct 21 '16 at 20:03
2
\$\begingroup\$

Pyth - 19 bytes

Will definitely be refactoring.

u?Kf!%ThGtG-tGhKGtS

Test Suite.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Don´t the assignments to $a and $b need parentheses? Wicked! \$\endgroup\$ – Titus Oct 24 '16 at 11:22
  • \$\begingroup\$ -1 byte with the trailing comma: (!$a?:print"$a,") -> print$a?"$a,":"". -2 bytes for both versions if you use the underscore as separator. \$\endgroup\$ – Titus Oct 24 '16 at 11:24
  • \$\begingroup\$ -2 bytes: foreach(... as$v), $v-2 instead of $k and $v*2-2 instead of $k*2+2. \$\endgroup\$ – Titus Oct 24 '16 at 11:27
  • \$\begingroup\$ @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. \$\endgroup\$ – Jörg Hülsermann Oct 24 '16 at 13:14
  • \$\begingroup\$ @Titus found it now php.net/manual/en/language.operators.precedence.php & bitwise and references haves a higher Precedence then the && operator \$\endgroup\$ – Jörg Hülsermann Oct 24 '16 at 13:58
1
\$\begingroup\$

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>

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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]
\$\endgroup\$
1
\$\begingroup\$

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)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.