Konstantin’s Weblog

Recognize your Primes

July 12, 2009 by zieglerk

After reading Tanya Khovanova’s Remember your Primes, I decided to do so. The description is due to John Conway.

Instead of memorizing all primes below 1000, it is easier to recognize composites:

1. Multiples of 2, 3, 5, 11 are easily detected.

2. Squares are known.

3. All that remains is to memorize 70 “non-trivial” composites (opposed to 168 primes in that range):

91, 119, 133, 161, 203, 217, 221, 247, 259, 287, 299, 301, 323, 329, 343, 371, 377, 391, 403, 413, 427, 437, 469, 481, 493, 497, 511, 527, 533, 551, 553, 559, 581, 589, 611, 623, 629, 637, 667, 679, 689, 697, 703, 707, 713, 721, 731, 749, 763, 767, 779, 791, 793, 799, 817, 833, 851, 871, 889, 893, 899, 901, 917, 923, 931, 943, 949, 959, 973, 989.

1. Remark:

If you are lazy, you can learn primes only up to 100. [...] [Y]ou need to remember only one number: 91.

2. Remark:

If you are very ambitious and plan to learn the primes up to 50,000, then the trick of learning non-trivial composites instead of primes is of no use to you. [...] The turning point is around 11,625: the number of primes below 11,625 equals the number of non-trivial composites below it.

3. As soon as you feel comfortable in the range below 1000 two more classes of composites become trivial to detect: Multiples of 7 and 13, since you can find the residue of a given number modulo 1001 by taking the alternating sum of three-digits.

Posted in math | Leave a Comment »

Verschlüsseln macht verdächtig

February 27, 2009 by zieglerk

Udo Vetter’s law blog cites under the title Verschlüsseln macht verdächtig from an interrogation transcript. [German]

Posted in res publica | Leave a Comment »

The “Broken Windows” Theory of Crimefighting

February 27, 2009 by zieglerk

Bruce Schneier’s blog post The “Broken Windows” Theory of Crimefighting quotes the article Breakthrough on ‘broken windows’ from The Boston Globe. Interesting information on what is effective — and what not.

Posted in res publica | Leave a Comment »

Question 4 from IMO 2008

February 24, 2009 by zieglerk

Problem: Find all functions $f: \mathbb{R}^{+} \to \mathbb{R}^{+}$ , s.t.

$\displaystyle \frac{f(w)^2 + f(x)^2}{f(y^2)+f(z^2)} = \frac{w^2+x^2}{y^2+z^2} \ \ \ \ \ (1)$

whenever $wx=yz$ . (Author: Hojoo Lee, South Korea)

Remark: Obvious solutions are $\mathop{id}: x \mapsto x$ and $\mathop{inv}: x \mapsto 1/x$ . We show, that those are also the only solutions.

Fact 1: $f(1) = 1$ .

Proof: Let $w=x=y=z=1$ .

Fact 2: $f(x^2) = f(x)^2$ .

Proof: Let $w=y=1$ and $x=z$ .

Using Fact 2, we can rewrite $(1)$ as

$\displaystyle \frac{f(w)+f(x)}{w+x}=\frac{f(y)+f(z)}{y+z} \ \ \ \ \ (2)$

whenever $wx=yz$ .

Fact 3: For every $x \in \mathbb{R}^{+}$

$\displaystyle f(x) = x \text{ or } f(x) = 1/x$ .

Proof: Let $w=x, y=1 \text{ and } z = x^2$ . Then $(2)$ implies

$\displaystyle \frac{2f(x)}{2x} = \frac{1+f(x)^2}{1+x^2}$

which is a quadratic equation for $f(x)$ with the two solutions $x$ and $1/x$ .

Fact 4 (

Non-mixing Lemma): If $f(x) = x$ for some $x \neq 1$ , then for all $x \in \mathbb{R}^{+}$ .

Proof: Assume $f(x) = x$ , for some $x \neq 1$ , but $f(w) \neq w$ for some $w \neq 1$ . By Fact 3, we know that in this case $f(w) = 1/w$ . We will show, that now the two possibilities for $f(xw)$ , i.e. $f(xw) = xw$ and $f(xw) = 1/(xw)$ both lead to contradictions.

Let $y=1$ and $z = x \cdot w$ . Then $(2)$ reads as

