Category Archives: Bongos

Evenness in Odd Bases

Everyone knows how to test for evenness: just check the last digit. If it’s in \{0,2,4,6,8\} then the number is even, no matter what other digits it has. This rule works in base 10 but not in base 3. In fact, this rule works in all even bases and fails in all odd bases. Why? And how do we test for evenness in odd bases?

Before we go into the details I want to ask two favors. First, if you are a math person, please forgive my sloppy use of terminology and typesetting; I have read very little math and written less. Second, for those who don’t already know the trick in odd bases: please don’t try to get the answer by inspection and intuition. Many people will find it easy to spot the pattern in a series of numbers. The treasure in this post is not the simple trick we learn for testing evenness, but the journey following the reasoning that proves that the trick works. So don’t even think about pondering a series of odd numbers because you’ll miss the journey of the proof.

Okay, let’s get the terminology and notation down before we start. Base 10 means we represent all numbers using only ten digits: 0-9. (Another word for base is radix.) Normally we write and read numbers in the decimal system which uses base 10 but any whole number can be used as a base: 2, 3, 10, 60, etc. When we represent numbers in different bases we place the number in parentheses followed by the base in subscript.


When we omit the subscript, the base is assumed to be 10. It’s important to have this notation because similar numbers have different values in different bases. For example, the three-digit number 100 represents one hundred in base 10.

(100)_{10} = 1\times10^2 + 0\times10^1 + 0\times10^0 = 100

In base 2 those digits represent a value of four.

(100)_2 = 1\times2^2 + 0\times2^1 + 0\times2^0 = 4

In base 3 the same three digits represent nine.

(100)_3 = 1\times3^2 + 0\times3^1 + 0\times3^0 = 9

That covers all of the technical lingo we need for this journey so let’s start.

First, let’s see why the evenness test is so easy in even bases. Evenness is just divisibility by 2. So let’s review how numbers and bases work. A number is the sum of its parts, which are its digits multiplied by their place values. We add 100 and 20 and 3 to get 123.

123 = 100 + 20 + 3 = 1\times10^2 + 2\times10^1 + 3\times10^0

Whatever is in the tens place, its value will be a multiple of ten. Two is a factor of ten. Two is therefore a factor of any whole multiple of ten. Adding an even number (a multiple of two) to any number X can not change the evenness of X. So it makes no difference how many tens or hundreds or thousands we add; the units place alone determines whether the number is divisible by 2. This is true in all even bases, not just 10. We can illustrate this by writing 123 in bases 8, 6, 4 and 2.

123 = (173)_8 = (323)_6 = (1323)_4 = (1111011)_2

In each of the above representations of 123, the digit in the units place is an odd number. That’s enough information to settle the question of evenness. It doesn’t matter that we don’t immediately recognize the that (1232_4) = 123; we can tell that it’s even just by checking the last digit.

Now let’s see what happens when we rewrite 123 in a few odd bases.

123 = (146)_9 = (234)_7 = (443)_5 = (4120)_3

The last digit can be even or odd but we know these numbers are all odd. Clearly the units place is not a reliable indicator of evenness. Why not? Because the radix is odd, multiples of the radix can be odd or even. Therefore the digits in the other places are capable of holding odd or even values. So our evenness test must consider all of the digits of the number.

Let’s remember how digits work together to make a number: they are added together. How does addition affect evenness? Adding an even number has no effect, but adding an odd number to X reverses the evenness of X. Adding two odds makes an even. Extending this, adding an even number of odds makes an even.

How does this help us? Well, every product of two odd numbers is itself odd. This is true because odd numbers are defined by the lack of 2 in its prime factorization. It also applies to powers of odd numbers. No matter how many times you multiply 3 by itself, the result is odd. So we know that each and every place value in an odd base is odd because it is a power of an odd number. This gives us the last clue we need for our trick: every even digit adds an even number, while every odd digit adds an odd number to the total.

The trick, then, finally, is to count the number of odd digits in the number, ignoring any evens. If the number of odd digits is even, all of the oddness cancels out and the number is even. If the number of odd digits is odd, the number is odd.

