Unlucky Numbers!

Question

Things to know:

First, lucky numbers.

Lucky numbers are generated like so:

Take all the natural numbers:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20...

Then, remove each second number.

1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39...

Now, 3 is safe.

Remove every 3rd number:

1, 3, 7, 9, 13, 15, 19, 21, 25, 27, 31, 33, 37, 39, 43, 45, 49, 51, 55, 59...

Now, 7 is safe.

Remove every 7th number.

Continue, and remove every nth number, where n is the first safe number after an elimination.

The final list of safe numbers is the lucky numbers.

---

The unlucky numbers is composed of separate lists of numbers, which are [U1, U2, U3... Un].

U1 is the first set of numbers removed from the lucky "candidates", so they are:

2, 4, 6, 8, 10, 12, 14, 16, 18, 20...

U2 is the second set of numbers removed:

5, 11, 17, 23, 29, 35, 41, 47, 53, 59...

And so on and so forth (U3 is the third list, U4 is the fourth, etc.)

---

Challenge:

Your task is, when given two inputs m and n, generate the mth number in the list Un.

Example inputs and outputs:

(5, 2) -> 29
(10, 1) -> 20

Specs:

• Your program must work for m up to 1e6, and n up to 100.
  • You are guaranteed that both m and n are positive integers.
  • If you're curious, U(1e6, 100) = 5,333,213,163. (Thank you @pacholik!)
• Your program must compute that within 1 day on a reasonable modern computer.

This is code-golf, so shortest code in bytes wins!

PS: It would be nice if someone came up with a general formula for generating these. If you do have a formula, please put it in your answer!

Answer 1

Perl, 87 85 82 81 bytes

Includes +4 for -pX

Give input on STDIN as one line with n first (notice this is the reverse of the order suggested in the challenge). So to calculate U(1000000, 100):

unlucky.pl <<< "100 1000000"

Algorithm based on aditsu's lucky numbers answer The time complexity is O(n^2) so it's rather fast for the required range. The 100, 1000000 case gives 5333213163 in 0.7 seconds. Due to the problems perl has with do$0 based recursion it uses a lot of memory. Rewriting it as a function would make the memory use O(n) but is a number of bytes longer

unlucky.pl:

#!/usr/bin/perl -pX
$_=$a{$_}||=/\d+$/>--$_?2*$&+$^S:($_=$_.A.(do$0,$^S?0|$&+$&/~-$_:$&*$_-1),do$0)

This works as shown, but use literal ^S to get the claimed score.

I am not aware of any earlier use of $^S in perlgolf.

Answer 2

Python 3, 170

from itertools import*
def L(n,k=1):
 if n<2:yield from count(2+k,2)
 t=L(n-1);l=next(t)
 for i in t:
  n+=1
  if(n%l>0)==k:yield i
U=lambda m,n:sum(islice(L(n,0),m-1,m))

