## Monday, August 24, 2009

### Serendipity 1.4.1 and blank post content fixed by voodoo!

After upgrading to Serendipity 1.4.1 (the software this blog used to run on), I noticed that sometimes a really lengthy post would get blanked out for no apparent reason. So, I rolled up my sleeves and futzed around with some PHP, and didn't come up with anything substantial. However, I noticed that when the nl2br plugin was enabled, my post would be blank. This prompted me to attempt some voodoo magic (read: trial and error).

I went to Administration -> Appearance -> Configure Plugins -> NL2BR, and looked for "A list of HTML-tags where no breaks shall be converted". This text field contained data like this:

ul,ol,li,p,code,textarea


I changed it to this:

pre,ul,ol,li,p,textarea


Now call me a witch doctor, because now my long posts don't get cut off.

## Friday, August 14, 2009

### Project Euler #188: The hyperexponentiation of a number

A friend of mine recently got me interested in problem 188 in Project Euler. I had given it a cursory glance before, but I didn't realize that I already possessed all the tools needed to solve it. In fact, all that's needed is some elementary number theory. I'll get started on a method to solve the problem, but I won't finish it, so the reader may enjoy the experience of solving the problem himself/herself.

To begin with this problem, the concept of order must be defined for two integers a and m where $$gcd(a, m) = 1$$.

$$ord_{m}a$$ is the least positive integer $$e$$ such that $$a^e \equiv 1 \pmod{m}$$.

But just because we have defined $$e$$ like so, it does not mean $$e$$ always exists. That must be proven.

# Proposition 1

If $$gcd(a, m) = 1$$, then $$ord_{m}a$$ always exists.

# Proof

Let $$a$$, $$k$$, $$m$$ be positive integers with $$gcd(a, m) = 1$$. Now let $$E_{m}=\{k\ |\ a^k \equiv 1 \pmod{m}\ \}$$. Since $$gcd(a, m) = 1$$, we have by Euler's theorem that $$a^{\phi(m)} \equiv 1\pmod{m}$$, where $$\phi(m)$$ is Euler's totient function. Since $$\phi(m) \in E_{m}$$, the set is non-empty, and therefore contains a least element by the well ordering principle. This least element is $$ord_{m}a$$.

# Proposition 2

$$a^k \equiv 1 \pmod{m}$$ if and only if $$e|k$$ where $$e = ord_{m}a$$.

# Proof

For the forward direction first suppose $$a^k \equiv 1 \pmod{m}$$. Then $$k=eq+r$$ with $$e > 0$$ and $$0 \le r < e$$ by Euclid's division lemma.

Therefore:

$$a^k \equiv a^{eq+r} \equiv a^{eq}a^r \equiv a^{r}a^{eq} \equiv a^{r}(1)^q \equiv a^r \equiv 1 \pmod{m}$$

Now, since $$e$$ is, by definition, the least positive integer such that $$a^e \equiv 1 \pmod{m}$$, if $$r < e$$ and $$a^r \equiv 1 \pmod{m}$$ as well, it must be the case that $$r = 0$$. Therefore, $$k = eq+r = eq+0 = eq$$, implying $$e|k$$. For the opposite direction, suppose that $$k=eq$$. Then: $$a^k \equiv a^{eq} \equiv (a^e)^q \equiv 1^q \equiv 1 \pmod{m}$$.

# Proposition 3

$$a^i \equiv a^j \pmod{m}$$ if and only if $$i \equiv j \pmod{e}$$, where $$e = ord_{m}a$$.

# Proof

Since $$gcd(a, m) = 1$$, $$gcd(a^k, m) = 1$$ as well. Therefore, $$a^k$$ must have a modular inverse; and in particular, so does $$a^j$$:

$$a^i \equiv a^j \pmod{m}$$
$$a^{i}a^{-j} \equiv a^{j}a^{-j} \pmod{m}$$
$$a^{i-j} \equiv a^0 \pmod{m}$$
$$a^{i-j} \equiv 1 \pmod{m}$$

