22
\$\begingroup\$

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 , 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!

\$\endgroup\$
  • \$\begingroup\$ On OEIS: A219178 and A255543 \$\endgroup\$ – Arnauld Sep 27 '16 at 11:09
  • 6
    \$\begingroup\$ Related. \$\endgroup\$ – Martin Ender Sep 27 '16 at 11:15
  • 2
    \$\begingroup\$ Have you implemented code that can actually perform (1e6,1e6)? \$\endgroup\$ – Jonathan Allan Sep 27 '16 at 14:18
  • 2
    \$\begingroup\$ If you're going to have a time requirement, you need to specify the timing environment (such as your machine, a freely-available online VM, or "a reasonable modern computer"). \$\endgroup\$ – Mego Sep 28 '16 at 13:01
  • 1
    \$\begingroup\$ Is it acceptable for the function not to work for the n=1 case? As this is special-- for all other cases, the 0-based index of the next lucky number is n-1. \$\endgroup\$ – Myridium Sep 28 '16 at 20:09
1
\$\begingroup\$

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.

\$\endgroup\$
7
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ But how long does this take for (1e6,100)? \$\endgroup\$ – Myridium Sep 30 '16 at 17:14
  • \$\begingroup\$ @Myridium Due to the memory explosion caused by do$0 it is basically unreachable on any realistic computer. But if that much memory existed about 2 years. I haven't really written out and tested a normal subroutine based version, but I would expect that to finish in a few months and run even on computers with very little memory. So it's a good thing these values are not in the required range for this challenge. \$\endgroup\$ – Ton Hospel Sep 30 '16 at 18:58
  • \$\begingroup\$ Isn't the challenge to compute for (1e6,100) within a day? What do you mean these values are not required? \$\endgroup\$ – Myridium Sep 30 '16 at 19:21
  • \$\begingroup\$ @Myridium Notice that in my program n and m are given in reverse order. The 100 1000000 input calculatesU(1000000, 100) and gives 5,333,213,163 in 0.7 seconds. It is by far the fastest program of these currently posted \$\endgroup\$ – Ton Hospel Sep 30 '16 at 19:31
  • \$\begingroup\$ Ah okay, I expected (100,1e6) to be much faster than (1e6,100), and thought this was the explanation for the lightning fast 0.7 seconds! \$\endgroup\$ – Myridium Sep 30 '16 at 19:33
7
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Should be valid now. \$\endgroup\$ – Qwerp-Derp Sep 27 '16 at 22:18
3
\$\begingroup\$

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

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.

\$\endgroup\$
  • \$\begingroup\$ Marking your answer as non-competing does not excuse it from failing to meet the challenge requirements. \$\endgroup\$ – Mego Oct 2 '16 at 7:55
  • \$\begingroup\$ @Mego Ive seen plenty of answers that fail to meet requirements (there is at least 1 other in this challenge). I coded it and I feel it meets the spirit of the coding request, I also clearly stated where it fell short. Also as you mention in your comments to the question it doesnt state what type of computer it needs to test on. Im sure there are computers out there that could write 7 Gb to memory and process it. The one I was on couldnt do it but i still wanted to post and i thought the clear statement was a valid compromise. \$\endgroup\$ – gtwebb Oct 2 '16 at 15:15
  • \$\begingroup\$ We have a clear policy about answers not meeting the challenge specification. That being said, I'm not sure why you labelled your answer as non-competing. If I understand correctly, this should work given enough memory, but you couldn't test it because you don't have enough RAM. Is that correct? \$\endgroup\$ – Dennis Oct 2 '16 at 15:23
  • 1
    \$\begingroup\$ 1. This policy is being enforced, but four moderators cannot test all answers on the site. If you find a submission that doesn't comply with the rules, be flag it for moderator attention so we can take a look. 2. You don't have to learn a golfing language to participate. Production languages like R are just as welcome. I post Python answers myself on a regular basis. \$\endgroup\$ – Dennis Oct 2 '16 at 15:45
  • 1
    \$\begingroup\$ 3. The spec doesn't mention any memory limits, but there is a 24 hour time limit. In the absence of a computer with 70 GiB (or did you mean gigabits) to test this on, it's hard to determine if this answer is valid or not. I suggest trying to extrapolate the runtime as well as you can. If it's less than a day, remove the non-competing header and include your extrapolation in the post. If it takes longer, your submission should be optimized or removed. \$\endgroup\$ – Dennis Oct 2 '16 at 15:45
1
\$\begingroup\$

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

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