gcd / lcm / phi
| Definition: |
atom res = gcd(object u, atom v=0)
-- or -- atom res = lcm(object u, atom v=0) -- or -- integer res = phi(integer n) |
| Description: |
gcd() returns the greatest common divisor of two or more numbers. lcm() returns the lowest common multiple of two or more numbers. phi() returns Euler’s totient function, with memoisation. |
| pwa/p2js: | Supported. |
| Comments: |
The result is always a positive integer (that might still need storing in an atom), except for gcd(0,0) which is 0.
atom parameters allow greater precision, but any fractional parts are immediately and deliberately discarded. If the first parameter u is a sequence then the second parameter is completely ignored. Should it contain only one element, ie gcd({N}), then the result is floor(abs(N)). Should you be looking for hcf(), aka highest common factor, that’s the same as gcd() and is in fact aliased to that in psym.e and of course also in p2js. From Wikipedia/MathWorld: Euler’s totient function is not to be confused with the Euler function. In number theory, Euler’s totient function is the number of positive integers <= n that are relatively prime to n, ie do not contain any factor in common with n, where 1 is counted as being relatively prime to all numbers. In other words, it is the number of integers k in 1..n for which gcd(n,k)=1. The integers k of this form are sometimes referred to as totatives of n. It is written using the Greek letter phi as φ(n) or ϕ(n), and may also be called Euler’s phi function. For example, the totatives of n = 9 are the six numbers 1, 2, 4, 5, 7 and 8. They are all relatively prime to 9, but the other three numbers in this range, 3, 6, and 9 are not, since gcd(9,3) = gcd(9,6) = 3 and gcd(9,9) = 9. Therefore, φ(9) = 6. As another example, φ(1) = 1 since 1 is the only integer in the range 1..1, and gcd(1,1) = 1. Lastly, φ(p) = p-1 for all primes p (and only primes). Euler’s totient function is a multiplicative function, meaning that if two numbers m and n are relatively prime, then φ(mn) = φ(m)φ(n). |
| Examples: |
?gcd(-9,6) -- 3
?gcd(70000000000000000000, 60000000000000000000000) -- 10000000000000000000
?gcd({57,0,-45,-18,90,447}) -- 3
?gcd({-9.3}) -- 9
?gcd(21,14) -- 7 (21=3*7, 14=2*7)
?lcm(21,14) -- 42 (=2*21=3*14)
?lcm(3,4) -- 12
?lcm(4,6) -- 12
?apply(tagset(10),phi) -- {1,1,2,2,4,2,6,4,6,4}
|
| Implementation: | See builtins\gcd.e (an autoinclude) for details of the actual implementation. |