summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--euler120.c24
-rw-r--r--euler72.c35
-rwxr-xr-xeuler72_alt_slow.sh20
3 files changed, 79 insertions, 0 deletions
diff --git a/euler120.c b/euler120.c
new file mode 100644
index 0000000..48e63e6
--- /dev/null
+++ b/euler120.c
@@ -0,0 +1,24 @@
+#include <stdio.h>
+
+/* (a-1)^n + (a+1)^n mod a^2
+ * = n*a*(-1)^(n-1) + (-1)^n + n*a + 1
+ * = na*[(-1)^(n-1)+1] + (-1)^n + 1
+ * = if (n is odd) 2na else 2
+ */
+
+int rmax(int a)
+{
+ int n = a / 2;
+ if (a % 2 == 0)
+ n--;
+ return 2 * n * a;
+}
+
+int main()
+{
+ int sum = 0;
+ for (int a = 3; a <= 1000; a++)
+ sum += rmax(a);
+ printf("%d\n", sum);
+}
+
diff --git a/euler72.c b/euler72.c
new file mode 100644
index 0000000..d62c508
--- /dev/null
+++ b/euler72.c
@@ -0,0 +1,35 @@
+#include <stdio.h>
+
+int euler_phi(int n)
+{
+ int phi = n;
+
+ if (n % 2 == 0) {
+ while (n % 2 == 0)
+ n /= 2;
+ phi /= 2;
+ }
+
+ for (int i = 3; i*i <= n; i++) {
+ if (n % i == 0) {
+ while (n % i == 0)
+ n /= i;
+ phi /= i;
+ phi *= (i-1);
+ }
+ }
+
+ if (n > 1)
+ phi = phi / n * (n-1);
+
+ return phi;
+}
+
+int main()
+{
+ long long cnt = 0;
+ for (int i = 2; i <= 1000000; i++)
+ cnt += euler_phi(i);
+
+ printf("%lld\n", cnt);
+}
diff --git a/euler72_alt_slow.sh b/euler72_alt_slow.sh
new file mode 100755
index 0000000..3a8514e
--- /dev/null
+++ b/euler72_alt_slow.sh
@@ -0,0 +1,20 @@
+#!/bin/bash
+
+euler_phi() {
+ prime_factors=($(factor $1 | cut -d ' ' -f2- | tr ' ' '\n' | sort -u))
+ t=$1
+ for i in ${prime_factors[@]}
+ do
+ t=$(($t/$i*($i-1)))
+ done
+ echo $t
+}
+
+sum=0
+i=2
+while [[ $i -le 1000000 ]]
+do
+ sum=$(($sum+$(euler_phi $i)))
+ i=$(($i+1))
+done
+echo $sum