Q For Problems - Episode 7

Community Support
1

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](“https://projecteuler.net/problem=7” "“Project”)

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

 

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

 

[Github Repo](“https://github.com/jkane17/qForProblems” "“Github”)

 

Thanks

2

Brilliant episode

Great work, thanks for sharing @jkane17

3

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

4

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.