## Thursday, January 28, 2010

### Screen cheat sheet

Here's my screen cheat sheet. It's simultaneous incredibly useful and ridiculous to configure. Actually reminds me of my other favorite tool with this syndrome: vim.

# Configuration

I like to bind C-o instead of C-a for screen commands; I feel that C-o is easier for my old hands to hit. Here's the skinny on what goes inside that cryptic screenrc:

# Use C-o to issue commands to screen
escape ^Oo


I also bind F5 and F6 to previous and next window:

# F5 for previous window
bindkey -k k5 prev
# F6 for next window
bindkey -k k6 next


# SSH

To be able to use ssh-agent within screen, you'll need this in your screenrc:

setenv SSH_AUTH_SOCK $HOME/.ssh/screen_agent screen -t remote ssh-agent ssh-agent -a$SSH_AUTH_SOCK $SHELL  # Internal commands C-o " Shows a list of sessions. C-o w Shows name of session the lower left. C-o c Creates a new session. C-o d Detaches the current session. C-o A Names the current session. C-o n Cycle to next session. C-o p Cycle to previous session. C-o F Fit the session to the current terminal. C-o :quit Quit all running sessions. C-o S Open a new region in a session. C-o Enter a newly created region. C-o X Close a region in screen. C-o ] Enables copy mode for copying or scrolling; use PgUp, or PgDn, etc. Press to mark text for copying. Press again to copy the text. Press C-o ] again to paste.  # External commands screen -ls List sessions. screen -r Reattach a session. screen -r foo Reattach to foo. screen -S foo Create a screen named foo.  # Conclusion Clear as mud right? ### Project Euler #15: Lattice paths This is problem #15. This problem can be viewed as a multi-permutation of 20 L's and 20 R's where L means "go left" and R means "go right". This way, no searching is needed and the solution can be calculated directly as: $$\frac{(20 + 20)!}{20!20!}$$ ## Wednesday, January 27, 2010 ### Wmii Recently, I stopped using XFCE in favor of wmii. Everybody else in the office was using a tiling window manager and I just felt left out. My C-fu and Haskell-fu just isn't strong enough to worry about both language syntax and window manager configuration so both dwm and xmonad were out the door. I was quite pleasantly surprised that I could use whatever language (including bash) to configure wmii. As proof, here is a snippet from my wmiirc that controls what shows up in the status bar: status() { echo -n 'Wlan0:'$(/sbin/iwconfig wlan0 | sed 's/ /\n/g' | grep Quality) '| '
echo -n 'Temp:' $(~/.wmii-3.5/temp) '| ' echo -n$(acpi -b | sed 's/.*, \{0,2\}$$[0-9]\{1,3\}%$$,.*/Bat: \1/') '| '
echo -n \$(date +"%a %b %d %I:%M%p")
}


The temp script is something I wrote and placed in my .wmii-3.5 directory (incidentally, scripts placed in there will show up when pressing mod-a).

The commands for navigating between created windows is very familiar, as they are the same keys used for navigation in vim. Moving the windows is also the same; they just involve holding another modifier key. In addition, wmii is pretty good about which windows should be floating, and which windows should not be. I'm quite pleased with the switch.

# Autostart

One initial hurdle was that I was a little confused about how to autostart applications in wmii, but in retrospect I feel dumb because its ridiculously simple; just put the apps you want in your wmiirc. Here's what I have:

# Swap capslock and control
setxkbmap -option ctrl:swapcaps
# Set mouse acceleration to 1.0
xset m 1
# Run pidgin (if not already running)
[ "ps aux | grep pidgin | grep -v grep" =  "" ] && pidgin &


For some reason, my mouse acceleration starts out at 2, which is way too fast. And the last line is a trick to only run pidgin if it's not already running.

# Pidgin

Lastly, I just needed something to notify me if I had messages in pidgin because I no longer had a system tray or task bar. Installing the packages libnotify1 and pidgin-libnotify, along with turning on the libnotify and message notification plugins puts a little asterisk next to the tag where pidgin is when you receive a message. However, I've just been giving pidgin multiple tags so I don't miss messages.

# Conclusion

Critical result: HAPPY

## Monday, January 25, 2010

### Project Euler #3: Largest prime factor

First, some clarification: I'm referring to the process of finding a non-trivial factor of a number (not one, and not itself) when I speak of factorization. This is not the same as finding the prime power decomposition of a number.

These algorithms are presented as more fun alternatives for solving project euler problem 3, rather than a bland trial and error approach.

# Fermat's Factorization Method

Fermat's factorization method is quite simple and forms the basis for faster algorithms. It works like this: suppose you have an integer n to be factored, and it can be expressed as the difference of two squares:

$$n = a^2-b^2$$

Then n can easily be factored like so:

