22
\$\begingroup\$

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.

\$\endgroup\$
  • 8
    \$\begingroup\$ I'd suggest including the definition in the post as well as the first ten or so numbers. \$\endgroup\$ – xnor Feb 17 '15 at 4:14
  • \$\begingroup\$ 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) \$\endgroup\$ – Ryan Feb 17 '15 at 15:51
  • \$\begingroup\$ @Ryan I think that sequence would be remarkably similar to the natural numbers :) \$\endgroup\$ – TheNumberOne Feb 18 '15 at 2:40
  • \$\begingroup\$ @TheBestOne You think so? I posted earlier to math.stackexchange: math.stackexchange.com/questions/1153889/… \$\endgroup\$ – Ryan Feb 18 '15 at 2:41
  • \$\begingroup\$ @Ryan Actually, I misinterpreted your suggestion. As you stated it in your question on math.se, I think that would be interesting. \$\endgroup\$ – TheNumberOne Feb 18 '15 at 2:47

19 Answers 19

16
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ You just need n**2 numbers, not 2**n \$\endgroup\$ – Optimizer Feb 17 '15 at 6:32
  • 3
    \$\begingroup\$ That's one amazing use of map you have there. I was wondering whether there was a better way... \$\endgroup\$ – Sp3000 Feb 17 '15 at 6:33
  • \$\begingroup\$ @Optimizer Unfortunately, n**2+1, unless the case n=1 can be forgiven. \$\endgroup\$ – xnor Feb 17 '15 at 6:34
  • \$\begingroup\$ 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. \$\endgroup\$ – Logic Knight Feb 17 '15 at 6:43
13
\$\begingroup\$

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.

\$\endgroup\$
12
\$\begingroup\$

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.

\$\endgroup\$
10
\$\begingroup\$

><>, 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)
\$\endgroup\$
  • 7
    \$\begingroup\$ Still better than Java ;) \$\endgroup\$ – Optimizer Feb 17 '15 at 14:01
  • 5
    \$\begingroup\$ I like the fact that nao can apparently be interpreted as "print this thing now". \$\endgroup\$ – Zgarb Feb 17 '15 at 14:24
10
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Interesting technique :) \$\endgroup\$ – TheNumberOne Feb 18 '15 at 3:21
6
\$\begingroup\$

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

\$\endgroup\$
5
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Alex A. Feb 17 '15 at 18:10
  • \$\begingroup\$ Thanks @Alex! Though that's 66, since it needs a name? \$\endgroup\$ – freekvd Feb 17 '15 at 20:13
  • \$\begingroup\$ 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. \$\endgroup\$ – Alex A. Feb 17 '15 at 22:41
  • \$\begingroup\$ What about n=scan(n=1)? \$\endgroup\$ – koekenbakker Feb 18 '15 at 12:53
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – freekvd Feb 18 '15 at 13:06
4
\$\begingroup\$

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

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

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.

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

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.

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

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

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

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.

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

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]
\$\endgroup\$
  • 1
    \$\begingroup\$ 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)} \$\endgroup\$ – DocMax Feb 19 '15 at 1:02
  • \$\begingroup\$ Your ungolfed doesn't really help here :P ;) \$\endgroup\$ – Optimizer Feb 19 '15 at 9:46
  • \$\begingroup\$ @Optimizer ungolfed updated - maybe still not of much help, but at least working now \$\endgroup\$ – edc65 Feb 19 '15 at 9:57
  • \$\begingroup\$ I meant more on lines on "simply a formatting change won't help, please provide comments :)" \$\endgroup\$ – Optimizer Feb 19 '15 at 10:01
2
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Thanks! I used that in the past, but tend to forget \$\endgroup\$ – Luis Mendo Feb 17 '15 at 23:33
  • \$\begingroup\$ @flawr Good point. This answer is becoming more yours than mine! :-) \$\endgroup\$ – Luis Mendo Feb 17 '15 at 23:40
  • \$\begingroup\$ Sure! I hang out more often in StackOverflow, but it's the same spirit there. I appreciate it! \$\endgroup\$ – Luis Mendo Feb 17 '15 at 23:43
  • \$\begingroup\$ Good point! I'm not sure all this I'm learning will be helpful or actually harmful for my standard Matlab usage, though :-P \$\endgroup\$ – Luis Mendo Feb 17 '15 at 23:45
  • 2
    \$\begingroup\$ Well codegolf is not about the use, but rather about the abuse of a language^^ \$\endgroup\$ – flawr Feb 17 '15 at 23:46
1
\$\begingroup\$

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

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.

\$\endgroup\$
  • 7
    \$\begingroup\$ This Code Golf, please add a byte count. \$\endgroup\$ – edc65 Feb 17 '15 at 16:55
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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