Is No One Rational?

I ran into a math subproblem in the course of a bigger problem. I thought I'd give the Internet a shot before posting the answer. Here it is:

Show that for any finite set of positive real numbers, there must exist some number x such that x times each of the numbers in the set produces an irrational number.

Or rephrased:

If n runners start out together on an infinite race, each at a constant speed, which is different from the others' speeds, show that at some time each one will be an irrational distance from the start line.

Just a reminder: irrational numbers are those that cannot be written as a fraction a/b with a and b both whole numbers.

The Factorial Base

We've all heard of binary and decimal as systems to represent integers. The idea is simple: In the decimal number 328, 3 reflects three hundreds, 2 reflects two tens and the 8 adds in eight ones.

The same number is 101001000 in binary. Specifically, one 256, one 64 and one 8. 256, 64 and 8 are the eighth, sixth and third powers of two, and those occur as ones that many spaces over from the right side of the number.

Clearly, numbers are longer in binary than they are in decimal, but the digits are much simpler in binary. If all we cared about was reducing the number of digits, we could use base 20, or 2008 or the largest number we could think of.

Of course the tradeoff that comes is that it can be hard to make up and keep straight all the extra digits we would need. For example, the decimal number 1330 only needs three digits in base 11, but each of those digits is the digit "10", because 1330 = 10 * 11² + 10 * 11 + 10. How would we write this? One option is the hexadecimal system where 10 is a, 11 is b and so on. Then 1330 (base 10) = aaa (base 11). We can take this all the way up to base 36 using all 26 letters, in which case a long decimal number like 2621102907451 (base 10) compacts down to xg48zv3v (base 36).

But for a small number like 10, it seems unreasonable to write it as "a" just to save one digit. What if there was some way to have small digits for small numbers and compact representations for large numbers? It turns out there is a way to do this using the "factorial base" or "factoradix".

In factoradix, the rightmost digit is base 2, the next one is base 3, and so on. As an example, here's how you would calculate the factoradix notation for 99:

First we notice that 99 gives a remainder of 1 when divided by 2. The quotient is 49. We keep both of these numbers: 1 because it is the rightmost digit of the factoradix representation of 99 and 49 because we need it for the next steps. Next, 49 divided by 3 is 16 with remainder 1. So 1 is the next digit and so far we have _11 as our representation with the _ part still to be filled in (we can't know how many digits it will be, yet). Divide 16 by 4, quotient: 4, remainder: 0. Last, divide 4 by 5 to get a remainder of 4 and quotient of 0 (0 means the algorithm is finished). Combining all the remainders, 4011 ends up as the factoradix notation for 99. Longer yes, but with a simpler choice of digits.

We don't need to go through the details, but larger numbers make the opposite tradeoff in factoradix. A 1 with 47 zeros behind it becomes 4z7,h0x,ipf,5gr,0bc,l7l,977,460,068,952,315,551,220 which is only 39 digits long. A 1 with 100 zeros is only 69 digits long, but we need some way to encode digits like "58".

What do some more of these representations look like? First, the Perl function below encapsulates the algorithm above.

sub factoradix {
    my $n = shift;
    my $base = Math::BigInt->new(2);
    my (@digits, $digit);
    while ($n->bcmp(0)) {
        ($n, $digit) = $n->bdiv($base);
        unshift @digits, $digit->bstr();
        $base->binc();
    }
    return [ @digits ];
} 

Using this function, here's how the powers of ten start out in factoradix:
For 10⁰, we get 1
For 10¹, we get 120
For 10², we get 4,020
For 10³, we get 121,220
For 10⁴, we get 1,651,220
For 10⁵, we get 23,551,220
For 10⁶, we get 266,251,220
For 10⁷, we get 2,750,051,220
For 10⁸, we get 25,551,151,220
For 10⁹, we get 210,564,451,220
For 10¹⁰, we get 1,7a5,726,651,220
For 10¹⁵, we get 2d,caa,584,234,451,220
For 10²⁰, we get 1k2,13c,54a,a81,881,151,220
For 10²⁵, we get g2i,h8c,8f7,bc3,5b8,250,051,220
For 10³⁰, we get 3,7mf,cdg,584,64c,f8b,c01,182,251,220
For 10³⁵, we get c,4tr,pn8,9ef,g2b,d3f,34b,225,975,551,220
For 10⁴⁰, we get x,tkt,18i,jep,8bh,g9j,f7e,1bb,652,056,651,220
For 10⁶⁴, we get g,lqd,ila,9ii,ju0,a5m,bas,91k,7l5,m66,1ii,4h5,462,7a5,726,651,220

Every power of ten larger than 10⁶⁴ seems to use a digit that we don't have a letter for (and I checked up to 10¹⁴⁰⁰!). Of course, all we need to do is add more symbols, maybe hearts or that thing The Artist Formerly Known as Prince uses...

What do you think is the next factoradix question to investigate?

From the Outbox: a Balanced Diet

From: Me
Subject: Re: The 20 Worst Foods in America]
Date: March 1, 2008 5:44:56 PM CST
To: xxxxxxx@xxxxx.xxx


On Feb 29, 2008, at 9:48 AM, Xxxxx Xxxxxxx wrote:

> Thought this was interesting.

> Xxxxx

> > 1. The Worst Food in America
> > Outback Steakhouse Aussie Cheese Fries with Ranch Dressing

> >

> > 2,900 calories
> > 182 g fat 240 g carbs


Of course, there's nothing inherently wrong with calories taken out of context of all food one eats. The Outback Steakhouse Aussie Cheese Fries with Ranch Dressing is a perfect complement to some diet, somewhere. For instance, if the only other thing we ate was grasses and roots that we dug up on the hllls, the aussie cheese fries might balance it out nicely.

Clothing's destiny?

If you ran a shirt through the dryer sufficiently many times, would it eventually turn completely into lint?

The Computer Scientific Method

I was sent a presentation called How to Have a Bad Career in Research/Academia by David A. Patterson.

The best slide concerns the "Computer Scientific Method;" funny because it's true...

Physics Question: Leaky Inflatable Chair

At OSCON 2006, some O'Reilly developers and I were lounging in the expansive round upper-level of the Oregon Convention Center. It turns out that the someone had spread around a bunch of inflatable chairs which were molded after an overstuffed cushy easy chair.

Ryan Grimm had claimed a partially-deflated one. As I eyed it, I posed the following question:

Suppose that the air-filled chair had a pinhole leak on the side. Could it deflate faster depending on how you sat on it? In other words, would the air leave faster, slower or at the same rate if you spread your weight out as evenly as possibly in a wide slouch compared to if you stood on one foot and put all your weight on a few square inches?

I posed this to a handful of people, and none of them ever agreed with my answer. Maybe we can put this to rest now. What do you think and why?


Update with Legal Fine Print
All your weight is on the chair. You're not blocking the pinhole. In both scenarios, your weight is the same. The question is about over how wide of a space your weight is distributed.


Updated Example
You could rephrases this problem as something like:
"Will your inflatable mattress retain its pressure longer if you curl up in a cannonball or if you spread out like a pancake?"

Cookie Recipe

This recipe has served me well for the last 15 years.

3/4 cup butter
1 cup brown sugar
1/2 cup sugar
teaspoon vanilla
2 eggs
3 cups flour
1 teaspoon baking soda
1 teaspoon salt
2 cups chocolate chips

• The butter must be softened, but not melted. Melting it was a disastrous mistake I made a number of times.


• The line suggesting 1 teaspoon baking soda is a pack of lies. You must use at least 2.5 teaspoons.


• Don't overbake. I would tell you how long, but ovens vary so you will have to eyeball it.