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)