While the odd-based evenness test may lose to the even-based test on the grounds of speed (inspecting every digit instead of just one) and on the grounds of usefulness (does anyone use odd bases for anything, ever?) I find it much more satisfying because I can derive it myself.

If you found this little journey interesting, others divisibility tricks also have parallels in other bases. Take the trick for 9: if the digits sum to 9, the number is divisible by 9. This works in base 10 because 9=10-1. The same trick works in base 8: if the digits sum to 7, the number is divisible by 7. In general terms, if the digits sum to radix - 1, the number is divisible by radix - 1. I haven’t derived the proof for that one yet.

Let me know if you would like this kind of thing better as a vihart-style video.

Credit goes to Zoe Skelton for helpful feedback prior to publication.


How to Read Tech News

News should be read with global context and broad perspective. When you blend Techmeme headlines with Voice Of America it’s hard to get so excited about rounded corners and iPads. Try it:

Techmeme & Voice Of America

Too often we configure our news experience to focus on the safe and the comfortable. Blinders are fine until you forget that you put them on yourself. Remember to take them off sometimes and look around.

With Which to Psychoanalyse Julian Assange

Selections from Rubberhose.

Our journey begins with example code from the style guide showing a preoccupation with sex, drugs, and jail time:

	enum myheadhurts {lsd, mda, mdma, thc, peyote, women};


	if (foo1 &&
	    boo1 &&
	    (sex1 && sex2))


	if (chdir("/home/lolita" == 0)


		struct hurricane
			int years;
			char sex;
			int parole;


This instructional snippet encodes a government conspiracy:

	== frazer.c ==

	bool CIA_support = TRUE;

	static int campaign_fund;
	static int frazer_dollars:
	static char *frazer_mental_state = "hopeful";

		frazer_dollars -= bribe_kerr(frazer_dollars);
		campaign_find -= frazer_dollars/2;
		if (dismiss_govenment &&
		    strcasecmp(dismiss_action, "care-taker"))
			frazer_mental_state = "hot doggarty dog";


Before we dive into a colorful autobiographical narrative, two brief fantasies:

		onion routed block-device! yeah!
		  nb. time to lay off the weed


The story of naming the program is an entertaining read. These highlights shed light on the character of the author:

Guards. Guardians. The Greeks didn't have many with bite and I'm
loosing patience with the whole culture. Euphrosyne, Aglaia, and
Thalia do not grace me.  What I need is something that evokes
passion within my cryptographic domain. And when you come down to
it, that means something which produces copious amounts of gore
and blood, at will, from those who would dare to pass its demesne
of protection.


You had to hand it to Sigmund. He was nothing if not authoritative,
and after reading his inspiring words on the terrific serpent haired
woman, two things became clear to me. One, _Proffs_ and the Gorgon had
certain unresolved metaphorical incompatibilities and two, Sigmund was
clinically insane. I didn't want my software giving anyone a
castration complex, but I didn't want to give up snorting coke either.


If MARUTUKKU was my exquisite cryptographic good, of wit, effusive
joy, ravishing pleasure and flattering hope; then where was the
counter point? The figure to its ground - the sharper evil, the
madness, the melancholy, the most cruel lassitudes, disgusts and the
severest disappointments. Was Hume right? Because if he was, there was
only one organisation this string of hellish adjectives could
represent. The cryptographic devil with its 500,000 sq feet of office
space in Maryland. But surely there could be no reference to such an
organisation in the 4,000 year old Babylonian tablets.  The idea was
preposterous. Wasn't it?


ESIZKUR shall sit aloft in the house of prayer;
   May the gods bring their presents before him, that from
   him they may receive their assignments; none can without
   him create artful works.  Four black-headed ones are
   among his creatures; aside from him no god knows the
   answer as to their days.

It's a cold and wintry night here in Melbourne and the gusts of wind
and rain seem to be unusually chilling. What had I, in my search for a
cryptographic mythology, stumbled onto?

I look hard at the seven letters E-S-I-Z-K-U-R. A frown turns to
a smile and then a dead pan stare. I write down:



Finally, the quip that inspired me to compile these excerpts:

Some possible alternatives to passphrase based keying (we have some more
notes on these ideas, but no code or concrete design documentation):


	6) Colour contrast discrimination. It has been shown that individuals see
	   slightly different hues due to visual cortex and cone cell / retina
	   variation. It maybe possible to design moire or 
	   other tests on 24 bit displays which are recognisable by
	   one party but not another. Just hope no-one runs a magnet
	   over your monitor. Interestingly, one drug that this method is
	   highly likely to detect is Viagra, which intereacts with the retinal
	   environment to produce hue distortions. Rubberhose is naturally
	   arousing so we don't see this as being an issue.