$\displaystyle \frac{1/w + x}{w+x} = \frac{1+f(xw)}{1+xw} \ \ \ \ \ (3)$ .

If $f(xw) = xw$ , this implies $w= 1$ . If $f(xw) = 1/(xw)$ this implies $x =1$ . Either way, a contradiction.

Posted in math | Leave a Comment »

A playful approach to the Moebius Function

January 25, 2009 by zieglerk

The Moebius Function $\mu$ of number theory seems to be defined in a rather artificial way:

$\mu (n) = 1$ if $n$ is the product of an even number of distinct primes,
$\mu (n) = -1$ if $n$ is the product of an odd number of distinct primes and
$\mu (n) = 0$ otherwise, i.e. if $n$ is not squarefree.

James Tanton gives a playful approach to $\mu$ in his article “An Illuminating Introduction to the Moebius Function”, MAA Focus, March 2007, P. 16-17. It starts with the following game: Imagine a row of 100 coins — all equal and all with heads up. Also imagine 100 players. The first player flips every coin. The second player flips every other coin, the third player every third coin, …, the $n$ th player flips every $n$ th coin. Now, the question arises: Which coins show tails up after 100 rounds? Amazingly, it is all those whose position is a perfect square.

This game is then generalized to a row of light bulbs where every light bulb can cycle through $k$ different states: $0, 1, ..., k-1$ and returns to state 0 after state $k-1$ . Imagine an infinite row of such light bulbs and face the following task: Which of the players (characterized above) do you have to send down the row (several ones certainly repeatedly) to set the first bulb into state $1$ and all others into state 0? Tanton then proves the following claim:

If the $n$ th player works the row $\mu(n)$ times (where we read $-1$ as $k-1$ ), then bulb 1 will be in state 1 and all others will be in state 0.

This approach also gives access to the multiplicity of the Moebius function and the Moebius inversion formula.

Posted in math | Leave a Comment »

China and the rest of the world

November 7, 2008 by zieglerk

Bruce Schneier’s blog post Surveillance in China brought the article China’s All-Seeing Eye by Naomi Klein in Rolling Stone to my attention. It is about lots more than china and well worth reading.

Posted in res publica | Leave a Comment »

Klein vs. Boy

October 1, 2008 by zieglerk

Recently, members of our group visited the imaginary exhibition in Cologne. When looking at the award-winning picture Still Life: Five Glass Surfaces on a Tabletop by Richard Palais and Luc Benard a discussion arose, as how to most easily distinguish a Boy’s Surface from a Klein Bottle. Assuming only basic knowledge about the construction of both of them this can be achieved by drawing the following series of diagrams which illustrates the construction of Boy’s Surface and finally comparing it to the analogous diagram for a Klein Bottle.

Posted in math | Leave a Comment »

how to determine the area under a curve

July 3, 2008 by zieglerk

tf called my attention on the paper A mathematical model for the determination of total area under glucose tolerance and other metabolic curves by MM Tai, pulished in Diabetes Care, Vol 17, Issue (2) 152–154. According to the abstract:

In Tai’s Model, the total area under a curve is computed by dividing the area under the curve between two designated values on the X-axis (abscissas) into small segments (rectangles and triangles) whose areas can be accurately calculated from their respective geometrical formulas. The total sum of these individual areas thus represents the total area under the curve. Validity of the model is established by comparing total areas obtained from this model to these same areas obtained from graphic method (less than +/- 0.4%). Other formulas widely applied by researchers under- or overestimated total area under a metabolic curve by a great margin.

This article has been cited by at least 35 other articles.

Posted in math | Leave a Comment »

“When are two proofs essentially the same?”

May 7, 2008 by zieglerk

Tim Gowers asks When are two proofs essentially the same?

For example, it is often possible to convert a standard inductive proof into a proof by contradiction that starts with the assumption that $X$ is a minimal counterexample.

He gives examples proving, that every natural number can be factored into primes and that $\sqrt{2}$ is irrational.

In the first case, you go from $n$ to $n+1$ or you assume a smallest number for which such a factorization does not exist and decide whether it is prime or composite. (In either case the induction hypothesis respectively the proof that the set of such numbers is non-empty are ommited.)

In the second case we assume for $\sqrt{2}$ a rational representation $\frac{p}{q}$ using either $p, q$ coprime or $p, q$ minimal, ending with a contradiction in either case.