Function L generates the row of possible lucky numbers (if k is True) or Un (if False). Evaluated lazily (so I don't have to generate n-1 infinite lists if I want Un).

Run function U.

Speed

U(1,000,000; 100) takes about 1h 45min to run on my machine with PyPy. I suspect some four hours with CPython. (Yes, 4h 20min to be precise.)

If I used a list instead of generators, I might gain some speed, but I would need a list of greater size than Python allows me. And if it did, it would need dozens of gigabytes of RAM.

---

Yes, and U(1,000,000; 100) = 5,333,213,163.

Answer 3

Haskell

Not able to compute for n=1: 175 160 bytes

When compiled, it took my computer 2h 35m to compute for an input of (1000000,100) using this:

n#s=y:(n#p)where y:p=drop(n-1)s
n%s=f n s$[]where f n s=(take(n-1)s++).f n(drop n s) 
l 2=[1,3..]
l m=((l$m-1)!!(m-2))%(l$m-1)
m?n=(((l n)!!(n-1))#(l$n))!!(m-1)

I tried ridding the where modules, but they seem to affect the speed and I'm not sure why... But I think there is more pruning to be done here.

The method to use is m?n for querying the answer given an m and n.

Ungolfed

everynth n xs = y:(everynth n ys) -- Takes every nth element from a list 'xs'
  where y:ys = drop (n-1) xs

skipeverynth n xs = f' n xs $ []  -- Removes every nth element from a list 'xs'
  where f' n xs = (take (n-1) xs ++) . f' n (drop n xs) 

l 2 = [1,3..] -- The base case of the list of lucky numbers for 'n=2'
l m = skipeverynth ((l$m-1)!!(m-2)) (l$m-1) -- Recursively defining next case as being the last one with every 'ath' element skipped. Here, 'a' is the (m-1)th elemnent of the (l (m-1)) list.
ul m = everynth ((l m)!!(m-1)) (l$m) -- This is not used other than to compute the final, required unlucky number list. It picks out every 'ath' element.

ans m n = (ul n)!!(m-1) -- The function giving the answer.

I reckon it may be possible to combine the 'skipeverynth' and 'everynth' functions into a single function which returns a pair.

I used this kind person's code for skipping every nth element. I did it myself a few times, but it was always much more inefficient and I couldn't figure out why.

Able to compute for all n: 170 bytes

This is basically the same, but a couple of max functions had to be thrown in to handle the special case of n=1.

n#s=y:(n#p)where y:p=drop(n-1)s
n%s=f n s$[]where f n s=(take(n-1)s++).f n(drop n s) 
l 1=[1..]
l m=((l$m-1)!!(max 1$m-2))%(l$m-1)
m?n=(((l n)!!(max 1$n-1))#(l$n))!!(m-1)

Answer 4

R 82 bytes

f<-function(m,n){a=1:2e8
i=1
while(i<n){a=c(0,a)[c(F,rep(T,i))]
i=i+1}
a[(n+1)*m]}

Usage

f(5,2)
Returns 29

This needs to have a large enough vector to start with so there are enough numbers left to return the value. The vector created is already about 800Mb and the function can handle upto m=1e4 and n=100 so still well short of the goal.

To create a large enough vector to calculate f(1e6,100) would take a starting vector of 1:2e10. Due to Rs data allocation procedures this creates a vector >70Gb which can't be run on any computer I know although the code would run.

Error: cannot allocate vector of size 74.5 Gb

For reference f(1e4,100) runs in about in about 30 seconds. Based on this and a couple smaller tests f(1e6,100) would take about an hour.

Answer 5

CJam, 74 bytes

ri0Lri:U{1$W%{1$\(1e>/+}/)+}/2t:A0@{@:B:(_0#):D{D(_A=tD<BD>+}&@)@DU=-}h]1=

Try it online! Will time out for larger cases, more on time constraints below.

---

Explanation:

Our program shamelessly borrows for aditsu's code to generate a list of N lucky numbers, replacing 1 with a 2 gives the increment in each phase of the sieve. The remaining code decrements on every element until a zero is found (by slicing and appending an un-decremented tail) and effectively counts the steps in each of N phases of the sieve at once.

ri                               e# read M
0Lri:U{1$W%{1$\(1e>/+}/)+}/2t:A  e# list steps (also becomes B)
0@                               e# arrange stack [B I M]
{                                e# while M
   @:B                           e#   get current B
   :(                            e#   decrement every element in B
   _0#):D                        e#   find first 0
   {                             e#   if there is a 0
      D(_A=t                     e#     reset that element in B
      D<BD>+                     e#     replace tail after 0
   }&                            e#   end if
   @)                            e#   increment I
   @DU=-                         e#   decrement M if N-th phase of sieve
}h                               e# end loop
]1=                              e# return I

---

Timing:

If you absolutely must run the program in browser for larger numbers you can use this interpreter and allow the script to continue if prompted, but this maybe too slow to qualify. Using (M,N)=(100,100) takes ~247s. The programs iteration is relatively linear in terms of M, so computing (1e6,100) could take ~29 days.

Using the shell interpreter on a PC the program computes (100,100) in ~6s and computes (1e4,100) in ~463s. The program should be able to compute (1e6,100) in ~13-17hrs. In this case I'll assume the program qualifies.

Note all times were rounded up in both measurements and calculations.

Answer 6

Racket 332 bytes

(λ(N m n)(let loop((l(filter odd?(range 1 N)))(i 1))(define x (list-ref l i))(if(= i (sub1 n))
(begin(set! l(for/list((j(length l))#:when(= 0(modulo(add1 j)x)))(list-ref l j)))(list-ref l(sub1 m)))
(begin(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 m n)
    (let loop ((l (filter odd? (range 1 N))) (i 1))
      (define x (list-ref l i))
      (if (= i (sub1 n))
          (begin (set! l (for/list ((j (length l)) 
                                   #:when (= 0 (modulo (add1 j) x)))
                           (list-ref l j)))
                 (list-ref l (sub1 m)))
          (begin (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 5 2)

Output:

29

Answer 7

Clojure, 221 bytes

Mighty long but handles the case (f 1). Without that special case it was 183 bytes. This was too much effort not to have it posted.

(defn f([n](if(< n 2)(take-nth 2(drop 2(range)))(f n 1(take-nth 2(rest(range))))))([n i c](if (< n 2)c(let[N(first(drop i c))F #((if(= 2 n)= >)(mod(inc %)N)0)](f(dec n)(inc i)(filter some?(map-indexed #(if(F %)%2)c)))))))

Sample outputs:

(pprint (map #(take 10 (f %)) (range 1 10)))
((2 4 6 8 10 12 14 16 18 20)
 (5 11 17 23 29 35 41 47 53 59)
 (19 39 61 81 103 123 145 165 187 207)
 (27 57 91 121 153 183 217 247 279 309)
 (45 97 147 199 253 301 351 403 453 507)
 (55 117 181 243 315 379 441 505 571 633)
 (85 177 277 369 471 567 663 757 853 949)
 (109 225 345 465 589 705 829 945 1063 1185)
 (139 295 447 603 765 913 1075 1227 1377 1537))

1000000 100 case was calculated in about 4.7 hours, at least it didn't crash.

java -jar target\stackoverflow-0.0.1-SNAPSHOT-standalone.jar 1000000 100
5333213163
"Elapsed time: 1.7227805535565E7 msecs"