Sunday, August 30, 2009

The virtues of 3435

Folklore tells us that there is no such thing as an uninteresting integer. For, would such uninteresting integers exist, there would certainly be a smallest among them. But being the smallest uninteresting integer is a very interesting property, hence we should not have found it. The only way around this conundrum is to conclude that every integer is interesting.

Well, today three thousand four hundred thirty five got a little more interesting. Besides having a nice decimal representation, this number also possesses the following curious property:

\[
3^3 + 4^4 + 3^3 + 5^5 = 3435
\]

The only numbers who have this property are 1 and 3435. I know this for a fact because an exhaustive computer search until \(10^{10}\) did not reveal any other then numbers mentioned above.
Furthermore, if \(n > 10^{10}\) then \(n > 9^9\log(n)\) for

\[
\frac{10^{10}}{\log(10^{10})} = \frac{10^{10}}{10} = 10^{9} > 9^{9}
\]

Now, define \(\theta(n) := \sum c_{i}^{c_{i}}\) where the \(c_{i}\) are the numerals that express \(n\) in base 10. Then it can be shown that \(9^{9}\log(n) > \theta(n)\).

Now we know that 3435 is the only nontrivial number with such a special property.

Saturday, August 15, 2009

Highly Palindromic Primes

Over at the μtoast the blogger Attila Oláh described an in interesting property of primes in Highly palindromic primes.

In his post Atilla explores the question "How palindromic is a prime number?". For a prime \(p\) he inspects all the representations in meaningful bases i.e. all bases from 1 to \(p-1\). Attila then counts the number of representations which are palindromes.

In the search for higly palindromic primes, Atilla lists 291721. It is a prime number which is palindromic in 16 bases. I found several highly palindromic primes which are palindromes in 17 bases, and one prime which is a palindrome in 18 bases.

The primes I found which are palindromes in 17 bases are: 950041, 960961, 1062601, 1108801. The prime which is a palindrome in 18 bases is: 1259701.

Which higly palindromic primes can you find?

Thursday, August 13, 2009

A Perl Quine

A quine, as popularized by Douglas Hofstadter, is a self-producing program. A program which, upon execution, will output its own source. I finally took the time to write a quine myself and in this blog I will explain my motivations. I have chosen Perl as the language to implement my quine in, although the ideas are language independent.

The first idea I had was something along the line of

#! /usr/bin/env perl

$program = <<'EOP';
#! /usr/bin/env perl

$program = <<'EOP';
#! /usr/bin/env perl

$program = <<'EOP';
.
.
.   
EOP

$program =~ s/^\t//g;
print $program;
EOP

$program =~ s/^\t//g;
print $program;
EOP

$program =~ s/^\t//g;
print $program;

It is an infinite program, so no computer could ever execute it. But it is a quine non the less. It essence is nicely depicted by the following picture.

In this picture the entire ensemble of points is similar to the ensemble with first point removed. (Depicted as a gray point.) The entire ensemble is representing the program, and the ensemble without the first point is the content of the $program variable.

But alas, it is infinite, and although the construction is appealing, it is a bit disappointing. So let's take an other try, staying as close to the original idea as possible. The greatest problem is the moment we start to fill the second $program variable. We been down that road and know it does not lead to anything practical. We will ignore the problem for now and finish our proposal like this.

#! /usr/bin/env perl

my $program = <<'EOP';
#! /usr/bin/env perl

my $program = <<'EOP';
EOP

$program =~ s/^\t//g;
print $program;
EOP

$program =~ s/^\t//g;
print $program;

Now we are almost there. The only difference between the source and it's output is the part which is defined between the EOP markers. But this part is the value of the $program variable. So if we substitute the value of $program at the right place we are done.

The resulting program can be found on google code.

Sunday, August 2, 2009

Counting Unlock Patterns

In this blog post I will enumerate the number of unlock patterns of the andriod operating system.


Imagine a square array of points, arranged in a three by three formation. We set our selfs the task of tracing a path through a number of these points subjected to the following rules.

  1. No point can be visited twice.
  2. If a point obstructs an other point, the obstructing point should be visited first.

I will illustrate rule two with an example. Let's say we start our path in the lower left point of our arrangement. Our goal is the upper right point. If we would trace a pattern from our starting point to the target point we visit the center point, which should be included in our path.
Here is an other example which also illustrates rule one. Now our path starts in the center point and again our goal is the upper right point. Instead of directly going to our target we make a little detour via the lower left point. Because we started in the center point, it does not obstruct our goal any more and we can go directly to our goal, the upper right point.

This lengthy explanation is in fact a description of the android unlock pattern. Being a proud owner of a android phone I pondered about the question: "How many unlock patterns are possible". So I set out and wrote a little script to enumerate the different unlock patterns.

The following tables summarizes my findings. The first column list the path lengths. The second column list the corresponding number of unlock patterns. So there is a total of 389498 unlock patterns.



Pattern length#Patterns
01
19
256
3320
41642
57152
626016
772912
8140704
9140704

The most important section of code is displayed here below. It recursively builds a tree of patterns which can be inspected via a visitor. Check out the source if you like.

def generate(self):
for patternElement in self.possible:
nextPossible = self.possible.copy()
nextPossible.remove(patternElement)

if (self.reachable(patternElement)):
child = PatternTree(self,patternElement,nextPossible)
self.children.add(child)
child.generate()