/* totient.c: Calculates the Euler totient function, phi. 
 *
 *  By Terry R. McConnell
 *
 *                              Theory
 *
 *  Euler's totient function, phi(n), is defined as the number of natural
 *  numbers <= n which are relatively prime to n. (We count 1 as relatively
 *  prime to everything.) It is an extremely important function in number
 *  theory. For primes p it is clear from the definition that phi(p) = p - 1.
 *  For powers of a prime it also easy to see (use induction on n) that
 *  phi(p^n) = p^(n-1)(p-1). Thus, e.g, phi(125) = 100. For all other
 *  values phi can be computed by factoring n completely and using the
 *  following result:
 *
 *  Theorem: Phi is a multiplicative function, i.e., if (m,n) = 1 (relatively
 *  prime) then phi(mn) = phi(m)phi(n).
 *
 *  Perhaps the easiest proof is via group theory. It follows from the
 *  Chinese Remainder Theorem that the multiplicative group of invertible 
 *  integers modulo  mn, Z(mn), is isomorphic to the direct product Z(m)xZ(n).
 *  The result follows since the orders of these groups are given by the 
 *  totient function. 
 *
 *  For a proof of the version of the Chinese Remainder Theorem required,
 *  see Theorem 3.7 in H.M. Stark, An Introduction to Number Theory, 
 *  Markham, Chicago, 1970.
 *
 *  Our implementation is highly recursive and is motivated by the McCarthy
 *  conditional statement formalism. (See Marvin Minsky, Computation:
 *  finite and infinite machines, Prentice Hall, Englewood Cliffs, 1967,
 *  problem 10.7-1.)
 *
 *  We define phi(-n) = phi(n), and do not define phi(0).
 *
*/

/* compile: cc -o totient  totient.c

      Use -D_SHORT_STRINGS if your compiler does not support multiline
          string constants.

   Run totient -h for usage information.

*/


#include<stdio.h>
#include<stdlib.h>

#define VERSION "1.0"
#define USAGE "totient [ -h -v -- ] n"
#ifndef _SHORT_STRINGS
#define HELP "\ntotient [ -h -v --] n\n\n\
Find the Euler totient function of n, the number of k <= n such that\n\
k and n are relatively prime. (1 is relatively prime to everything.)\n\n\
--: Signal end of options so that negative n can be input. (Silly, since\n\
    we merely define phi(-n) = phi(n).)\n\
-v: Print version number and exit. \n\
-h: Print this helpful information. \n\n"
#else
#define HELP USAGE
#endif

/* my_gcd: return the greatest common divisor of a and b, or -1 if it
 * is not defined. (See also euclid.c for a standalone implementation
 * of my_gcd.) 
 * 
 */

static int my_gcd(int a, int b)
{
	int q,r,t;

	/* Normalize so that 0 < a <= b */
	if((a == 0)||(b == 0)) return -1;
	if(a < 0) a = -a;
	if(b < 0) b = -b;
	if(b < a){
		t = b;
		b = a;
		a = t;
	}

	/* Now a <= b and both >= 1. */

	q = b/a;
	r = b - a*q;
	if(r == 0) 
		return a;

	return my_gcd(a,r);
}

/* In conditional statement form, phi can be defined together with another
 * function of 2 variables we denote as phiphi. We have phi(n) = phiphi(n,2)
 * and phiphi(y,x) = if(x = y-1 then x else if( x|y then
 * 	if((x,y/x)=1 then phi(x)phi(y/x) else x phi(y/x)) else phi(y,x+1))))
 */

static int phiphi(int,int);
static int phi(int n)
{
	if(n<0)n=-n;
	/* handle a few trivial boundary cases */
	if(n<=1)return 0;
	if(n==2)return 1;
	if(n==3)return 2;
	return phiphi(n,2);
}

/* This only gets called with y >= 3 and y > x >= 2 */

static int phiphi(int y, int x)
{
	int z;

	if(x+1 == y)return x; /* phi(prime p) = p-1 */
	if((y%x)==0){
		if(my_gcd(x,z=y/x)==1)
			return phi(x)*phi(z); /* multiplicative property */
		else
			return x*phi(z); /* This is a tricky case. It may
					    happen when x is a prime such
					    that a power of x divides y. In
					    case y = p^n, phi(y) = p^(n-1)(p-1)
					   */
	}
	else return phiphi(y,x+1);
}

int
main(int argc, char **argv)
{
	int n;
	int j=0;

	/* Process command line */
	while(++j < argc){
		if(argv[j][0] == '-')
			switch(argv[j][1]){ 
				case '-':
					++j;
					break;
				case 'v':
				case 'V':
					printf("%s\n",VERSION);
					exit(0);
				case '?':
				case 'h':
				case 'H':
					printf("%s\n",HELP);
					exit(0);
				default:
					fprintf(stderr,"totient: unkown option %s\n",
						argv[j]);
					fprintf(stderr,"%s\n",USAGE);
					exit(1);
			}
		break;
	}

	if(j >= argc){
		fprintf(stderr,"totient: usage error.\n");
		fprintf(stderr,"%s\n",USAGE);
		return 1;
	}

	n = atoi(argv[j++]);
	if(n == 0){
		fprintf(stderr,"totient: not defined for n = 0.\n");
		return 1;
	}

	printf("phi(%d) = %d\n",n,phi(n));

	return 0;

}