Since $$a^{i-j} \equiv 1 \pmod{m}$$, it must be the case that $$e|i-j$$ by the proposition #2. Therefore $$i-j = eq$$, or $$i = eq + j$$. It follows that $$i \equiv j \pmod{e}$$.

For the other direction, assume that $$i \equiv j \pmod{e}$$, or that $$e|i-j$$. Then $$eq=i-j$$ and $$a^{eq} \equiv a^{i-j} \equiv 1 \pmod{m}$$. This implies that $$a^i \equiv a^j \pmod{m}$$.

Armed with this information it is much easier to solve #188.

# What is 3 ↑↑ 4 (mod 1000)?

This problem is asking for the last three digits of $$3 \uparrow\uparrow 4$$, and as expected, we don't need to explicitly calculate $$3 \uparrow\uparrow 4$$. Instead, we would rather find some $$j$$ such that $$3 \uparrow\uparrow 4 \equiv 3^j \pmod{1000}$$, where $$j$$ is some much smaller number. Luckily, the last proposition tells us that this $$j$$ satisfies $$j \equiv 3 \uparrow\uparrow 3 \pmod{ord_{1000}3}$$.

But now the problem remains to calculate $$3 \uparrow\uparrow 3 \pmod{ord_{1000}3}$$. But instead of calculating this directly, we would rather find some $$k$$ such that $$3 \uparrow\uparrow 3 \equiv 3^k \pmod{1000}$$, where $$k$$ is some much smaller number. Happily enough, we can apply the last proposition yet again, and discover that $$k$$ satisfies $$k \equiv 3 \uparrow\uparrow 2 \pmod{ord_{1000}3}$$.

But now $$3 \uparrow\uparrow 2 = 3^3$$, and this is rather easy to calculate (actual calculation left to the reader).

# Moving forward

The only thing that stands between the reader and solving problem 188 are the actual implementation. Some questions that remain to be asked include: "how does one calculate the $$ord_{m}a$$?", and "what is a good method for modular exponentiation?", etc. Although, the lazy reader may view this solution in Ruby.

## Sunday, August 2, 2009

### There exists no polynomial with integer coefficients that generates only primes

Thinking back to my post about Project Euler's problem #27, this result popped into my head again. It is somewhat relevant, but the topic escaped my mind before I finished writing the previous post.

Anyways, the proof is very very simple. Assume that, on the contrary, such a polynomial exists. Call it $$f(x)$$:

$$f(x) = a_{k}x^{k}+a_{k-1}x^{k-1}+ \ldots +a_{2}x^{2}+a_{1}x+a_0$$

By assumption, if $$b$$ is an integer, $$f(b)$$ is some prime $$p$$. Let $$t$$ be an integer; then $$b+tp$$ is also an integer, and $$f(b+tp)$$ should also be prime. We can rewrite $$f(b+tp)$$ as:

$$f(b+tp) = a_{k}(b+tp)^{k} + a_{k-1}(b+tp)^{k-1} + \ldots + a_2(b+tp)^2 + a_1(b+tp) + a_0$$
$$\hspace{4em} = a_kb^k + a_{k-1}b^{k-1} + \ldots + a_2b^2 + a_1b + a_0 + p \cdot g(t)$$

...where $$g(t)$$ is some polynomial in $$t$$. The above expression can further be simplified to:

$$f(b+tp) = f(b) + p \cdot g(t)$$
$$\hspace{4em} = p + p \cdot g(t)$$
$$\hspace{4em} = p \cdot (1 + g(t))$$

...giving the result that $$p$$ divides $$f(b+tp)$$. Given that $$f(b+tp)$$ is prime and $$p$$ divides it, we must have that $$p = f(b+tp)$$. Since $$t$$ is an arbitrary integer, it must be the case that $$f(x)$$ generates the prime $$p$$ infinitely many times.

This is a contradiction as $$f(x)$$ is a polynomial of degree $$k$$; it can take on the same value at most $$k$$ times.