Consider the following expressions:
3*0 1 2 3 4 5 6 0 3 6 9 12 15 18 1+3*0 1 2 3 4 5 6 1 4 7 10 13 16 19 2+3*0 1 2 3 4 5 6 2 5 8 11 14 17 20
From the first expression, it is clear that the numbers 0, 3, 6, 9, 12, 15, and 18 are each the product of 3 and some integer; they are therefore said to be integer multiples or simply multiples of 3. A number which is an integer multiple of 3 is also said to be divisible by 3.
The numbers 1, 4, 7, 10, 13, 16, and 19 are not divisible by 3; when divided by 3 they each yield an integer quotient and a remainder of 1. Similarly the numbers 2, 5, 8, 11, 14, 17, and 20 each yield a remainder of 2 when divided by 3. The remainder when dividing an integer by 3 must be either 2 or 1 or 0. If the remainder is 0 the number is, of course, divisible by 3.
The remainder obtained on dividing an integer b by an integer a is a function of a and b. This function is provided by the remainder or residue verb, which is denoted by a vertical line as follows: a|b. For example:
3|6 0 3|7 1 3|0 1 2 3 4 5 6 7 8 9 10 0 1 2 0 1 2 0 1 2 0 1 5|0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 0 1 2 3 4 0
A function table for residue is shown in Figure 7.1. From this table it should be clear that the results of the expression a|b must be one of the integers 0, 1, 2, 3, etc., up to a-1. That is, the results belong to the list i.a.
| 1 | 1 | 1 | 1 | 1 |
|
Left Domain: 1+i.8
Right domain: i.15 Body: (1+i.8)|/i.15 Symbol: | |
|||||||||||
| | | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0 | 1 | 2 | 3 | 4 | ||
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ||
| 2 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | ||
| 3 | 0 | 1 | 2 | 0 | 1 | 2 | 0 | 1 | 2 | 0 | 1 | 2 | 0 | 1 | 2 | ||
| 4 | 0 | 1 | 2 | 3 | 0 | 1 | 2 | 3 | 0 | 1 | 2 | 3 | 0 | 1 | 2 | ||
| 5 | 0 | 1 | 2 | 3 | 4 | 0 | 1 | 2 | 3 | 4 | 0 | 1 | 2 | 3 | 4 | ||
| 6 | 0 | 1 | 2 | 3 | 4 | 5 | 0 | 1 | 2 | 3 | 4 | 5 | 0 | 1 | 2 | ||
| 7 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 0 | ||
| 8 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
#1-2
The following examples show how the residue verb applies to negative right arguments:
]s=._5+i.11 _5 _4 _3 _2 _1 0 1 2 3 4 5 3*s _15 _12 _9 _6 _3 0 3 6 9 12 15 3|3*s 0 0 0 0 0 0 0 0 0 0 0 1+3*s _14 _11 _8 _5 _2 1 4 7 10 13 16 3|1+3*s 1 1 1 1 1 1 1 1 1 1 1 2+3*s _13 _10 _7 _4 _1 2 5 8 11 14 17 3|2+3*s 2 2 2 2 2 2 2 2 2 2 2
It should be clear from these examples that the 3-residue of b (that is, 3|b) is obtained by adding or subtracting some integer multiple of 3 so that the result is the smallest non-negative number that can be so obtained. In general, the result a|b is the smallest non-negative integer that can be obtained by adding to, or subtracting from, b some integer multiple of a.
#3-4
The integer b is divisible by the integer a only if the a-residue of b is zero, that is, only if 0=a|b. Since the expression (1+i.8)|/i.15 produced a table of residues (Table 7.1), the expression 0=(1+i.8)|/i.15 will produce the body of the corresponding divisibility table:
| 1 | 1 | 1 | 1 | 1 | |||||||||||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0 | 1 | 2 | 3 | 4 | |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| 3 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 |
| 4 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 |
| 5 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
| 6 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| 7 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| 8 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
It is also interesting to arrange the integers 0 to 99 in a 10 by 10 table and then observe the patterns produced by first taking residues and then determining divisibility. For example:
]m=.(10*i.10)+/i.10 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99
5|m 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 |
0=5|m 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 |
3|m 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 |
0=3|m 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 1 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 |
#5-12
If b is divisible by a, then a is said to be a factor of b. For example, 3 is a factor of 12, and 5 is a factor of 15, and so on as shown below:
12%3 4 15%5 3 9%3 3 24%4 6 24%8 3 |
3|12 0 5|15 0 3|9 0 4|24 0 8|24 0 |
From these examples it is clear that the factors of any number b occur in pairs such that the product of the pair is equal to b . Thus if 3 is a factor of 12 then 12%3 (that is, 4 is also a factor and 3*4 is equal to 12. In general, if a is a factor of b, then b%a is also a factor and the product of the pair of factors a and b%a (that is, (b%a)*a) is equal to b.
All possible factors of a number b can be found by simply trying to divide it by each of the integers from 1 up to and including b. For example, the number 24 has the following 8 factors:
1 2 3 4 6 8 12 24
The factor pairs of 24 can be obtained by simply dividing 24 by the list of its factors as follows:
24%1 2 3 4 6 8 12 24 24 12 8 6 4 3 2 1
Thus 1 and 24 are a pair; 2 and 12 are a pair; and so on.
The residue verb can be used to determine which of the integers 1+i.b are factors of b. For example, if b is 6, then:
1 2 3 4 5 6|6 0 0 0 2 1 0 0=1 2 3 4 5 6|6 1 1 1 0 0 1
The positions of the 1s in the last list indicate which of the integers 1 2 3 4 5 6 are factors of 6. For example, since the third element is 1, then 3 is a factor, and since the fourth element is 0, then 4 is not a factor. The list 1 1 1 0 0 1 can be used to pick out the actual factors 1 2 3 6 by means of the compression verb discussed in the following section.
#13-16
The following examples show the behavior of the compression case of the copy verb, which selects elements from a list using a Boolean left argument:
1 0 1 0 1#1 2 3 4 5 1 3 5 1 0 1 0 1#2 3 5 7 11 2 5 11 (1+i.6)|6 0 0 0 2 1 0 0=(1+i.6)|6 1 1 1 0 0 1 (0=(1+i.6)|6)#1+i.6 1 2 3 6 (0=(1+i.24)|24)#1+i.24 1 2 3 4 6 8 12 24
#17-18
The following expressions yield all factors for each of the integers from 1 to 8:
(0=(1+i.1)|1)#1+i.1 1 (0=(1+i.2)|2)#1+i.2 1 2 (0=(1+i.3)|3)#1+i.3 1 3 (0=(1+i.4)|4)#1+i.4 1 2 4 (0=(1+i.5)|5)#1+i.5 1 5 (0=(1+i.6)|6)#1+i.6 1 2 3 6 (0=(1+i.7)|7)#1+i.7 1 7 (0=(1+i.8)|8)#1+i.8 1 2 4 8
Any number which has exactly two distinct factors is called a prime number. From the above examples it is clear that 2, 3, 5, and 7 are primes, but 1, 4, 6, and 8 are not. Thus a prime has no factors other than itself and 1.
If k is a list of 0s and 1s, then +/k gives the count of the number of 1s in it. For example:
+/1 1 0 1 0 0 0 1 4 0=(1+i.8)|8 1 1 0 1 0 0 0 1 +/0=(1+i.8)|8 4
The conditions for a prime number stated above in words can therefore be stated algebraically as follows: b is a prime number if the expression 2=+/0=(1+i.b)|b has the value 1. For example:
2=+/0=(1+i.1)|1 0 2=+/0=(1+i.2)|2 1 2=+/0=(1+i.3)|3 1 2=+/0=(1+i.4)|4 0 2=+/0=(1+i.5)|5 1 2=+/0=(1+i.6)|6 0 2=+/0=(1+i.7)|7 1 2=+/0=(1+i.8)|8 0
This same test can be used to obtain all of the primes up to a certain value by applying it to a divisibility table. Consider, for example, the following tables:
| | | 1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12 |
|
Left: D:1+i.12
|
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ||
| 2 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | ||
| 3 | 1 | 2 | 0 | 1 | 2 | 0 | 1 | 2 | 0 | 1 | 2 | 0 | ||
| 4 | 1 | 2 | 3 | 0 | 1 | 2 | 3 | 0 | 1 | 2 | 3 | 0 | ||
| 5 | 1 | 2 | 3 | 4 | 0 | 1 | 2 | 3 | 4 | 0 | 1 | 2 | ||
| 6 | 1 | 2 | 3 | 4 | 5 | 0 | 1 | 2 | 3 | 4 | 5 | 0 | ||
| 7 | 1 | 2 | 3 | 4 | 5 | 6 | 0 | 1 | 2 | 3 | 4 | 5 | ||
| 8 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 0 | 1 | 2 | 3 | 4 | ||
| 9 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 0 | 1 | 2 | 3 | ||
| 10 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0 | 1 | 2 | ||
| 11 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 0 | 1 | ||
| 12 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 0 |
| D
|
1
|
2
|
3 | 4 | 5 | 6 | 7 | 8 | 9 | 10
|
11
|
12 |
|
Left: D:1+i.12
|
| 1
|
1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | ||
| 2 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | ||
| 3 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | ||
| 4 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | ||
| 5 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | ||
| 6 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | ||
| 7 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | ||
| 8
|
0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | ||
| 9 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ||
| 10 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | ||
| 11 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | ||
| 12 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
The last table shows divisibility. For example, the 1s in the 6th column show the position of the 4 factors of 6. Therefore the sum of the sixth column tells how many factors 6 has, and similarly for each column. Thus:
+/0=(1+i.12)|/1+i.12 1 2 2 3 2 4 2 4 3 4 2 6
The last result gives the number of factors for each of the numbers 1 to 12. Therefore the expression 2=+/0=(1+i.12)|/1+i.12 determines which numbers are primes:
2=+/0=(1+i.12)|/1+i.12 0 1 1 0 1 0 1 0 0 0 1 0
This vector of 0s and 1s can be used to compress the vector 1+i.12 to finally pick out all of the primes up to 12:
(2=+/0=(1+i.12)|/1+i.12)#1+i.12 2 3 5 7 11
#19-26
There is a verb, p:, for generating primes. The expression p: n yields the nth prime, with the count starting at 0. For example:
p:0 2 p:1 3 p:i.10 2 3 5 7 11 13 17 19 23 29
The monadic case of the verb q: returns a list of prime factors for any positive argument. The list is in increasing order, and each factor may be repeated so that */q:n yields n. For example:
q: 2 2 q: 3 3 q: 4 2 2 q: 6 2 3 q: 12 2 2 3 q: 10 2 5 q: 1 NB. 1 has no prime factors */q: 1 1 q: 1000 2 2 2 5 5 5
The dyadic case of q: returns a list of exponents for an initial set of primes. If x is positive and finite, x q: y is the list of exponents in the prime decomposition of positive integer y, based upon the first x primes; if x is _ , a sufficient number of primes is used. In this case, t=.p:i.#_q:y yields the initial sequence of primes of appropriate length, so that */t^(_ q: y) yields y. For example:
4 q:*/2 3 7 1 1 0 1 3 q:*/2 3 7 1 1 0 ]t=._ q:13 0 0 0 0 0 1 p: i.#t 2 3 5 7 11 13 (p:i.#t)^t 1 1 1 1 1 13 */(p:i.t)^t 13 (p:i.t)*/ .^t 13
#27
There has been error in communication with booki server. Not sure right now where is the problem.
You should refresh this page.
