Vocabulary/pco

>> <<   Down to: Dyad   Back to: Vocabulary Thru to: Dictionary

p: y

Primes

Rank 0 -- operates on individual atoms of y, producing a result of the same shape -- WHY IS THIS IMPORTANT?

---

The y-th prime (starting with 2 as the 0-th prime).

   p: i.9
2 3 5 7 11 13 17 19 23
   p: 2000
17393

The inverse  p:^:_1 y tells the number of primes less than y

   p:^:_1 (17 19 23 24 25)
6 7 8 9 9

---

Common uses

Mathematical investigations.

---

Related Primitives

Prime Factors * Prime Exponents (q:)

---

x p: y

Primes

Rank Infinity -- operates on x and y as a whole -- WHY IS THIS IMPORTANT?

---

A collection of prime-related functions of integer y, with x selecting the function.

The Prime Functions x p: y
x	Function
_4	The largest prime smaller than y
_1	π(y), the number of primes less than y (same as p:^:_1)
0	1 if y is not prime
1	1 if y is prime
2	a 2-row table of the prime factors and exponents in the factorization of y (same as __ q: y)
3	the list of primes whose product is equal to y (same as q: y)
4	The smallest prime larger than y
5	The number of integers less than or equal to y that are relatively prime to y (Euler's totient function φ(y))

   ]y=: p: 2001   NB. The 2001st prime
17401

   _4 p: y        NB. Next prime down from y
17393
   4 p: 17393     NB. Next prime up from 17393
17401
   _1 p: y        NB. Number of primes <y
2001
   1 p: y         NB. Boolean: y is prime
1
   0 p: y         NB. Boolean: y is non-prime
0

   1 p: i.25      NB. flags the primes in i.25
0 0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0
   I. (1 p: i.25) NB. Primes in (i.25)
2 3 5 7 11 13 17 19 23
                  NB. Euler's Prime-Generating Polynomial n^2 + n + 41 is 
                  NB. known to generate (distinct) primes for n = 0..39
   1 p: 41 1 1 p. i. 40
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
                  NB. and has less than 100% success for n > 39
   v=. 41 1 1 p. 39 + i. 12     
   (] ,:1&p:) v
1601 1681 1763 1847 1933 2021 2111 2203 2297 2393 2491 2591
   1    0    0    1    1    0    1    1    1    1    0    1

   3 p: 2+ 2^31   NB. prime factorization of 2+(2^31)
2 5 5 13 41 61 1321
   2 p: 2+ 2^31   NB. table of prime factors of 2+(2^31) with their exponents
2 5 13 41 61 1321
1 2  1  1  1    1
   3 p: !23x      NB. same for a factorial (note the use of extended precision integer)
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 5 5 5 5 7 7 7 11 11 13 17 19 23
   2 p: !23x
 2 3 5 7 11 13 17 19 23
19 9 4 3  2  1  1  1  1

   NB. Totient function φ(y) = Number of co-prime integers less than or equal to y
   NB. φ(y) = y-1 (if y is prime) and less of course if y is composite

   5 p: y         NB. y (17401) is prime
17400
   3 p: y-1       NB. y-1 (17400) is composite (non-prime)
2 2 2 3 5 5 29
   2 p: y-1       NB. showing distinct prime factors
2 3 5 29
3 1 2  1
                  NB. using Product over the distinct prime factors
   (y-1)*(1-1r2)*(1-1r3)*(1-1r5)*(1-1r29)    
4480
                  NB. using Product (more elegant version from the 'Voc/Primes' section)
   */ (p-1)*p^e-1 [ 'p e'=. 2 p: y-1
4480
                  NB. using Product (Andrew Nikitin's version of above expression)
   (- ~:) &. q: y-1
4480
   5 p: y-1       NB. using Totient function shortcut
4480

---

Common uses

Mathematical investigations.

---

Related Primitives

Prime Factors * Prime Exponents (q:)

---

Details

1. Primality testing on numbers larger than (2^31) uses the probabilistic Miller-Rabin algorithm.

---