Unlucky Numbers!

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.


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.


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)