Euler's Totient Script

RoboBOT · 2008-02-24 14:50:22

Hello all! I'd thought I'd contribute a script.
Euler's totient is the number of integers that are less than the value and coprime (no common factors).
It's useful in pseudorandom number generators, for example. I admit though, it's uses for the average game maker are limited.

I have two versions, but I'm pretty sure the first version listed is a lot faster:
Version 1:

Expand/*
**      eulers_totient(number);
**
**      argument0 = a postive real number
**
**  Returns the value of Euler's totient as a real number
**
**  Notes:
**      Euler's totient is how many coprime numbers there are
**      less than the inputted number.
**      Uses the function "factor(n)"
*/

var f,i,val,val_prev,et;
et=argument0;
val_prev=0;
f=factor(argument0);
ds_list_sort(f,true);
for (i=0;i<ds_list_size(f);i+=1) {
    val=ds_list_find_value(f,i);
    if (val!=val_prev) et*=(1-(1/val));
    val_prev=val;
}
ds_list_destroy(f);
return et;

Version 2:

Expand/*
**      eulers_totient(number);
**
**      argument0 = a postive real number
**
**  Returns the value of Euler's totient as a real number
**
**  Notes:
**      Euler's totient is how many coprime numbers there are
**      less than the inputted number.
**      Uses the function "gcd(n)"
*/
var i,et;
i=1;
et=0;
while (i<argument0) {
    if (gcd(i,argument0)=1) et+=1;
    i+=1;
}
return et;

By the way, if we donate a script to GMLscripts, may we also post the script on our own website? (Though I don't mean this script, since I made use of scripts from this site)

Last edited by RoboBOT (2008-02-24 19:20:25)

xot · 2008-02-24 16:47:35

These are interesting but I haven't the first clue about how to use them. smile If the first is fastest, I may decide to post both because the second works for unregistered GM users. I'm hoping Yourself or some other smart mathphile can chime in with a suggestion of how they can be used.

There are a couple things that should be addressed. In both scripts your variable declarations are a bit off. Also, you are using ; after } which doesn't really do anything, it's like an empty instruction.

By the way, if we donate a script to GMLscripts, may we also post the script on our own website? (Though I don't mean this script, since I make use of scripts from this site)

If it's your script, you can do whatever you want with it. You can repost any other scripts as well, but please reproduce them in their entirety.

RoboBOT · 2008-02-24 19:15:50

Yeah, I see the problems with my variable declarations. You mean I didn't declare et in the first script and declared c instead of et in the second, right? I fixed those.

Oh, and I'll remove the extraneous semicolons, if you prefer.

Last edited by RoboBOT (2008-02-24 19:19:11)

Yourself · 2008-09-23 02:10:29

I guess I missed seeing this. This script could actually be used to reduce large powers of some number module another. Euler's theorem states the following:

a^phi(m) === 1 (mod m)

if GCD(a, m) = 1.

That is, a to the phi(m) is congruent to 1 (mod m) where phi is Euler's totient function. For example:

Find the last two digits of 3^39 in base 10. Well, phi(100) = 40, so 3^40 === 1 (mod 100), so 3^-1 * 3^40 === 3^-1 (mod 100). So, we need only find the multiplicative inverse of 3 mod 100. 3*33 === -1 (mod 100) => 3*(-33) === 1 (mod 100) => 3*67 === 1 (mod 100), so the last two digits of 3^39 are 67.

Similarly the last two digits of the following are:

3^40 = 01
3^41 = 03
3^42 = 09...

Last edited by Yourself (2008-09-23 02:17:59)

brac37 · 2010-03-01 23:18:27

What about this if you do not have factor?

Expand/*
**      eulers_totient(number);
**
**      argument0 = a postive real number
**
**  Returns the value of Euler's totient as a real number
**
**  Notes:
**      Euler's totient is how many coprime numbers there are
**      less than the inputted number.
*/
var n,i,et;
n = argument0;
i=2;
et=1;
while (i <= n) {
    if (n mod i == 0) {
       et *= i - 1;
       n /= i;
       while (n mod i == 0) {
           et *= i;
           n /= i;   
       }
    }
    i+=1;
}
return et;

EDIT: script was incorrect. Corrected it.

Last edited by brac37 (2010-03-02 09:04:53)

GMLscripts.com

#1 2008-02-24 14:50:22

Euler's Totient Script

#2 2008-02-24 16:47:35

Re: Euler's Totient Script

#3 2008-02-24 19:15:50

Re: Euler's Totient Script

#4 2008-09-23 02:10:29

Re: Euler's Totient Script

#5 2010-03-01 23:18:27

Re: Euler's Totient Script

Board footer