Generate Lucky Numbers

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.

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.

• I'd suggest including the definition in the post as well as the first ten or so numbers.
– xnor
Feb 17, 2015 at 4:14
• A cool extension would be that for each item examined (3, 7, etc.) will do that operation that number of times. For example for 3, remove the third element in the list 3 times, the 7th element 7 times, etc. (note this is not the sequence but the idea is the same)
– Ryan
Feb 17, 2015 at 15:51
• @Ryan I think that sequence would be remarkably similar to the natural numbers :) Feb 18, 2015 at 2:40
• @TheBestOne You think so? I posted earlier to math.stackexchange: math.stackexchange.com/questions/1153889/…
– Ryan
Feb 18, 2015 at 2:41
• @Ryan Actually, I misinterpreted your suggestion. As you stated it in your question on math.se, I think that would be interesting. Feb 18, 2015 at 2:47

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.

• You just need n**2 numbers, not 2**n Feb 17, 2015 at 6:32
• That's one amazing use of map you have there. I was wondering whether there was a better way... Feb 17, 2015 at 6:33
• @Optimizer Unfortunately, n**2+1, unless the case n=1 can be forgiven.
– xnor
Feb 17, 2015 at 6:34
• That use of map is brilliant. Like using an ordered set. Perhaps also can be used like map(A.index,B) to find the indexes of the elements of B in A, map(A.count,B) to find the number of the elements of B in A, map(A.extend,B) to add a flattened B list to A. The mind boggles. Feb 17, 2015 at 6:43

s(n:k)p=n:s[m|(i,m)<-zip[p..]k,imodn>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..],imodn>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 imodn>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. • Sorry, but is the input n$1? Cuz running running say f n=take 10:s[3,5..]3 doesnt work :/ Nov 11, 2022 at 11:46
• @DialFrost The code snippet defines a function f that you can call like f 10. Try it online! Nov 12, 2022 at 7:19
• Ya lol, but I wanted it to be shorter? So theres no other way? Nov 12, 2022 at 10:12

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.

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


><>, 121114 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)

• Still better than Java ;) Feb 17, 2015 at 14:01
• I like the fact that nao can apparently be interpreted as "print this thing now". Feb 17, 2015 at 14:24

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

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

• 64 bytes: Change n=as.numeric(readline()) to function(n){...}. This creates a function object that can be assigned and called. Drop the curly braces in the for loop. Feb 17, 2015 at 18:10
• Thanks @Alex! Though that's 66, since it needs a name? Feb 17, 2015 at 20:13
• It doesn't need a name for the submission. See the Matlab/Octave solutions. R function objects are akin to unnamed/lambda functions in other languages, which are valid submissions. Feb 17, 2015 at 22:41
• What about n=scan(n=1)? Feb 18, 2015 at 12:53
• That works! And it's 1 character less. It's even shorter if I'd drop the n=1, the function ignores all elements of n after the first. Feb 18, 2015 at 13:06

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

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, 393635 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.

Perl, 8681 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}  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. 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. 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]  • You can save 1 by counting down with the first loop and up with the second: F=n=>{for(o=[1],i=n*n;--i;)o[i]=2*i+1;for(;++i<n;o=o.filter((x,j)=>++j%o[i]));return o.slice(0,n)} Feb 19, 2015 at 1:02 • Your ungolfed doesn't really help here :P ;) Feb 19, 2015 at 9:46 • @Optimizer ungolfed updated - maybe still not of much help, but at least working now Feb 19, 2015 at 9:57 • I meant more on lines on "simply a formatting change won't help, please provide comments :)" Feb 19, 2015 at 10:01 Octave, 13983 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  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  • Thanks! I used that in the past, but tend to forget Feb 17, 2015 at 23:33 • @flawr Good point. This answer is becoming more yours than mine! :-) Feb 17, 2015 at 23:40 • Sure! I hang out more often in StackOverflow, but it's the same spirit there. I appreciate it! Feb 17, 2015 at 23:43 • Good point! I'm not sure all this I'm learning will be helpful or actually harmful for my standard Matlab usage, though :-P Feb 17, 2015 at 23:45 • Well codegolf is not about the use, but rather about the abuse of a language^^ Feb 17, 2015 at 23:46 Julia, 66 bytes x->(l=[1:x^2;];[deleteat!(l,(i+=i<2):i:length(l)) for i=l];l[1:x])  Try it online! 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}


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.

05AB1E, 17 16 bytes

∞IFD®LKн©ô€¨˜}I£


Try it online.

Explanation:

∞             # Push an infinite positive list: [1,2,3,...]
IF           # Loop the input amount of times:
D          #  Duplicate the infinite list
®L        #  Push a list in the range [1,®]
#  (® is -1 by default, so the list is [1,0,-1] the first iteration)
K       #  Remove all those values from the duplicated list
н      #  Pop the list and leave the first (smallest) value
#  (this is basically the smallest value above ®)
©     #  Store it as new ® (without popping)
ô    #  Split the infinite list into parts of size ®
€¨  #  Remove the last item of each inner list
˜ #  Flatten it back to a single list
}I£         # After the loop: only leave the first input amount of values
# (after which the list is output implicitly as result)


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.

• This Code Golf, please add a byte count. Feb 17, 2015 at 16:55

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


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

(f 100)

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