$$n = (a+b)(a-b)$$

Luckily enough, all odd integers can be written like this (proof left to the reader). The problem that remains is to find out how to express n as the difference of two squares, and this can be done quite easily. For example, one can start at $$a = \sqrt{n}$$ and incrementing, checking whether or not $$a^2-n$$ is a perfect square.

Unfortunately, this naive process can take longer than trial division, so I would not recommend it (for the interested reader; however, there are many ways to speed up this method).

A more clever method exists if the integer in question has relatively small factors; however, before introducing it, I have to discuss some notation:

# Division

The notation $$a|b$$ means "a divides b". In other words, there exists an integer c such that $$ac=b$$.

# Congruences

The notation $$a \equiv b \pmod{m}$$ means that $$m|a-b$$, or that "m divides the difference of a and b". The notation may be unfamiliar, so a small exercise may help. Take a gander at the following statement:

$$a \equiv r \pmod{m}$$ and $$0 \leq r < m$$ This means that r is the remainder when a is divided by m, which is a more familiar concept.

# Pollard's Rho Method

This approach works well for large odd numbers with small factors. The first step is to generate some random Diophantine polynomial, such as:

$$f(x)=x^2+a$$ where $$a\not=0,-2$$

Now generate a sequence of $${x_k}$$ such that:

$$x_{k+1} \equiv f(x_k) \pmod{m}$$, with $$k \ge 0$$

The goal is to find some small, non-trivial factor $$d$$ of $$n$$. Since there are exactly $$d$$ congruent classes modulo $$d$$, and $$d < n$$, the integers $$x_k$$ must become periodic (modulo $$d$$). That is, there must exist residues $$x_i$$ and $$x_j$$ such that $$x_i \equiv x_j \pmod{d}$$, where $$i < j$$. Therefore, the strategy is to choose $$x_0$$ and $$f$$ such that $$x_i \equiv x_j \pmod{d}$$, but $$x_i \not \equiv x_j \pmod{n}$$. If suitable values can be chosen, note that $$d | x_j - x_i$$ but $$n \not | x_j - x_i$$. This means that $$gcd(x_j - x_i, n)$$ is a non-trivial factor of $$n$$. Pretty clever huh? Notice that knowledge of the value of $$d$$ is not used to compute $$gcd(x_j - x_i, n)$$.

# Conclusion: Trial Division

Despite it all, my preference is for a simple approach: trial division with a pre-generated list of primes. Most Project Euler problems can be solved pretty quickly if you've got a big enough list; the only problem that remains is how to efficiently generate such a list...

## Saturday, January 23, 2010

### Project Euler #120: Square remainders

Here is the question:

Let r be the remainder when $$(a-1)^n + (a+1)^n$$ is divided by $$a^2$$.

For example, if $$a = 7$$ and $$n = 3$$, then $$r = 42$$: $$6^3 + 8^3 = 728 \equiv 42 \pmod{49}$$. And as $$n$$ varies, so too will $$r$$, but for $$a = 7$$ it turns out that $$r_{max} = 42$$.

For $$3 \leq a \leq 1000$$, find $$\sum r_{max}$$.

Actually this, is a very easy problem, solved using a formula you may have learned about in elementary school.

The formula mentioned is, of course, the binomial formula; the same one that forms Pascal's Triangle. If one simply expands $$(a-1)^n$$ and $$(a+1)^n$$ via the binomial formula, then adds them together, one sees that the odd terms cancel each other out.

Now:

When $$n = 1$$, the remainder modulo $$a^2$$ is just $$2a$$.

When $$n > 1$$, and $$n$$ even, it's easy to see that the remainder is $$2$$.

When $$n > 1$$, and $$n$$ odd, the remainder is $$2na$$.

It remains to do a search through values of n to find the maximum remainder. Here is a solution in Scala:

def f(a: Int) = {
def g(n: Int) = n match {
case 1 => 2 * a
case _ if n % 2 == 0 => 2
case _ => 2 * n * a
}
(1 to (2 * a)).map(g _)
.map(_ % (a * a))
.reduceLeft(_ max _)
}

println((3 to 1000).map(f _).reduceLeft(_ + _))


### Project Euler #26: Reciprocal cycles

Here is problem #26:

Insight into some elementary number theory will help shorten this search for the longest cycle.

It's better to start computing cycle lengths starting from 999 down because a number 1/n cannot have more than n repeating digits in its decimal expansion. To convince yourself of this, think about what is happening when you do long division. Suppose you calculating 1/7:

First you divide 1.0 by 7 and find the remainder. Computationally, this is the same as dividing 10 by 7, then multiplying the remainder by 10, dividing by 7 again, and so on. See the sequence of computations for calculating 1/7 below, written in this manner:

