projecteuler solution 112; added phi, ispermutation to common

3 files changed, 93 insertions, 0 deletions

diff --git a/src/projecteuler/112.c b/src/projecteuler/112.c
new file mode 100644
index 0000000..bb808be
--- /dev/null
+++ b/src/projecteuler/112.c
@@ -0,0 +1,45 @@
+
+int isbouncy(unsigned long n)
+{
+	char increasing=1, decreasing=1;
+	char lastdigit = n % 10;
+	n /= 10;
+
+	while(n > 0)
+	{
+		char digit = n % 10;
+		if(digit > lastdigit)
+			increasing = 0;
+		else if(digit < lastdigit)
+			decreasing = 0;
+
+		if(increasing == 0 && decreasing == 0)
+			return 1;
+
+		lastdigit = digit;
+		n /= 10;
+	}
+	return 0;
+}
+
+int main(void)
+{
+	unsigned long n = 100;
+	unsigned long bouncycount = 0;
+	double ratio;
+
+	while(1)
+	{
+		if(isbouncy(++n))
+			bouncycount++;
+
+		ratio = (double)bouncycount/n;
+		if(ratio == 0.99)
+			break;
+
+	}
+	printf("%ld\n", n);
+
+	return 0;
+}
+
diff --git a/src/projecteuler/common.c b/src/projecteuler/common.c
index 15ac8aa..52e5173 100644
--- a/src/projecteuler/common.c
+++ b/src/projecteuler/common.c
@@ -94,6 +94,52 @@ extern int isprime(unsigned long number, const unsigned long* primes)
 	return 0;
 }
 
+extern unsigned long phi(unsigned long n, unsigned long* primelist)
+{
+	double product = (double) n;
+	unsigned long i;
+
+	//if(isprime(n, primelist))
+	//	return n-1;
+
+	for(i=1; i<=primelist[0]; i++)
+	{
+		unsigned long p = primelist[i];
+		if(p > n)
+			break;
+		if(n % p != 0)
+			continue;
+		product *= (1 - 1.0/p);
+	}
+	return (unsigned long) product;
+}
+
+extern int ispermutation(unsigned long a, unsigned long b)
+{
+	char digits1[10];
+	char digits2[10];
+	memset(digits1, 0, 10);
+	memset(digits2, 0, 10);
+
+	while(a > 0 && b > 0)
+	{
+		char d1 = a % 10;
+		char d2 = b % 10;
+		digits1[d1]++;
+		digits2[d2]++;
+		a /= 10;
+		b /= 10;
+	}
+
+	if(a > 0 || b > 0)
+		return 0;
+
+	if(memcmp(digits1, digits2, 10) == 0)
+		return 1;
+
+	return 0;
+}
+
 /*int main()
 {
 	long* p = primes(10000);
diff --git a/src/projecteuler/common.h b/src/projecteuler/common.h
index 5889bb8..10b298e 100644
--- a/src/projecteuler/common.h
+++ b/src/projecteuler/common.h
@@ -3,5 +3,7 @@
 
 unsigned long* primes(unsigned long limit);
 int isprime(unsigned long number, const unsigned long* primes);
+unsigned long phi(unsigned long n, unsigned long* primelist);
+int ispermutation(unsigned long a, unsigned long b);
 
 #endif // COMMON_H