Q For Problems - Episode 7

[jkane17]

Hi everyone,

Please check out episode 7 of the Q For Problems video series.

This covers problem 7 from the Project Euler problem set.

Project Euler - Problem 7

The problem is to find the 10 001st prime number.

Feel free to share your own solutions and ideas in the comments.

Github Repo

Thanks

[LeahS]

Brilliant episode 👏

Great work, thanks for sharing @jkane17

[SJT]

Another strategy: use Eratosthenes’ Sieve to write pt to return the primes to x. (No iterated arithmetic, but hungry for space.)

1. Use the π function {x%log x} to find a number P with N or more primes below it.
2. @[;n] pt (n>pi::)(2*)/1000

Details on GitHub at qbists/studyq/euler/07.md

[SJT]

Inserting a line at the beginning of the Cond in your .math.isPrimes will let it take the vector argument you give it:

0<type x; .z.s each x;

Your 6K strategy is to run through every 6th number and test one before and one behind. Since you’re looking (only) for the 10,001st prime, you should be able to save space by keeping in your state the last pair tested, the result, and the count of primes seen so far – we don’t need a list of 10,000 primes.

nprimes4:{[N]                                     / Nth prime
  is:("i"$1,count::;.math.isPrime;::)@\:2 3;      /   initial state: k:1; 2 3 found
  step:{[x;y;z] 
    b:.math.isPrime n:-1 1+6*first x;             /     test 2 candidates
    (x+1,sum b;b;n)                               /     new state 
  }.;
  fs:{x>y . 0 1}[N;] step/is;                     /   final state
  {[n;kc;b;p] (p where b)@(kc 1)-n}[N;;;] . fs }

Which is what we find.

q)\ts nprimes3 10001
371 262784
q)\ts nprimes4 10001
370 5248

q)\ts nprimes3 100001
13434 2097792
q)\ts nprimes4 100001
12290 17536

Either the time we saved by not appending to the list of primes 5000+ times was lost to extra code – or the interpreter was smart enough to do the appending without 5000+ internal copies.

It’s instructive to compare with space-hungry Eratosthenes, which instead of arithmetic uses long vector ANDs.

np:{[N]                                           / Nth prime
  es:{                                            /   Eratosthenes' sieve
    is:{(1#2;0b,1_x#10b)};                        /     initial state
    step:{(x,n;y&count[y]#i<>til n:1+i:y?1b)}. ;  /     step: sieve next prime
    {x>last first y}[floor sqrt x] step/is x };
  rslv:raze @[;1;1+where@]::;                     /   resolve result
  pt:rslv es::;                                   /   primes to
  pi:{x%log x};                                   /   π(x) first approximation
  @[;n]pt (N>pi@)(2*)/1000 }

Not intuitively obvious which will run faster. But it turns out vector-hungry q loves long vectors and implicit iteration.

q)\ts np 10001
1 526192
q)\ts np 100001
43 8391536

It’s a good example of how in a vector language ‘overcomputing’ (Eratosthenes returns all the primes found) can still be orders of magnitude faster.