$$(1 * 10) / 7 = (1) * 7 + 3$$
$$(3 * 10) / 7 = (4) * 7 + 2$$
$$(2 * 10) / 7 = (2) * 7 + 6$$
$$(6 * 10) / 7 = (8) * 7 + 4$$
$$(4 * 10) / 7 = (5) * 7 + 5$$
$$(5 * 10) / 7 = (7) * 7 + 1$$
$$(1 * 10) / 7 = (1) * 7 + 3$$
$$(3 * 10) / 7 = (4) * 7 + 2$$

Notice that the parenthesized numbers on the right hand side are precisely the first few digits in the decimal expansion of 1/7 = .14285714... and further notice that:

$$1 * 10 \pmod{7} \equiv 10^1 \pmod{7}$$
$$3 * 10 \pmod{7} \equiv 10^2 \pmod{7}$$
$$2 * 10 \pmod{7} \equiv 10^3 \pmod{7}$$
$$6 * 10 \pmod{7} \equiv 10^4 \pmod{7}$$
$$4 * 10 \pmod{7} \equiv 10^5 \pmod{7}$$
$$5 * 10 \pmod{7} \equiv 10^6 \pmod{7}$$
$$1 * 10 \pmod{7} \equiv 10^7 \pmod{7}$$
$$3 * 10 \pmod{7} \equiv 10^8 \pmod{7}$$

As you can see, at the next to last step, the digits start to repeat. In fact, the number of repeating digits is given by $$e = ord_{10}n$$, where $$e$$ is the smallest positive integer such that $$10^e \equiv 1 \pmod{n}$$. The preceding is not a proof of this fact, but hopefully is convincing enough.

I have written another blog post about calculating order, so please refer to that if needed. Finally, here is a Ruby program exploiting this info:

class Array
def tail
self.drop(1)
end
end

def order(a, m)
b = 1
(1...m).each do |i|
b = (a*b)%m
return i if b == 1
end
end

def max_period(best, numbers)
return best if numbers.nil?
n = numbers.first
ord = order(10, n)
return [n, ord] if ord == n - 1
return max_period([n, ord], numbers.tail) if ord > best.last
return max_period(best, numbers.tail)
end

numbers = 999.step(2, -1).select { |n| n % 2 != 0 && n % 5 != 0 }
result = max_period([0, 0], numbers)
puts result.first


### Project Euler #24: Lexicographic permutations

Here is the question:

A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:

012 021 102 120 201 210

What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

Only an elementary understanding of combinatorics is required to solve this problem by hand. Start with the smallest possible digit (0 in this case), then find the number of permutations of the remaining digits. If this number is less than 1000000, then 0 cannot be the first digit in the 1000000th permutation.

Try 1 instead, and count the number of permutations. Keep going with 2, 3, 4, etc until the number of permutations exceeds 1000000. Suppose that fixing the first digit at $$k$$ results in more than 1000000 permutations; this means the first digit is fixed at $$k-1$$, and the second digit must be examined by this method.

A diligent Project Euler enthusiast can execute this method by hand, but here is a simple program written in Scala that demonstrates this method:

val digits = List(0,1,2,3,4,5,6,7,8,9)
val target = 1000000

def fact(n: Int): Int = {
def recur(n: Int, acc: Int): Int = if (n == 1) acc else recur(n-1, n*acc)
if (n == 0) 1 else recur(n, 1)
}

def compute(list: List[Int]): List[Int] = {
def recur(list: List[Int], current: Int): List[Int] = {
val permutations = fact(list.length - 1)
val index = (target - current) / permutations
val digit = list(index)
val next = current + index * permutations
list.length match {
case 2 if target - current == 0 => list
case 2 if target - current == 1 => list.reverse
case _                          => digit :: recur(list - digit, next)
}
}
recur(list, 1)
}

val result = compute(digits).mkString("")
println(result)


### Wmii: Dealing with a lack of xrandr support

I use wmii on my EeePC, which is frequently connected to and disconnected from an external monitor. Earlier I posted about how to get my DPI under control using two monitors, but a different issue I had was with wmii and the lack of xrandr support. When I plug in the external monitor, I get a lot of extra screen real estate, but the status bar stays in the same place instead of moving to the bottom of the screen to take advantage of that extra real estate.

The unhappy workaround to this problem is to place this in your .xsession:

while true; do
wmii
done


If you do this and login via gdm by selecting "XClient script" as your session, you can quit wmii without stopping X. This will re-launch wmii and all your windows will be retagged. Not optimal, but it will do for now.

### Netbeans 6.8: Enable anti aliasing in fonts

So many GUI options and no checkbox to enable this. Awesome.

Edit etc/netbeans.conf in the Netbeans install directory and add this to netbeans_default_options:

-J-Dswing.aatext=true