Generate Lucky Numbers

Question

Story:

Lucy asked George what his Lucky Number was. After some contemplation, George replied that he had several Lucky Numbers. After some brief confusion, Lucy asked George what his first n Lucky Numbers are. George then asked you, his buddy, to write him a program to do the work for him.

The Challenge:

You will write a program/function that will receive from standard input/function argument a string or integer n. The program/function will then return/output the first n Lucky Numbers. Lucky numbers are defined via a sieve as follows.

Start with the positive integers:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, ...

Now remove every second number:

1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, ...

The second remaining number is 3, so remove every third number:

1, 3, 7, 9, 13, 15, 19, 21, 25, ...

Now the next remaining number is 7, so remove every seventh number:

1, 3, 7, 9, 13, 15, 21, 25, ...

Next, remove every ninth number and so on. The resulting sequence are the lucky numbers.

Winning:

As usual for codegolf, fewest bytes wins.

As usual, submissions using standard loopholes are disqualified.

Answer 1

Python 2, 79

n=input()
L=range(1,2**n)
for r in L:r+=r<2;map(L.remove,L[r-1::r])
print L[:n]

The magic of iterating over a list as the loop modifies it!

The list L starts with all the integers 1 to a sufficiently high value. The code iterates over each element r of L, taking the sublist of every r'th element, and removing each of those values. As a result, the removed values aren't iterated over. At the end, print the first n elements.

The expression map(A.remove,B) is a trick I've been waiting a long time to use. It calls A.remove for each element of B, which causes all the elements of B to removed from A. Effectively, it takes the list difference, though it requires B to be a sublist of A. It requires Python 2, since Python 3 wouldn't actually evaluate the map.

The first loop needs to be special-cased to convert r from 1 to 2, as r+=r<2.

The sufficiently high upper bound of 2**n makes the program very slow for large values of n. Using n*n+1 suffices, but costs a character. Note that n*n doesn't work for n=1.

Answer 2

Haskell, 71 69 bytes

s(n:k)p=n:s[m|(i,m)<-zip[p..]k,i`mod`n>0](p+1)
f n=take n$1:s[3,5..]3

Defines a function f. The expression 1:s[3,5..]3 evaluates to the infinite list of lucky numbers, and f simply takes the first n of them by take n.

f 20
[1,3,7,9,13,15,21,25,31,33,37,43,49,51,63,67,69,73,75,79]

I could shave off 5 bytes from the sieve using a parallel list comprehension

s(n:k)p=n:s[m|m<-k|i<-[p..],i`mod`n>0](p+1)

but that would require passing the humongous compiler flag -XParallelListComp to GHC to enable the extension.

Explanation of the sieve

s(n:k)p=               -- Sieving a list with head n and tail k with accumulator p is
 n:                    -- the head n, followed by
  s[m|                 -- the result of sieving the list of numbers m
    (i,m)<-zip[p..]k,  -- where (i,m) is drawn from [(p,k_0),(p+1,k_1),(p+2,k_2),..] and
    i`mod`n>0]         -- i does not divide n,
   (p+1)               -- using p+1 as the accumulator

The basic idea is that s(n:k)p produces the (p-1)th lucky number n, drops every nth number from the infinite tail k (offset by p to account for the numbers produced earlier), and recurses to that list with accumulator (p+1). In f, we initialize the process with the odd numbers starting from 3, and tack 1 to the front, obtaining exactly the lucky numbers.

Answer 3

Python 2, 71 69 67

At first, I thought this would be a great challenge for Python's array slicing. However, I encountered a stumbling block when I discovered that slices with a step other than 1 can only have another slice of identical length assigned to them. But after googling "python remove slice", my faith was restored: I found a funky del statement that does the trick perfectly.

n=input()
l=range(n*n+9)
for v in l:del l[v&~1::v or 2]
print l[:n]

Old version

n=input()
l=range(1,n*n+9)
for v in l:del l[v-1%v::v+1/v]
print l[:n]

-2 bytes thanks to Sp3000.

Answer 4

><>, 121 114 111 bytes