Here ends an incomplete and unrepresentative picture intended for entertainment only. Cheers to you, Julian, for making life on Earth more entertaining. I wish you liberty.

p.s. I wonder how many encrypted aspects exist in the insurance file. You wouldn’t let one key unlock the whole file, spending all of your insurance at once. The first key must expose a little bit of data while leaving the bulk of it encrypted. If it contains anything as clever as a Rubberhose extent, one can never be certain whether the insurance policy has been exhausted.

p.p.s. Love the sig’:

Prof. Julian Assange  |If you want to build a ship, don't drum up people
                      |together to collect wood and don't assign them tasks          |and work, but rather teach them to long for the endless  |immensity of the sea. -- Antoine de Saint Exupery

Ketchup Calculus

Recently Heinz announced they have reformulated their tomato ketchup with about 15% less salt. Because they hold six tenths of the ketchup market, and because their recipe has not changed in nearly 40 years, this must have been a hard decision to make. They probably predicted some negative reactions. Why did they proceed?

Heinz altered their flagship product under pressure from politicians, but not yet under force of law. Here is an oversimplified economical argument for reformulating ketchup with less salt. Continue reading Ketchup Calculus

Interstate Commerce Abuse

Let’s make a deal. I am a private entity and you are a private entity. Can our transaction ever be called Commerce among States? Am I a State? Are you a State? No. We are private entities conducting a private transaction. Then what gives the Federal government the power to regulate our transactions? They claim that power derives from this clause:

[The Congress shall have the power] To regulate Commerce with foreign Nations, and among the several States, and with the Indian tribes;

Regardless of our communication or trading across State borders, this clause does not refer to us. It refers to recognized bodies of government: Nations, States, and Indian tribes. We are not governments. We are private entities.

If the United States Congress has the power to regulate my Commerce then I’m a State and I demand my own Representative and two Senators.

Nowhere does the Constitution give Congress the power to regulate our transaction. To quote the Tenth Amendment, that power is “reserved to the States respectively, or to the people.” If there exists a State law respecting our transaction then we must obey that law. No Federal law can apply to our transaction because we never gave Congress that power.

The only reason the State government should get involved is if one of the parties to a transaction (you or I) accuses the other of a wrong and seeks recourse. The Federal government has no power to regulate our private Commerce until one of us seeks recourse and there is a dispute among the States of jurisdiction, or until we seek recourse from the Federal government against the States.

I recognize that I have to share this great country with people who disagree with me. I’m just floating some ideas here. I am not a lawyer, a legislator, nor a legal scholar, but I sure disagree with a lot of Supreme Court decisions. At least a few Supreme Court justices have believed as I do. Sadly they were too few.

Omitted from this writing is any suggestion of how our Federal politicians could reform the current apparatus into one which operates correctly. That is a trick question because no politician would ever lift a finger to reduce their own power. Politicians are also incapable of that transgression against their brethren. And by “politicians” I mean the Legislative, the Executive, and the Judicial. All branches are complicit in the tendency to accumulate powers.

The only way to trim the Federal powers is by amending the Constitution. Such reform would be contrary to the interests of the majority of Federal politicians. Adversarial action must be done by adversaries. It can’t be done through Congress; it must be done to Congress by the States. The Constitution lights the way in Article Five:

The Congress, […] on the Application of the Legislatures of two thirds of the several States, shall call a Convention for proposing Amendments, which […] shall be valid to all Intents and Purposes, as Part of this Constitution, when ratified by the Legislatures of three fourths of the several States or by Conventions in three fourths thereof…

This is the only lawful and peaceful way to compel Congress. Every other road is slick with blood.

I welcome your opinion.