MathJax

SyntaxHighlighter

Highlight

Custom CSS

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.