i2+:&:*1\
:})?v:2+>l{
nao2\r~1
)?vv>1+:&:&=?;:[{::nao}]$}l1-[01+}:l3-$%$l1-@@-{$[{~l1
3.\ ff+
!?:<]-1v
~]{43. >

I have only a few words to say...

... "Argh my brain hurts."

---

Explanation

><> is a 2D esoteric programming language and is definitely not suited for this task, due to its lack of arrays. In fact, the only data type in ><> is strange mix of int/float/char, and everything happens on a stack of stacks.

Here's the rundown:

Line 1:            i2+:&:*1\

i2+:&              Read a char as input (n) and add 2, copying n+2 into the register
:*                 Duplicate and multiply, giving (n+2)^2 on the stack
1\                 Push 1 and go to the next line

Line 2:            >l{:})?v:2+

l{:})?v            Go to the next line if the stack's length is greater than (n+2)^2
:2+                Otherwise duplicate the top of the stack and add 2 to it

Line 3:            \r~1nao2

r~                 Reverse the stack and pop; stack contains the first (n+2)^2 odd integers
1nao               Print 1 (special case)
2\                 Push 2 (let's call this "i" for "iterations") and go to the next line

Line 4:            >1+:&:&=?;:[{::nao}]$}l1-[01+}:l3-$%$l1-@@-{$[{~l1)?vv

1+                 Increment i
:&:&=?;            If i is equal to n+2 (+2 because we started at 2), halt
:[{::nao}]$}       Print the i-th element down (the next lucky number) and also
                   copy it to the top of the stack, while moving i to the bottom
l1-[               Move everything but i to a new stack
0                  Push 0 (let's call this "r" for recursion depth)

Sieve loop:

1+                 Increment r
}:l3-$%$l1-@@-{$[  Move everything up to the last element to be sieved out to a new stack
{~                 Remove said last element
1)?vv              If the length is 1, go to line 6 (sieving complete)
                   Otherwise go to line 5, which repeats this sieve loop by teleporting

Line 6:            :?!v1-]

:?!v1-]            Keep unrolling and decrementing r until r is 0

Line 7:            >~]{43.             

~]                 Pop r and unroll once more (to the stack where i waits)
43.                Loop, performing everything from line 4 all over again

Here's a mock example which demonstrates roughly how the sieving works (here k is the lucky number which we sieve with):

[[15 13 11 9 7 5 3 1 k=3 r=0]]     -- move -->
[[15 13] [11 9 7 5 3 1 k=3 r=1]]   -- pop  -->
[[15 13] [9 7 5 3 1 k=3 r=1]]      -- move -->
[[15 13] [9 7] [5 3 1 k=3 r=2]]    -- pop  -->
[[15 13] [9 7] [3 1 k=3 r=2]]      -- move -->
[[15 13] [9 7] [3 1] [k=3 r=3]]    -- pop  -->
[[15 13] [9 7] [3 1] [r=3]]        (now we unroll)

Answer 5

CJam - 25

Lri{1$W%{1$\(1e>/+}/)+}/p

Try it online

Explanation:

This implementation doesn't remove numbers successively from an array, but calculates each number based on how many would have been removed before it.
For each index i (from 0 to n-1) and each previous lucky number l, in reverse order, we increment i by i/(l-1), except for l=1 we use 1 instead of 0, and also add 1 at the end.
E.g. for i=4 we have the first 4 numbers, [1 3 7 9], and calculate:
4 + 4/(9-1) = 4
4 + 4/(7-1) = 4
4 + 4/(3-1) = 6
6 + 6/1 = 12
12 + 1 = 13

L              empty array - the first 0 lucky numbers :)
ri             read and convert to integer (n)
{…}/           for each number (i) from 0 to n-1
    1$         copy the previous array
    W%         reverse the order
    {…}/       for each array element (l)
        1$     copy i
        \(     swap with l and decrement l
        1e>    use 1 if l=1
        /+     divide and add to i
    )+         increment and add the new lucky number to the array
p              pretty print

Answer 6

Pyth: 23 22 bytes

<u-G%@GhH+0GQ%2r1^hQ2Q

Try it online: Pyth Compiler/Executor

Explanation:

<u-G%@GhH+0GQ%2r1^hQ2Q    Q = input()
             %2r1^hQ2     create the list [1, 2, ..., (Q+1)^2-1][::2]
 u          Q%2r1^hQ2     G = [1, 2, ..., (Q+1)^2-1][::2]
                           modify G for each H in [0, 1, 2, ..., Q]:
  -G%:GhH+0G                  G = G - ([0] + G)[::G[H+1]]
                               (minus is remove in Pyth)
<                    Q    print the first Q elements of the resulting list

The reduce actually calculates more than Q lucky numbers (the remove command is called Q+1 times, Q-1 should be enough).

