Euler's totient function
- Author:
- Juan Carlos Ponce Campuzano
- Topic:
- Numbers
Euler's totient function counts the positive integers up to a given integer n that are relatively prime to n.
Note: It works for n < 1015-1
This example uses JavaScript but it seems to be easier using just GGB script:
https://www.geogebra.org/m/mvxnxamm
1. Global JavaScript
function ggbOnInit() {}
// Euler's Totient Function
// https://en.wikipedia.org/wiki/Euler%27s_totient_function
// using Euler's product formula
function phi(n) {
// Initialize
// result as n
var result = n;
// Consider all prime
// factors of n and subtract
// their multiples from result
for (var p = 2; p * p <= n; ++p) {
// Check if p is
// a prime factor.
if (n % p == 0) {
// If yes, then
// update n and result
while (n % p == 0)
n = parseInt(n / p);
result -= parseInt(result / p);
}
}
// If n has a prime factor
// greater than sqrt(n)
// (There can be at-most
// one such prime factor)
if (n > 1)
result -= parseInt(result / n);
return result;
}
// This code is contributed
// by _saurabh_jaiswal
2. Basic Setup
n = 123456
phi = ?
Inp = InputBox(n)
SetCaption(Inp, "n = ")
text = "\phi(n) =" + phi
3. Create button named "Calculate" with JavaScript
var n = ggbApplet.getValue('n');
if ( n <= 0 )
ggbAppletevalCommand("SetValue(phi, ?)");
else if ( n === 1)
ggbApplet.setValue("phi", 1);
else ggbApplet.setValue("phi", phi(n));
4. Finally, add script in "n" on Update tab
RunClickScript( Calculate )