Answer 7

R, 58 bytes

n=scan();s=r=1:n^2;for(j in 1:n)r=r[-max(2,r[j])*s];r[1:n]

With line breaks:

n=scan()              #user input
s=r=1:n^2             #declare r and s simultaneously, both large enough to sieve
for(j in 1:n)
  r=r[-max(2,r[j])*s] #iteratively remove elements by position in vector
r[1:n]                #print

Previous version, 62 bytes

function(n){
  s=r=1:n^2             #declare r and s simultaneously, both large enough to sieve
  for(j in 1:n)
    r=r[-max(2,r[j])*s] #iteratively remove elements by position in vector
  r[1:n]                #print
}

Previous version, 78 bytes

n=as.numeric(readline())   #ask for user input and convert it to numeric
r=1:n^2                    #create a large enough vector to sieve
for(j in 1:n){             #loop
  r=r[-max(2,r[j])*1:n^2]  #iteratively remove elements by position in vector
}
r[1:n]                     #print

Answer 8

Python 2, 105 101 bytes

n=input()
L=range(-1,n*n+9,2)
i=2
while L[i:]:L=sorted(set(L)-set(L[L[i]::L[i]]));i+=1
print L[1:n+1]

Just a straightforward implementation.

Pyth, 39 36 35 32 bytes

J%2r1h^Q2VJI>JhN=J-J%@JhN+2J;<JQ

Similar to the approach above, but things are 0-indexed rather than 1-indexed. Try it online.

Thanks to @Jakube for pointing out a byte saving.

Answer 9

CJam, 32 30 bytes

3ri:N#,N{0\__I1e>)=%-+}fI(;N<p

Takes input from STDIN.

Code explanation:

3ri:N#,                          "Read the input in N and get first 3^N whole numbers";
       N{0\__I1e>)=%-+}fI        "Run the code block N times, storing index in I";
         0\__                    "Put 0 before the array and take 2 copies";
             I1e>)=              "Take min(2, I + 1) th index from the copy";
                   %             "Take every array[ min (2, I + 1)] element from the array";
                    -+           "Remove it from the list and prepend 0 to the list";
                         (;N<p   "Print number index 1 to N";

Try it online here

Answer 10

Mathematica, 80 bytes

(For[l=Range[#^2];i=1,(m=l[[i++]]~Max~2)<=Length@l,l=l~Drop~{m,-1,m}];l[[;;#]])&

Straight-forward implementation of the definition. As some other answers, starts with a range from 1 to n2 and then keeps filtering.

Answer 11

Octave, 139 83 72

function r=l(n)r=1:2:n^2;for(i=2:n)h=r(i);r(h:h:end)=[];end;r=r(1:n);end

Ungolfed:

function r=l(n)
  r=1:2:n^2;
  for(i=2:n)
    h=r(i);
    r(h:h:end)=[];
  end
r=r(1:n);  # reduce it to only N lucky numbers
end

Answer 12

Perl, 86 81 78

86:

@a=(1..($k=<>)**2);for$n(@a){$i=1;@a=map{$i++%($n+($n<2))?$_:()}@a;$k-=$k&&print"$n "}

UPDATE: obviously, grep{...} is better than map{...?$_:()} 81:

@a=(1..($k=<>)**2);for$n(@a){$i=1;@a=grep{$i++%($n+($n<2))}@a;$k-=$k&&print"$n "}

UPDATE: OK, actually a one-liner now. I can stop. (?) 78:

@a=(1..($k=<>)**2);for$n(@a){$k-=$i=$k&&print"$n ";@a=grep{$i++%($n+=$n<2)}@a}

Answer 13

JavaScript (ES6) 96 99

Edit Counting down in first loop - thanks @DocMax

F=n=>(i=>{
  for(o=[1];--i;)o[i]=i-~i;
  for(;++i<n;)o=o.filter((x,j)=>++j%o[i]);
})(n*n)||o.slice(0,n)

Ungolfed

F=n=>{
  for (i = n*n, o = [1]; --i;)
    o[i] = i+i+1;
  for (; ++i < n; )
    o = o.filter((x, j) => (j+1) % o[i])
  return o.slice(0,n)
}

Test In Firefox / FireBug console

F(57)

Output

[1, 3, 7, 9, 13, 15, 21, 25, 31, 33, 37, 43, 49, 51, 63, 67, 69, 73, 75, 79, 87, 93, 99, 105, 111, 115, 127, 129, 133, 135, 141, 151, 159, 163, 169, 171, 189, 193, 195, 201, 205, 211, 219, 223, 231, 235, 237, 241, 259, 261, 267, 273, 283, 285, 289, 297, 303]

Answer 14

J, 60 52 bytes

   ({.}.@((>:@{.,]#~0<({~{.)|i.@#)@]^:[2,1+2*i.@*:@>:)) 8
1 3 7 9 13 15 21 25

Explanation (from right to left):

2,1+2*i.@*:@>:  generates the list 2 1 3 5 7 9... with (n+1)^2 odd numbers
^:[             repeats n times the following
@]                using the list
0<({~{.)|i.@#     is the remainder of the indexes of the lists elements with the first element positive (i.e. index divisible by first element)
]#~               keep those elements from the list
>:@{.,            concatenate a first element with the value of the current one +1
}.@             drop first element
{.              take the first n element

2,1+2*i.@*:@>: seems way too long but I can only shorten it by 1 byte swapping *: with ! making the list grow exponentially.

Answer 15

Matlab, 104 bytes

function x=f(n)
k=1;N=n;x=0;while nnz(x)<n
x=1:N;m=1;while m-nnz(x)
m=x(x>m);x(m:m:end)=[];end
N=N+2;end

With thanks to @flawr for very appropriate comments and suggestions.

Example from Matlab command prompt:

>> f(40)
ans =
  Columns 1 through 22
     1     3     7     9    13    15    21    25    31    33    37    43    49    51    63    67    69    73    75    79    87    93
  Columns 23 through 40
    99   105   111   115   127   129   133   135   141   151   159   163   169   171   189   193   195   201

Answer 16

Go, 326

package main
import"fmt"
func s(k, p int,in chan int)chan int{
    o := make(chan int)
    go func(){
        for p>0{
            o<-<-in;p--
        }
        for{
            <-in
            for i:=1;i<k;i++{o<-<-in}
        }
    }()
    return o
}
func main(){
    n := 20
    fmt.Print(1)
    c := make(chan int)
    go func(c chan int){
        for i:=3;;i+=2{c<-i}
    }(c)
    for i:=1;i<n;i++{
        v := <-c
        fmt.Print(" ", v)
        c = s(v, v-i-2, c)
    }
}

Straight forward implementation using goroutine and pipes to make sieves.

Answer 17

Bash+coreutils, 136

I'd hoped to golf this down more, but oh well. Not every day that you pipe into a recursive function in a shell script:

f(){
mapfile -tn$2 a
(($1>$2))&&{
tr \  \\n<<<${a[@]}
sed $[${a[-1]}-$2]~${a[-1]}d
}|f $1 $[$2+1]||echo ${a[@]}
}
yes|sed -n 1~2=|f $1 2

Output:

$ ./lucky.sh 23
1 3 7 9 13 15 21 25 31 33 37 43 49 51 63 67 69 73 75 79 87 93 99
$ 

---

Bash+coreutils, 104

Shorter using a more straightforward implementation:

a=(`seq 1 2 $[3+$1**2]`)
for((;i++<$1;));{
a=($(tr \  \\n<<<${a[@]}|sed 0~${a[i]}d))
}
echo ${a[@]:0:$1}

Answer 18

MATLAB, 62 characters

n=input('');o=1:2:n^2;for i=2:n;o(o(i):o(i):end)=[];end;o(1:n)

I misinterpreted the challenge at first - my revised version is now actually shorter.

Answer 19

Racket 196 bytes

Produces lucky numbers upto n:

(λ(n)(let loop((l(filter odd?(range 1 n)))(i 1))(define x(list-ref l i))(set! l(for/list((j(length l))
#:unless(= 0(modulo(add1 j)x)))(list-ref l j)))(if(>= i(sub1(length l)))l(loop l(add1 i)))))

Ungolfed version:

(define f
 (λ(n)
    (let loop ((l (filter odd? (range 1 n))) (i 1))
      (define x (list-ref l i))
      (set! l (for/list ((j (length l)) #:unless (= 0 (modulo (add1 j) x)))
                (list-ref l j)))
      (if (>= i (sub1 (length l)))
          l
          (loop l (add1 i)))))
  )

Testing:

(f 100)

Output:

'(1 3 7 9 13 15 21 25 31 33 37 43 49 51 63 67 69 73 75 79 87 93 99)