Archive for the ‘mathematics’ Category
A simple puzzle, with a foray into inequivalent expressions
[Needs cleanup… just dumping here for now.]
Mark Jason Dominus tweeted and later blogged about this puzzle:
From the four numbers [6, 6, 5, 2], using only the binary operations [+, -, *, /], form the number 17.
When he tweeted the first time, I thought about it a little bit (while walking from my desk to the restroom or something like that), but forgot about it pretty soon and didn’t give it much further thought. When he posted again, I gave it another serious try, failed, and so gave up and wrote a computer program.
This is what I thought this time.
Idea
Any expression is formed as a binary tree. For example, 28 = 6 + (2 * (5 + 6)) is formed as this binary tree (TODO make a proper diagram with DOT or something):
+ 6 * 2 + 5 6
And 8 = (2 + 6) / (6 – 5) is this binary tree:
/ + - 2 6 6 5
Alternatively, any expression is built up from the 4 given numbers [a, b, c, d] as follows:
Take any two of the numbers and perform any operation on them, and replace the two numbers with the result. Then repeat, until you have only one number, which is the final result.
Thus the above two expressions 28 = 6 + (2 * (5 + 6)) and 8 = (2 + 6) / (6 – 5) can be formed, respectively, as:
- Start with [6, 6, 5, 2]. Replace (5, 6) with 5+6=11 to get [6, 11, 2]. Replace (11, 2) with 11*2=22 to get [6, 22]. Replace (6, 22) with 6+22=28, and that’s your result.
- Start with [6, 6, 5, 2]. Replace (2, 6) with 2+6=8 to get [8, 6, 5]. Replace (6, 5) with 6-5=1 to get [8, 1]. Replace (8, 1) with 8/1=8 and that’s your result.
So my idea was to generate all possible such expressions out of [6, 6, 5, 2], and see if 17 was one of them. (I suspected it may be possible by doing divisions and going via non-integers, but couldn’t see how.)
(In hindsight it seems odd that my first attempt was to answer whether 17 could be generated, rather than how: I guess at this point, despite the author’s assurance that there are no underhanded tricks involved, I still wanted to test whether 17 could be generated in this usual way, if only to ensure that my understanding of the puzzle was correct.)
Multiple ways of understanding
In his wonderful On Proof and Progress in Mathematics, Thurston begins his second section “How do people understand mathematics?” as follows:
This is a very hard question. Understanding is an individual and internal matter that is hard to be fully aware of, hard to understand and often hard to communicate. We can only touch on it lightly here.
People have very different ways of understanding particular pieces of mathematics. To illustrate this, it is best to take an example that practicing mathematicians understand in multiple ways, but that we see our students struggling with. The derivative of a function fits well. The derivative can be thought of as:
- Infinitesimal: the ratio of the infinitesimal change in the value of a function to the infinitesimal change in a function.
- Symbolic: the derivative of is , the derivative of is , the derivative of is , etc.
- Logical: if and only if for every there is a such that when
- Geometric: the derivative is the slope of a line tangent to the graph of the function, if the graph has a tangent.
- Rate: the instantaneous speed of , when is time.
- Approximation: The derivative of a function is the best linear approximation to the function near a point.
- Microscopic: The derivative of a function is the limit of what you get by looking at it under a microscope of higher and higher power.
This is a list of different ways of thinking about or conceiving of the derivative, rather than a list of different logical definitions. Unless great efforts are made to maintain the tone and flavor of the original human insights, the differences start to evaporate as soon as the mental concepts are translated into precise, formal and explicit definitions.
I can remember absorbing each of these concepts as something new and interesting, and spending a good deal of mental time and effort digesting and practicing with each, reconciling it with the others. I also remember coming back to revisit these different concepts later with added meaning and understanding.
The list continues; there is no reason for it ever to stop. A sample entry further down the list may help illustrate this. We may think we know all there is to say about a certain subject, but new insights are around the corner. Furthermore, one person’s clear mental image is another person’s intimidation:
- The derivative of a real-valued function in a domain is the Lagrangian section of the cotangent bundle that gives the connection form for the unique flat connection on the trivial -bundle for which the graph of is parallel.
These differences are not just a curiosity. Human thinking and understanding do not work on a single track, like a computer with a single central processing unit. Our brains and minds seem to be organized into a variety of separate, powerful facilities. These facilities work together loosely, “talking” to each other at high levels rather than at low levels of organization.
This has been extended on the MathOverflow question Different ways of thinking about the derivative where you can find even more ways of thinking about the derivative. (Two of the interesting pointers are to this discussion on the n-Category Café, and to the book Calculus Unlimited by Marsden and Weinstein, which does calculus using a “method of exhaustion” that does not involve limits. (Its definition of the derivative is also mentioned at the earlier link, as that notion of the derivative closest to [the idea of Eudoxus and Archimedes] of “the tangent line touches the curve, and in the space between the line and the curve, no other straight line can be interposed”, or “the line which touches the curve only once” — this counts as another important way of thinking about the derivative.)
It has also been best extended by Terence Tao, who in an October 2009 blog post on Grothendieck’s definition of a group gave several ways of thinking about a group:
In his wonderful article “On proof and progress in mathematics“, Bill Thurston describes (among many other topics) how one’s understanding of given concept in mathematics (such as that of the derivative) can be vastly enriched by viewing it simultaneously from many subtly different perspectives; in the case of the derivative, he gives seven standard such perspectives (infinitesimal, symbolic, logical, geometric, rate, approximation, microscopic) and then mentions a much later perspective in the sequence (as describing a flat connection for a graph).
One can of course do something similar for many other fundamental notions in mathematics. For instance, the notion of a group can be thought of in a number of (closely related) ways, such as the following:
- Motivating examples: A group is an abstraction of the operations of addition/subtraction or multiplication/division in arithmetic or linear algebra, or of composition/inversion of transformations.
- Universal algebraic: A group is a set with an identity element , a unary inverse operation , and a binary multiplication operation obeying the relations (or axioms) , , for all .
- Symmetric: A group is all the ways in which one can transform a space to itself while preserving some object or structure on this space.
- Representation theoretic: A group is identifiable with a collection of transformations on a space which is closed under composition and inverse, and contains the identity transformation.
- Presentation theoretic: A group can be generated by a collection of generators subject to some number of relations.
- Topological: A group is the fundamental group of a connected topological space .
- Dynamic: A group represents the passage of time (or of some other variable(s) of motion or action) on a (reversible) dynamical system.
- Category theoretic: A group is a category with one object, in which all morphisms have inverses.
- Quantum: A group is the classical limit of a quantum group.
etc.
One can view a large part of group theory (and related subjects, such as representation theory) as exploring the interconnections between various of these perspectives. As one’s understanding of the subject matures, many of these formerly distinct perspectives slowly merge into a single unified perspective.From a recent talk by Ezra Getzler, I learned a more sophisticated perspective on a group, somewhat analogous to Thurston’s example of a sophisticated perspective on a derivative (and coincidentally, flat connections play a central role in both):
- Sheaf theoretic: A group is identifiable with a (set-valued) sheaf on the category of simplicial complexes such that the morphisms associated to collapses of -simplices are bijective for (and merely surjective for ).
The rest of the post elaborates on this understanding.
Again in a Google Buzz post on Jun 9, 2010, Tao posted the following:
Bill Thurston’s “On proof and progress in mathematics” has many nice observations about the nature and practice of modern mathematics. One of them is that for any fundamental concept in mathematics, there is usually no “best” way to define or think about that concept, but instead there is often a family of interrelated and overlapping, but distinct, perspectives on that concept, each of which conveying its own useful intuition and generalisations; often, the combination of all of these perspectives is far greater than the sum of the parts. Thurston illustrates this with the concept of differentiation, to which he lists seven basic perspectives and one more advanced perspective, and hints at dozens more.
But even the most basic of mathematical concepts admit this multiplicity of interpretation and perspective. Consider for instance the operation of addition, that takes two numbers x and y and forms their sum x+y. There are many such ways to interpret this operation:
1. (Disjoint union) x+y is the “size” of the disjoint union X u Y of an object X of size x, and an object Y of size y. (Size is, of course, another concept with many different interpretations: cardinality, volume, mass, length, measure, etc.)
2. (Concatenation) x+y is the size of the object formed by concatenating an object X of size x with an object Y of size y (or by appending Y to X).
3. (Iteration) x+y is formed from x by incrementing it y times.
4. (Superposition) x+y is the “strength” of the superposition of a force (or field, intensity, etc.) of strength x with a force of strength y.
5. (Translation action) x+y is the translation of x by y.
5a. (Translation representation) x+y is the amount of translation or displacement incurred by composing a translation by x with a translation by y.
6. (Algebraic) + is a binary operation on numbers that give it the structure of an additive group (or monoid), with 0 being the additive identity and 1 being the generator of the natural numbers or integers.
7. (Logical) +, when combined with the other basic arithmetic operations, are a family of structures on numbers that obey a set of axioms such as the Peano axioms.
8. (Algorithmic) x+y is the output of the long addition algorithm that takes x and y as input.
9. etc.
These perspectives are all closely related to each other; this is why we are willing to give them all the common name of “addition”, and the common symbol of “+”. Nevertheless there are some slight differences between each perspective. For instance, addition of cardinals is based on perspective 1, while addition of ordinals is based on perspective 2. This distinction becomes apparent once one considers infinite cardinals or ordinals: for instance, in cardinal arithmetic, aleph_0 = 1+ aleph_0 = aleph_0 + 1 = aleph_0 + aleph_0, whereas in ordinal arithmetic, omega = 1+omega < omega+1 < omega + omega.
Transitioning from one perspective to another is often a necessary first conceptual step when the time comes to generalise the concept. As a child, addition of natural numbers is usually taught initially by using perspective 1 or 3, but to generalise to addition of integers, one must first switch to a perspective such as 4, 5, or 5a; similar conceptual shifts are needed when one then turns to addition of rationals, real numbers, complex numbers, residue classes, functions, matrices, elements of abstract additive groups, nonstandard number systems, etc. Eventually, one internalises all of the perspectives (and their inter-relationships) simultaneously, and then becomes comfortable with the addition concept in a very broad set of contexts; but it can be more of a struggle to do so when one has grasped only a subset of the possible ways of thinking about addition.
In many situations, the various perspectives of a concept are either completely equivalent to each other, or close enough to equivalent that one can safely “abuse notation” by identifying them together. But occasionally, one of the equivalences breaks down, and then it becomes useful to maintain a careful distinction between two perspectives that are almost, but not quite, compatible. Consider for instance the following ways of interpreting the operation of exponentiation x^y of two numbers x, y:
1. (Combinatorial) x^y is the number of ways to make y independent choices, each of which chooses from x alternatives.
2. (Set theoretic) x^y is the size of the space of functions from a set Y of size y to a set X of size x.
3. (Geometric) x^y is the volume (or measure) of a y-dimensional cube (or hypercube) whose sidelength is x.
4. (Iteration) x^y is the operation of starting at 1 and multiplying by x y times.
5. (Homomorphism) y → x^y is the continuous homomorphism from the domain of y (with the additive group structure) to the range of x^y (with the multiplicative structure) that maps 1 to x.
6. (Algebraic) ^ is the operation that obeys the laws of exponentiation in algebra.
7. (Log-exponential) x^y is exp( y log x ). (This raises the question of how to interpret exp and log, and again there are multiple perspectives for each…)
8. (Complex-analytic) Complex exponentiation is the analytic continuation of real exponentiation.
9. (Computational) x^y is whatever my calculator or computer outputs when it is asked to evaluate x^y.
10. etc.
Again, these interpretations are usually compatible with each other, but there are some key exceptions. For instance, the quantity 0^0 would be equal to zero [ed: I think this should be one —S] using some of these interpretations, but would be undefined in others. The quantity 4^{1/2} would be equal to 2 in some interpretations, be undefined in others, and be equal to the multivalued expression +-2 (or to depend on a choice of branch) in yet further interpretations. And quantities such as i^i are sufficiently problematic that it is usually best to try to avoid exponentiation of one arbitrary complex number by another arbitrary complex number unless one knows exactly what one is doing. In such situations, it is best not to think about a single, one-size-fits-all notion of a concept such as exponentiation, but instead be aware of the context one is in (e.g. is one raising a complex number to an integer power? A positive real to a complex power? A complex number to a fractional power? etc.) and to know which interpretations are most natural for that context, as this will help protect against making errors when manipulating expressions involving exponentiation.
It is also quite instructive to build one’s own list of interpretations for various basic concepts, analogously to those above (or Thurston’s example). Some good examples of concepts to try this on include “multiplication”, “integration”, “function”, “measure”, “solution”, “space”, “size”, “distance”, “curvature”, “number”, “convergence”, “probability” or “smoothness”. See also my blog post below in which the concept of a “group” is considered.
I plan to collect more such “different ways of thinking about the same (mathematical) thing” in this post, as I encounter them.
The same in every country
(TODO: Learn and elaborate more on their respective histories and goals.)
The formula
(reminded via this post), a special case at of
was found by Leibniz in 1673, while he was trying to find the area (“quadrature”) of a circle, and he had as prior work the ideas of Pascal on infinitesimal triangles, and that of Mercator on the area of the hyperbola with its infinite series for . This was Leibniz’s first big mathematical work, before his more general ideas on calculus.
Leibniz did not know that this series had already been discovered earlier in 1671 by the short-lived mathematician James Gregory in Scotland. Gregory too had encountered Mercator’s infinite series , and was working on different goals: he was trying to invert logarithmic and trigonometric functions.
Neither of them knew that the series had already been found two centuries earlier by Mādhava (1340–1425) in India (as known through the quotations of Nīlakaṇṭha c.1500), working in a completely different mathematical culture whose goals and practices were very different. The logarithm function doesn’t seem to have been known, let alone an infinite series for it, though a calculus of finite differences for interpolation for trigonometric functions seems to have been ahead of Europe by centuries (starting all the way back with Āryabhaṭa in c. 500 and more clearly stated by Bhāskara II in 1150). Using a different approach (based on the arc of a circle) and geometric series and sums-of-powers, Mādhava (or the mathematicians of the Kerala tradition) arrived at the same formula.
[The above is based on The Discovery of the Series Formula for π by Leibniz, Gregory and Nilakantha by Ranjay Roy (1991).]
This startling universality of mathematics across different cultures is what David Mumford remarks on, in Why I am a Platonist:
As Littlewood said to Hardy, the Greek mathematicians spoke a language modern mathematicians can understand, they were not clever schoolboys but were “fellows of a different college”. They were working and thinking the same way as Hardy and Littlewood. There is nothing whatsoever that needs to be adjusted to compensate for their living in a different time and place, in a different culture, with a different language and education from us. We are all understanding the same abstract mathematical set of ideas and seeing the same relationships.
The same thought was also expressed by Mean Girls:
The generating function for Smirnov words (or: time until k consecutive results are the same)
1. Alphabet
Suppose we have an alphabet of size . Its generating function (using the variable to mark length) is simply , as contains elements of length each.
2. Words
Let denote the class of all words over the alphabet . There are many ways to find the generating function for .
2.1.
We have
so its generating function is
2.2.
To put it differently, in the symbolic framework, we have , so the generating function for is
2.3.
We could have arrived at this with direct counting: the number of words of length is as there are choices for each of the letters, so the generating function is
3. Smirnov words
Next, let denote the class of Smirnov words over the alphabet , defined as words in which no two consecutive letters are identical. (That is, words in which for all , and for any .) Again, we can find the generating function for in different ways.
3.1.
For any word in , by “collapsing” all runs of each letter, we get a Smirnov word. To put it differently, any word in can be obtained from a Smirnov word by “expanding” each letter into a nonempty sequence of that letter. This observation (see Analytic Combinatorics, pp. 204–205) lets us relate the generating functions of and as
which implicitly gives the generating function : we have
3.2.
Alternatively, consider in an arbitrary word the first occurrence of a pair of repeated letters. Either this doesn’t happen at all (the word is a Smirnov word), or else, if it happens at position so that , then the part of the word up to position is a nonempty Smirnov word, the letter at position is the same as the previous letter, and everything after is an arbitrary word. This gives
or in terms of generating functions
giving
3.3.
A minor variant is to again pick an arbitrary word and consider its first pair of repeated letters, happening (if it does) at positions and , but this time consider the prefix up to : either it is empty, or the pair of letters is different from the last letter of the prefix, giving us the decomposition
and corresponding generating function
so
which is the same as before after we cancel the factors.
3.4.
We could have arrived at this result with direct counting. For , for a Smirnov word of length , we have choices for the first letter, and for each of the other letters, as they must not be the same as the previous letter, we have choices. This gives the number of Smirnov words of length as for , and so the generating function for Smirnov words is
again giving
4. Words with bounded runs
We can now generalize. Let denote the class of words in which no letter occurs more than times consecutively. (.) We can find the generating function for .
4.1.
To get a word in we can take a Smirnov word and replace each letter with a nonempty sequence of up to occurrences of that letter. This gives:
so
4.2.
Pick any arbitrary word, and consider its first occurrence of a run of letters. Either such a run does not exist (which means the word we picked is in ), or it occurs right at the beginning ( possibilities, one for each letter in the alphabet), or, if it occurs starting at position , then the part of the word up to position (the “prefix”) is a nonempty Smirnov word, positions to are occurrences of any of the letters other than the last letter of the prefix, and what follows is an arbitrary word. This gives
or in terms of generating functions
so
giving
4.3.
Arriving at this via direct counting seems hard.
5. Words that stop at a long run
Now consider words in which we “stop” as soon we see consecutive identical letters. Let the class of such words be denoted (not writing to keep the notation simple). As before, we can find its generating function in multiple ways.
5.1.
We get any word in by either immediately seeing a run of length and stopping, or by starting with a nonempty prefix in , and then stopping with a run of identical letters different from the last letter of the prefix. Thus we have
and
which gives
5.2.
Alternatively, we can decompose any word by looking for its first run of identical letters. Either it doesn’t occur at all (the word we picked is in , or the part of the word until the end of the run belongs to and the rest is an arbitrary word, so
and
so
6. Probability
Finally we arrive at the motivation: suppose we keep appending a random letter from the alphabet, until we encounter the same letter times consecutively. What can we say about the length of the word thus generated? As all sequences of letters are equally likely, the probability of seeing any string of length is . So in the above generating function , the probability of our word having length is , and the probability generating function is therefore . This can be got by replacing with in the expression for : we have
In principle, this probability generating function tells us everything about the distribution of the length of the word. For example, its expected length is
(See this question on Quora for other powerful ways of finding this expected value directly.)
We can also find its variance, as
This variance is really too large to be useful, so what we would really like, is the shape of the distribution… to be continued.
Some playing with Python
A long time ago, Diophantus (sort of) discussed integer solutions to the equation
(solutions to this equation are called Pythagorean triples).
Centuries later, in 1637, Fermat made a conjecture (now called Fermat’s Last Theorem, not because he uttered it in his dying breath, but because it was the last one to be proved — in ~1995) that
has no positive integer solutions for . In other words, his conjecture was that none of the following equations has a solution:
… and so on. An nth power cannot be partitioned into two nth powers.
About a century later, Euler proved the case of Fermat’s conjecture, but generalized it in a different direction: he conjectured in 1769 that an nth power cannot be partitioned into fewer than n nth powers, namely
has no solutions with . So his conjecture was that (among others) none of the following equations has a solution:
… and so on.
This conjecture stood for about two centuries, until abruptly it was found to be false, by Lander and Parkin who in 1966 simply did a direct search on the fastest (super)computer at the time, and found this counterexample:
(It is still one of only three examples known, according to Wikipedia.)
Now, how might you find this solution on a computer today?
In his wonderful (as always) post at bit-player, Brian Hayes showed the following code:
import itertools as it def four_fifths(n): '''Return smallest positive integers ((a,b,c,d),e) such that a^5 + b^5 + c^5 + d^5 = e^5; if no such tuple exists with e < n, return the string 'Failed'.''' fifths = [x**5 for x in range(n)] combos = it.combinations_with_replacement(range(1,n), 4) while True: try: cc = combos.next() cc_sum = sum([fifths[i] for i in cc]) if cc_sum in fifths: return(cc, fifths.index(cc_sum)) except StopIteration: return('Failed')
to which, if you add (say) print four_fifths(150)
and run it, it returns the correct answer fairly quickly: in about 47 seconds on my laptop.
The if cc_sum in fifths:
line inside the loop is an cost each time it’s run, so with a simple improvement to the code (using a set instead) and rewriting it a bit, we can write the following full program:
import itertools def find_counterexample(n): fifth_powers = [x**5 for x in range(n)] fifth_powers_set = set(fifth_powers) for xs in itertools.combinations_with_replacement(range(1, n), 4): xs_sum = sum([fifth_powers[i] for i in xs]) if xs_sum in fifth_powers_set: return (xs, fifth_powers.index(xs_sum)) return 'Failed' print find_counterexample(150)
which finishes in about 8.5 seconds.
Great!
But there’s something unsatisfying about this solution, which is that it assumes there’s a solution with all four numbers on the LHS less than 150. After all, changing the function invocation to find_counterexample(145)
makes it run a second faster even, but how could we know to do without already knowing the solution? Besides, we don’t have a fixed 8- or 10-second budget; what we’d really like is a program that keeps searching till it finds a solution or we abort it (or it runs out of memory or something), with no other fixed termination condition.
The above program used the given “n” as an upper bound to generate the combinations of 4 numbers; is there a way to generate all combinations when we don’t know an upper bound on them?
Yes! One of the things I learned from Knuth volume 4 is that if you simply write down each combination in descending order and order them lexicographically, the combinations you get for each upper bound are a prefix of the list of the next bigger one, i.e., for any upper bound, all the combinations form a prefix of the same infinite list, which starts as follows (line breaks for clarity):
1111, 2111, 2211, 2221, 2222, 3111, 3211, 3221, 3222, 3311, 3321, 3322, 3331, 3332, 3333, 4111, ... ... 9541, 9542, 9543, 9544, 9551, ... 9555, 9611, ...
There doesn’t seem to be a library function in Python to generate these though, so we can write our own. If we stare at the above list, we can figure out how to generate the next combination from a given one:
- Walk backwards from the end, till you reach the beginning or find an element that’s less than the previous one.
- Increase that element, set all the following elements to 1s, and continue.
We could write, say, the following code for it:
def all_combinations(r): xs = [1] * r while True: yield xs for i in range(r - 1, 0, -1): if xs[i] < xs[i - 1]: break else: i = 0 xs[i] += 1 xs[i + 1:] = [1] * (r - i - 1)
(The else
block on a for
loop is an interesting Python feature: it is executed if the loop wasn’t terminated with break
.) We could even hard-code the r=4
case, as we’ll see later below.
For testing whether a given number is a fifth power, we can no longer simply lookup in a fixed precomputed set. We can do a binary search instead:
def is_fifth_power(n): assert n > 0 lo = 0 hi = n # Invariant: lo^5 < n <= hi^5 while hi - lo > 1: mid = lo + (hi - lo) / 2 if mid ** 5 < n: lo = mid else: hi = mid return hi ** 5 == n
but it turns out that this is slower than one based on looking up in a growing set (as below).
Putting everything together, we can write the following (very C-like) code:
largest_known_fifth_power = (0, 0) known_fifth_powers = set() def is_fifth_power(n): global largest_known_fifth_power while n > largest_known_fifth_power[0]: m = largest_known_fifth_power[1] + 1 m5 = m ** 5 largest_known_fifth_power = (m5, m) known_fifth_powers.add(m5) return n in known_fifth_powers def fournums_with_replacement(): (x0, x1, x2, x3) = (1, 1, 1, 1) while True: yield (x0, x1, x2, x3) if x3 < x2: x3 += 1 continue x3 = 1 if x2 < x1: x2 += 1 continue x2 = 1 if x1 < x0: x1 += 1 continue x1 = 1 x0 += 1 continue if __name__ == '__main__': tried = 0 for get in fournums_with_replacement(): tried += 1 if (tried % 1000000 == 0): print tried, 'Trying:', get rhs = get[0]**5 + get[1]**5 + get[2]**5 + get[3]**5 if is_fifth_power(rhs): print 'Found:', get, rhs break
which is both longer and slower (takes about 20 seconds) than the original program, but at least we have the satisfaction that it doesn’t depend on any externally known upper bound.
I originally started writing this post because I wanted to describe some experiments I did with profiling, but it’s late and I’m sleepy so I’ll just mention it.
python -m cProfile euler_conjecture.py
will print relevant output in the terminal:
26916504 function calls in 26.991 seconds Ordered by: standard name ncalls tottime percall cumtime percall filename:lineno(function) 1 18.555 18.555 26.991 26.991 euler_conjecture.py:1() 13458164 4.145 0.000 4.145 0.000 euler_conjecture.py:12(fournums_with_replacement) 13458163 4.292 0.000 4.292 0.000 euler_conjecture.py:3(is_fifth_power) 175 0.000 0.000 0.000 0.000 {method 'add' of 'set' objects} 1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
Another way to view the same thing is to write the profile output to a file and read it with cprofilev
:
python -m cProfile -o euler_profile.out euler_conjecture.py cprofilev euler_profile.out
and visit http://localhost:4000 to view it.
Of course, simply translating this code to C++ makes it run much faster:
#include <array> #include <iostream> #include <map> #include <utility> typedef long long Int; constexpr Int fifth_power(Int x) { return x * x * x * x * x; } std::map<Int, int> known_fifth_powers = {{0, 0}}; bool is_fifth_power(Int n) { while (n > known_fifth_powers.rbegin()->first) { int m = known_fifth_powers.rbegin()->second + 1; known_fifth_powers[fifth_power(m)] = m; } return known_fifth_powers.count(n); } std::array<Int, 4> four_nums() { static std::array<Int, 4> x = {1, 1, 1, 0}; int i = 3; while (i > 0 && x[i] == x[i - 1]) --i; x[i] += 1; while (++i < 4) x[i] = 1; return x; } std::ostream& operator<<(std::ostream& os, std::array<Int, 4> x) { os << "(" << x[0] << ", " << x[1] << ", " << x[2] << ", " << x[3] << ")"; return os; } int main() { while (true) { std::array<Int, 4> get = four_nums(); Int rhs = fifth_power(get[0]) + fifth_power(get[1]) + fifth_power(get[2]) + fifth_power(get[3]); if (is_fifth_power(rhs)) { std::cout << "Found: " << get << " " << known_fifth_powers[rhs] << std::endl; break; } } }
and
clang++ -std=c++11 euler_conjecture.cc && time ./a.out
runs in 2.43s, or 0.36s if compiled with -O2.
But I don’t have a satisfactory answer to how to make our Python program which takes 20 seconds as fast as the 8.5-second known-upper-bound version.
Edit [2015-05-08]: I wrote some benchmarking code to compare all the different “combination” functions.
import itertools # Copied from the Python documentation def itertools_equivalent(iterable, r): pool = tuple(iterable) n = len(pool) if not n and r: return indices = [0] * r yield tuple(pool[i] for i in indices) while True: for i in reversed(range(r)): if indices[i] != n - 1: break else: return indices[i:] = [indices[i] + 1] * (r - i) yield tuple(pool[i] for i in indices) # Above function, specialized to first argument being range(1, n) def itertools_equivalent_specialized(n, r): indices = [1] * r yield indices while True: for i in reversed(range(r)): if indices[i] != n - 1: break else: return indices[i:] = [indices[i] + 1] * (r - i) yield indices # Function to generate all combinations of 4 elements def all_combinations_pythonic(r): xs = [1] * r while True: yield xs for i in range(r - 1, 0, -1): if xs[i] < xs[i - 1]: break else: i = 0 xs[i] += 1 xs[i + 1:] = [1] * (r - i - 1) # Above function, written in a more explicit C-like way def all_combinations_clike(r): xs = [1] * r while True: yield xs i = r - 1 while i > 0 and xs[i] == xs[i - 1]: i -= 1 xs[i] += 1 while i < r - 1: i += 1 xs[i] = 1 # Above two functions, specialized to r = 4, using tuple over list. def fournums(): (x0, x1, x2, x3) = (1, 1, 1, 1) while True: yield (x0, x1, x2, x3) if x3 < x2: x3 += 1 continue x3 = 1 if x2 < x1: x2 += 1 continue x2 = 1 if x1 < x0: x1 += 1 continue x1 = 1 x0 += 1 continue # Benchmarks for all functions defined above (and the library function) def benchmark_itertools(n): for xs in itertools.combinations_with_replacement(range(1, n), 4): if xs[0] >= n: break def benchmark_itertools_try(n): combinations = itertools.combinations_with_replacement(range(1, n), 4) while True: try: xs = combinations.next() if xs[0] >= n: break except StopIteration: return def benchmark_itertools_equivalent(n): for xs in itertools_equivalent(range(1, n), 4): if xs[0] >= n: break def benchmark_itertools_equivalent_specialized(n): for xs in itertools_equivalent_specialized(n, 4): if xs[0] >= n: break def benchmark_all_combinations_pythonic(n): for xs in all_combinations_pythonic(4): if xs[0] >= n: break def benchmark_all_combinations_clike(n): for xs in all_combinations_clike(4): if xs[0] >= n: break def benchmark_fournums(n): for xs in fournums(): if xs[0] >= n: break if __name__ == '__main__': benchmark_itertools(150) benchmark_itertools_try(150) benchmark_itertools_equivalent(150) benchmark_itertools_equivalent_specialized(150) benchmark_all_combinations_pythonic(150) benchmark_all_combinations_clike(150) benchmark_fournums(150)
As you can see, I chose inside the benchmarking function the same statement that would cause all_combinations
to terminate, and have no effect for the other combination functions.
When run with
python -m cProfile benchmark_combinations.py
the results include:
2.817 benchmark_combinations.py:80(benchmark_itertools) 8.583 benchmark_combinations.py:84(benchmark_itertools_try) 126.980 benchmark_combinations.py:93(benchmark_itertools_equivalent) 46.635 benchmark_combinations.py:97(benchmark_itertools_equivalent_specialized) 44.032 benchmark_combinations.py:101(benchmark_all_combinations_pythonic) 18.049 benchmark_combinations.py:105(benchmark_all_combinations_clike) 10.923 benchmark_combinations.py:109(benchmark_fournums)
Lessons:
- Calling
itertools.combinations_with_replacement
is by far the fastest, taking about 2.7 seconds. It turns out that it’s written in C, so this would be hard to beat. (Still, writing it in atry
block is seriously bad.) - The “equivalent” Python code from the itertools documentation (
benchmark_itertools_combinations_with_replacment
) is about 50x slower. - Gets slightly better when specialized to numbers.
- Simply generating all combinations without an upper bound is actually faster.
- It can be made even faster by writing it in a more C-like way.
- The tuples version with the loop unrolled manually is rather fast when seen in this light, less than 4x slower than the library version.
Colliding balls approximate pi
Found via G+, a new physical experiment that approximates , like Buffon’s needle problem: The Pi Machine.
Roughly, the amazing discovery of Gregory Galperin is this: When a ball of mass collides with one of ball , propelling it towards a wall, the number of collisions (assuming standard physics idealisms) is , so by taking , we can get the first digits of . Note that this number of collisions is an entirely determinstic quantity; there’s no probability is involved!
Here’s a video demonstrating the fact for (the blue ball is the heavier one):
The NYT post says how this discovery came about:
Dr. Galperin’s approach was also geometric but very different (using an unfolding geodesic), building on prior related insights. Dr. Galperin, who studied under well-known Russian mathematician Andrei Kolmogorov, had recently written (with Yakov Sinai) extensively on ball collisions, realized just before a talk in 1995 that a plot of the ball positions of a pair of colliding balls could be used to determine pi. (When he mentioned this insight in the talk, no one in the audience believed him.) This finding was ultimately published as “Playing Pool With Pi” in a 2003 issue of Regular and Chaotic Dynamics.
The paper, Playing Pool With π (The number π from a billiard point of view) is very readable. The post has, despite a “solution” section, essentially no explanation, but the two comments by Dave in the comments section explain it clearly. And a reader sent in a cleaned-up version of that too: here, by Benjamin Wearn who teaches physics at Fieldston School.
Now someone needs to make a simulation / animation graphing the two balls in phase space of momentum. :-)
I’d done something a while ago, to illustrate The Orbit of the Moon around the Sun is Convex!, here. Probably need to re-learn all that JavaScript stuff, to make one for this. Leaving this post here as a placeholder.
Or maybe someone has done it already?
Prefatory apprehension
Robert Recorde’s 1557 book is noted for being the first to introduce the equals sign =, and is titled:
The Whetstone of Witte: whiche is the seconde parte of Arithmeteke: containing the extraction of rootes; the cossike practise, with the rule of equation; and the workes of Surde Nombers.
Its title page (see http://www.maa.org/publications/periodicals/convergence/mathematical-treasures-robert-recordes-whetstone-of-witte, see also the full book at https://archive.org/stream/TheWhetstoneOfWitte#page/n0/mode/2up) contains this verse:
Original spelling
Though many ſtones doe beare greate price, The grounde of artes did brede this ſtone: |
Modern spelling
Though many stones do bear great price, The ground of arts did breed this stone; |
Apparently the full title contains a pun (see http://www.pballew.net/arithm17.html): “the cossike practise” in the title refers to algebra, as the Latin cosa apparently meaning “a thing” was used to stand for an unknown, abbreviated to cos — but the Latin word cos itself means a grindstone.
The author again reminds readers not to blame his book, at the end of his preface:
To the curiouſe ſcanner.
If you ought finde, as ſome men maie, But if you mende not that you blame, |
Authors are either anxious about how their book is received, or make sure to be pointedly uncaring.
Sir Arthur Conan Doyle, in a mostly forgettable volume of poetry (Songs of the Road, 1911), begins:
If it were not for the hillocks
You’d think little of the hills;
The rivers would seem tiny
If it were not for the rills.
If you never saw the brushwood
You would under-rate the trees;
And so you see the purpose
Of such little rhymes as these.
Kālidāsa of course begins his Raghuvaṃśa with a grand disclaimer:
kva sūryaprabhavo vaṃśaḥ kva cālpaviṣayā matiḥ /
titīrṣur dustaram mohād uḍupenāsmi sāgaram // Ragh_1.2 //mandaḥ kaviyaśaḥ prārthī gamiṣyāmy upahāsyatām /
prāṃśulabhye phale lobhād udbāhur iva vāmanaḥ // Ragh_1.3 //atha vā kṛtavāgdvāre vaṃśe ‘smin pūrvasūribhiḥ /
maṇau vajrasamutkīrṇe sūtrasyevāsti me gatiḥ // Ragh_1.4 //
But the most nonchalant I’ve seen, thanks to Dr. Ganesh, is this gīti by Śrīkṛṣṇa Brahmatantra Yatīndra of the Parakāla Maṭha, Mysore:
nindatu vā nandatu vā
mandamanīṣā niśamya kṛtim etām
harṣaṃ vā marṣaṃ vā
sarṣapamātram api naiva vindema
Screw you guys. :-)
Big O() notation: a couple of sources
This post contains, just for future reference, a couple of primary sources relevant to the (“Big O”) notation:
- Some introductory words from Asymptotic Methods in Analysis by de Bruijn
- An letter from Donald Knuth on an approach to teaching calculus using this notation.
Visualizing product of permutations
A simple pedagogical trick that may come in handy: represent a permutation using arrows (curved lines) from to for each . Then, the product of two permutations can be represented by just putting the two corresponding figures (sets of arrows) one below the other, and following the arrows.
The figure is from an article called Symmetries by Alain Connes, found via the Wikipedia article on Morley’s trisector theorem (something entirely unrelated to permutations, but the article covers both of them and more).
I’m thinking how one might write a program to actually draw these: if we decide that the “height” of the figure is some , then each arrow needs to go from some to (using here the usual screen convention of coordinate increasing from left to right, and coordinate increasing from top to bottom). Further, each curve needs to have vertical slope at its two endpoints, so that successive curves can line up smoothly. The constraint on starting point, ending point, and directions at the endpoints defines almost a quadratic Bezier curve, except that here the two directions are parallel. So it’s somewhere between a quadratic and the (usual) cubic Bezier curve, which is given by the start point, end point, and derivatives at the start and end point. (Here we only care about the direction of the derivative; we can pick some arbitrary magnitude to fix the curve: the larger we pick, the more smooth it will look at the ends, at the cost of smoothness in the interior.)
Even knowing the curve, how do we generate an image?
The idea of logarithms, and the first appearance of e
[Incomplete post: about 10% written, about 90% left.]
The notion of the number , the exponential function , and logarithms are often conceptual stumbling blocks even to someone who has an otherwise solid understanding of middle-school mathematics.
Just what is the number ? How was it first calculated / where did it first turn up? Premature exposure to its numerical value
only serves to deepen the mysteriousness and to make it seem arbitrary.
Here a historical perspective helps: as is often the case, here too, the first appearance is simpler and more well-motivated than the accounts in dry textbooks. This is from this account by Matthew P. Wiener (originally posted on USENET somewhere, as quoted by MJD). I’m just going to quote it directly for now, and edit it later:
Napier, who invented logarithms, more or less worked out a table of logarithms to base , as follows:
0 1 2 3 4 5 6 7 8 9 10 ... 1 2 4 8 16 32 64 128 256 512 1024 ...The arithmetic progression in the first row is matched by a geometric progression in the second row. If, by any luck, you happen to wish to multiply 16 by 32, that just happen to be in the bottom row, you can look up their “logs” in the first row and add 4+5 to get 9 and then conclude 16·32=512.
For most practical purposes, this is useless. Napier realized that what one needs to multiply in general is for a base—the intermediate values will be much more extensive. For example, with base 1.01, we get:
0 1.00 1 1.01 2 1.02 3 1.03 4 1.04 5 1.05 6 1.06 7 1.07 8 1.08 9 1.09 10 1.10 11 1.12 12 1.13 13 1.14 14 1.15 15 1.16 16 1.17 17 1.18 18 1.20 19 1.21 20 1.22 21 1.23 22 1.24 23 1.26 24 1.27 25 1.28 26 1.30 27 1.31 28 1.32 29 1.33 30 1.35 31 1.36 32 1.37 33 1.39 34 1.40 35 1.42 [...] 50 1.64 51 1.66 52 1.68 53 1.69 54 1.71 55 1.73 [...] 94 2.55 95 2.57 96 2.60 97 2.63 98 2.65 99 2.68 100 2.70 101 2.73 102 2.76 103 2.79 104 2.81 105 2.84 [...]So if you need to multiply 1.27 by 1.33, say, just look up their logs, in this case, 24 and 29, add them, and get 53, so 1.27·1.33=1.69. For two/three digit arithmetic, the table only needs entries up to 9.99.
Note that is almost there, as the antilogarithm of 100. The natural logarithm of a number can be read off from the above table, as just [approximately] the corresponding exponent.
What Napier actually did was work with base .9999999. He spent 20 years computing powers of .9999999 by hand, producing a grand version of the above. That’s it. No deep understanding of anything, no calculus, and pops up anyway—in Napier’s case, was the 10 millionth entry. (To be pedantic, Napier did not actually use decimal points, that being a new fangled notion at the time.)
Later, in his historic meeting with Briggs, two changes were made. A switch to a base was made, so that logarithms would scale in the same direction as the numbers, and the spacing on the logarithm sides was chosen so that . These two changes were, in effect, just division by .
In other words, made its first appearance rather implicitly.
(I had earlier read a book on Napier and come to the same information though a lot less clearly, here.)
I had started writing a series of posts leading up to an understanding of the exponential function (here, here, here), but it seems to have got abandoned. Consider this one a contribution to that series.
The functional equation f(x+y) = f(x)f(y)
Suppose satisfies . What can we say about ?
Putting gives
which can happen if either or . Note that the function which is identically zero satisfies the functional equation. If is not this function, i.e., if for at least one value of , then plugging that value of (say ) into the equation gives . Also, for any , the equation forces as well. Further, so for all .
Next, putting gives , and by induction . Putting in place of in this gives which means (note we’re using here). And again, . So , which completely defines the function at rational points.
[As , it can be written as for some constant , which gives for rational .]
To extend this function to irrational numbers, we need some further assumptions on , such as continuity. It turns out that being continuous at any point is enough (and implies the function is everywhere): note that . Even being Lebesgue-integrable/measurable will do.
Else, there are discontinuous functions satisfying the functional equation. (Basically, we can define the value of the function separately on each “independent” part. That is, define the equivalence class where and are related if for rationals and , pick a representative for each class using the axiom of choice (this is something like picking a basis for , which corresponds to the equivalence class defined by the relation ), define the value of the function independently for each representative, and this fixes the value of on . See this article for more details.)
To step back a bit: what the functional equation says is that is a homorphism from , the additive group of real numbers, to , the multiplicative monoid of real numbers. If is not the trivial identically-zero function, then (as we saw above) is in fact a homomorphism from , the additive group of real numbers, to , the multiplicative group of positive real numbers. What we proved is that the exponential functions are precisely all such functions that are nice (nice here meaning either measurable or continuous at least one point). (Note that this set includes the trivial homomorphism corresponding to : the function identically everywhere. If is not this trivial map, then it is in fact an isomorphism.)
Edit [2013-10-11]: See also Overview of basic facts about Cauchy functional equation.
Trajectory of a point moving with acceleration perpendicular to velocity
(Just some basic high-school physics stuff; to assure myself I can still do some elementary things. :P Essentially, showing that if a particle moves with acceleration perpendicular to velocity, or velocity perpendicular to position, then it traces out a circle. Stop reading here if this is obvious.)
Suppose a point moves in the plane such that its acceleration is always perpendicular to its velocity, and of the same magnitude. What is its path like?
To set up notation: let’s say the point’s position at time is , its velocity is , and its acceleration is .
The result of rotating a point by 90° is . (E.g. see figure below)
So the fact that acceleration is at right angles to velocity means that , or, to write everything in terms of the velocity,
where we can get rid of by substituting the second equation (in the form ) into the first:
or in other words
By some theory about ordinary differential equations, which I don’t know (please help!) (but see the very related example you saw in high school, of simple harmonic motion), the solutions to this equation are and and any linear combination of those: the solution in general is
where and is the angle such that and . And the fact that gives . So . Note that is indeed perpendicular to as we wanted.
The actual trajectory can be got by integrating
to get and . This trajectory is a point moving on a circle centered at point and of radius , with speed or unit angular speed. Note that velocity is also perpendicular to the point’s position wrt the centre of the circle, as velocity is tangential to the circle, as it should be.
With a suitable change of coordinates (translate the origin to , then rotate the axes by , then scale everything so that ), this is the familiar paremetrization of the circle.
Note: Just as we derived from assuming that the acceleration is perpendicular to velocity, we can, by assuming that velocity is perpendicular to position, identically derive , i.e. that the point moves on a circle.
The power series for sin and cos
There are many ways to derive the power series of and using the machinery of Taylor series etc., but below is another elementary way of demonstrating that the well-known power series expansions are the right ones. The argument below is from Tristan Needham’s Visual Complex Analysis, which I’m reproducing without looking at the book just to convince myself that I’ve internalized it correctly.
So: let
We will take the following two for granted (both can be proved with some effort):
- Both power series are convergent.
- The power series can be differentiated term-wise.
As suggested by (2) above, the first thing we observe is that and .
So firstly:
which means that is a constant and does not vary with . Putting shows that and , so for all .
Secondly, define the angle as a function of , by . (To be precise, this defines up to a multiple of , i.e. modulo .)
Differentiating the left-hand side of this definition gives
(where means )
while differentiating the right-hand side gives
The necessary equality of the two tells us that , which along with the initial condition that says , gives (or to be precise, ).
In other words, we have shown that the power series and satisfy and therefore and for some . The observation that (or our earlier observation that for all ) gives , thereby showing that and .
So much for and . Just as an aside, observe that if we take to be a symbol satisfying , then
the right hand side of which looks very much like the result of “substituting” in the known (real) power series
(which itself can be proved using the term-wise differentiation above and the defining property , say).
So this is one heuristic justification for us to define .
Or, if we define as the result of substituting in the real power series for , this proves that .
The potions puzzle by Snape in Harry Potter and the Philosopher’s Stone
Sometime this week, I reread the first Harry Potter book (after at least 10 years… wow, has it been that long?), just for contrast after reading Rowling’s adult novel The Casual Vacancy (on which more later). Anyway, in the penultimate chapter there is a puzzle:
He pulled open the next door, both of them hardly daring to look at what came next — but there was nothing very frightening in here, just a table with seven differently shaped bottles standing on it in a line.
“Snape’s,” said Harry. “What do we have to do?”
They stepped over the threshold, and immediately a fire sprang up behind them in the doorway. It wasn’t ordinary fire either; it was purple. At the same instant, black flames shot up in the doorway leading onward. They were trapped.
“Look!” Hermione seized a roll of paper lying next to the bottles. Harry looked over her shoulder to read it:Danger lies before you, while safety lies behind,
Two of us will help you, whichever you would find,
One among us seven will let you move ahead,
Another will transport the drinker back instead,
Two among our number hold only nettle wine,
Three of us are killers, waiting hidden in line.
Choose, unless you wish to stay here forevermore,
To help you in your choice, we give you these clues four:
First, however slyly the poison tries to hide
You will always find some on nettle wine’s left side;
Second, different are those who stand at either end,
But if you would move onward, neither is your friend;
Third, as you see clearly, all are different size,
Neither dwarf nor giant holds death in their insides;
Fourth, the second left and the second on the right
Are twins once you taste them, though different at first sight.
I became curious about whether this is just a ditty Rowling made up, or the puzzle actually makes sense and is consistent. It turns out she has constructed it well. Let’s take a look. This investigation can be carried out by hand, but we’ll be lazy and use a computer, specifically Python. The code examples below are all to be typed in an interactive Python shell, the one that you get by typing “python” in a terminal.
So what we have are seven bottles, of which one will take you forward (F), one will let you go back (B), two are just nettle wine (N), and three are poison (P).
>>> bottles = ['F', 'B', 'N', 'N', 'P', 'P', 'P']
The actual ordering of these 7 bottles is some ordering (permutation) of them. As 7 is a very small number, we can afford to be inefficient and resort to brute-force enumeration.
>>> import itertools >>> perms = [''.join(s) for s in set(itertools.permutations(bottles))] >>> len(perms) 420
The set
is needed to remove duplicates, because otherwise itertools.permutations
will print 7! “permutations”. So already the number of all possible orderings is rather small (it is ). We can look at a sample to check whether things look fine.
>>> perms[:10] ['PNFNPBP', 'NPPBNFP', 'FNNPBPP', 'PPPFNBN', 'NPPNBFP', 'PFNNBPP', 'NPBPPFN', 'NBNPPFP', 'NPPFBNP', 'BNPFNPP']
Now let us try to solve the puzzle. We can start with the first clue, which says that wherever a nettle-wine bottle occurs, on its left is always a poison bottle (and in particular therefore, a nettle-wine bottle cannot be in the leftmost position). So we must restrict the orderings to just those that satisfy this condition.
>>> def clue1(s): return all(i > 0 and s[i-1] == 'P' for i in range(len(s)) if s[i]=='N') ... >>> len([s for s in perms if clue1(s)]) 60
(In the code, the 7 positions are 0 to 6, as array indices in code generally start at 0.)
Then the second clue says that the bottles at the end are different, and neither contains the potion that lets you go forward.
>>> def clue2(s): return s[0] != s[6] and s[0] != 'F' and s[6] != 'F' ... >>> len([s for s in perms if clue1(s) and clue2(s)]) 30
The third clue says that the smallest and largest bottles don’t contain poison, and this would be of help to Harry and Hermione who can see the sizes of the bottles. But as we readers are not told the sizes of the bottles, this doesn’t seem of any help to us; let us return to this later.
The fourth clue says that the second-left and second-right bottles have the same contents.
>>> def clue4(s): return s[1] == s[5] ... >>> len([s for s in perms if clue1(s) and clue2(s) and clue4(s)]) 8
There are now just 8 possibilities, finally small enough to print them all.
>>> [s for s in perms if clue1(s) and clue2(s) and clue4(s)] ['PPNBFPN', 'BPNPFPN', 'BPFPNPN', 'BPPNFPN', 'PNPFPNB', 'BPNFPPN', 'PPNFBPN', 'PNFPPNB']
Alas, without knowing which the “dwarf” and “giant” bottles are, we cannot use the third clue, and this seems as far as we can go. We seem to have exhausted all the information available…
Almost. It is reasonable to assume that the puzzle is meant to have a solution. So even without knowing where exactly the “dwarf” and “giant” bottles are, we can say that they are in some pair of locations that ensure a unique solution.
>>> def clue3(d, g, s): return s[d]!='P' and s[g]!='P' ... >>> for d in range(7): ... for g in range(7): ... if d == g: continue ... poss = [s for s in perms if clue1(s) and clue2(s) and clue4(s) and clue3(d,g,s)] ... if len(poss) == 1: ... print d, g, poss[0] ... 1 2 PNFPPNB 1 3 PNPFPNB 2 1 PNFPPNB 2 5 PNFPPNB 3 1 PNPFPNB 3 5 PNPFPNB 5 2 PNFPPNB 5 3 PNPFPNB
Aha! If you look at the possible orderings closely, you will see that we are down to just two possibilities for the ordering of the bottles.
Actually there is some scope for quibbling in what we did above: perhaps we cannot say that there is a unique solution determining the entire configuration; perhaps all we can say is that the puzzle should let us uniquely determine the positions of just the two useful bottles. Fortunately, that gives exactly the same set of possibilities, so this distinction happens to be inconsequential.
>>> for d in range(7): ... for g in range(7): ... if d == g: continue ... poss = [(s.index('F'),s.index('B')) for s in perms if clue1(s) and clue2(s) and clue4(s) and clue3(d,g,s)] ... if len(set(poss)) == 1: ... print d, g, [s for s in perms if clue1(s) and clue2(s) and clue4(s) and clue3(d,g,s)][0] ... 1 2 PNFPPNB 1 3 PNPFPNB 2 1 PNFPPNB 2 5 PNFPPNB 3 1 PNPFPNB 3 5 PNPFPNB 5 2 PNFPPNB 5 3 PNPFPNB
Good. Note that there are only two configurations above. So with only the clues in the poem, and the assumption that the puzzle can be solved, we can narrow down the possibilities to two configurations, and be sure of the contents of all the bottles except the third and fourth. We know that the potion that lets us go forward is in either the third or the fourth bottle.
In particular we see that the last bottle lets us go back, and indeed this is confirmed by the story later:
“Which one will get you back through the purple flames?”
Hermione pointed at a rounded bottle at the right end of the line.
[…]
She took a long drink from the round bottle at the end, and shuddered.
But we don’t know which of the two it is, as we can’t reconstruct all the relevant details of the configuration. Perhaps we can reconstruct something with the remaining piece of information from the story?
“Got it,” she said. “The smallest bottle will get us through the black fire — toward the Stone.”
Harry looked at the tiny bottle.
[…]
Harry took a deep breath and picked up the smallest bottle.
So we know that the bottle that lets one move forward is in fact in the smallest one, the “dwarf”.
>>> for d in range(7): ... for g in range(7): ... poss = [s for s in perms if clue1(s) and clue2(s) and clue4(s) and clue3(d,g,s)] ... if len(poss) == 1 and poss[0][d] == 'F': ... print d, g, poss[0] ... 2 1 PNFPPNB 2 5 PNFPPNB 3 1 PNPFPNB 3 5 PNPFPNB
This narrows the possible positions of the smallest and largest bottles (note that it says the largest bottle is one that contains nettle wine), but still leaves the same two possibilities for the complete configuration. So we can stop here.
Conclusion
What we can conclude is the following: apart from the clues mentioned in the poem, the “dwarf” (the smallest bottle) was in either position 2 (third from the left) or 3 (fourth from the left). The biggest bottle was in either position 1 (second from the left) or 5 (sixth from the left). With this information about the location of the smallest bottle (and without necessarily assuming the puzzle has a unique solution!), Hermione could determine the contents of all the bottles. In particular she could determine the location of the two useful bottles: namely that the bottle that lets you go back was the last one, and that the one that lets you go forward was the smallest bottle.
>>> for (d,g) in [(2,1), (2,5), (3,1), (3,5)]: ... poss = [s for s in perms if clue1(s) and clue2(s) and clue4(s) and clue3(d, g, s)] ... assert len(poss) == 1 ... s = poss[0] ... assert s.index('B') == 6 ... assert s.index('F') == d ... print (d,g), s ... (2, 1) PNFPPNB (2, 5) PNFPPNB (3, 1) PNPFPNB (3, 5) PNPFPNB
It is not clear why she went to the effort to create a meaningful puzzle, then withheld details that would let the reader solve it fully. Perhaps some details were removed during editing. As far as making up stuff for the sake of a story goes, though, this is nothing; consider for instance the language created for Avatar which viewers have learned.
Added:
See also http://www.zhasea.com/logic/snape.html which does it by hand, and has a perfectly clear exposition (it doesn’t try the trick of guessing that solution is unique before reaching for the additional information from the story).
Bill Thurston
Somehow I am saddened to hear of the death of William Thurston, even though I never knew him nor can I even understand his work.
For years I have been pointing people at this article of his, which I find illuminating and inspiring, even in ways that have nothing to do with mathematics: http://arxiv.org/abs/math.HO/9404236
5-paragraph version: http://mathoverflow.net/questions/43690/whats-a-mathematician-to-do/44213#44213
Riffs on his “derivative” exercise: https://profiles.google.com/114134834346472219368/buzz/hTVJiP5LoPb https://shreevatsa.wordpress.com/2016/03/26/multiple-ways-of-understanding/
User profile (http://mathoverflow.net/users/9062/bill-thurston):
“Mathematics is a process of staring hard enough with enough perseverance at at the fog of muddle and confusion to eventually break through to improved clarity. I’m happy when I can admit, at least to myself, that my thinking is muddled, and I try to overcome the embarrassment that I might reveal ignorance or confusion. Over the years, this has helped me develop clarity in some things, but I remain muddled in many others. I enjoy questions that seem honest, even when they admit or reveal confusion, in preference to questions that appear designed to project sophistication.”
http://matrixeditions.com/Thurstonforeword.html :
“At that time, I prided myself in reading quickly. I was really amazed by my first encounters with serious mathematics textbooks. I was very interested and impressed by the quality of the reasoning, but it was quite hard to stay alert and focused. After a few experiences of reading a few pages only to discover that I really had no idea what I’d just read, I learned to drink lots of coffee, slow way down, and accept that I needed to read these books at 1/10th or 1/50th standard reading speed, pay attention to every single word and backtrack to look up all the obscure numbers of equations and theorems in order to follow the arguments.”
http://mathoverflow.net/questions/38639/thinking-and-explaining :
“When listening to a lecture, I can’t possibly attend to every word: so many words blank out my thoughts. My attention repeatedly dives inward to my own thoughts and my own mental models, asking ‘what are they really saying?’ or ‘where is this going?’. I try to shortcut through my own understanding, then emerge to see if I’m still with the lecture. It’s the only way for me, and it often works.”
http://quomodocumque.wordpress.com/2012/08/22/my-thurston-memory/
“My first tenure-track job interview was at Cornell. During and after my job talk, most people were pretty quiet, but there was one guy who kept asking very penetrating and insightful questions. And it was very confusing, because I knew all the number theorists at Cornell, and I had no idea who this guy was, or how it was that he obviously understood my talk better than anybody else in the room, possibly including me.”
http://books.google.com/books?id=BXYucAAhFCgC&pg=PR11
“When I grew up I was a voracious reader. But when I started studying serious mathematical textbooks I was surprised how slowly I had to read, at a much lower speed than reading non-mathematical books. I couldn’t just gloss over the text. The phrasing and the symbols had been carefully chosen and every sign was important. Now I read differently. I rarely spend the time and effort to follow carefully every word and every equation in a mathematics article. I have come to appreciate the importance of the explanation that lies beneath the surface. […] I have little expectation for the words to be a good representation of the real ideas. I try to tunnel beneath the surface and to find shortcuts, checking in often enough to have a reasonable hope not to miss a major point. I have decided that daydreaming is not a bug but a feature. If I can drift away far enough to gain the perspective that allows me to see the big picture, noticing the details becomes both easier and less important.
I wish I had developed the skill of reading beneath the surface much earlier. As I read, I stop and ask, What’s the author trying to say? What is the author really thinking (if I suppose it is different from what he put in the mathematical text)? What do I think of this? I talk to myself back and forth while reading somebody else’s writing. But the main thing is to give myself time, to close my eyes, to give myself space, to reflect and allow my thoughts to form on their own in order to shape my ideas.”
http://mathoverflow.net/questions/5499/which-mathematicians-have-influenced-you-the-most/5539#5539 :
“A prominent mathematician once remarked to me that Thurston was the most underappreciated mathematician alive today. When I pointed out that Thurston had a Fields medal and innumerable other accolades, he replied that this was not incompatible with his thesis.”
He believed that this human understanding was what gave mathematics not only its utility but its beauty, and that mathematicians needed to improve their ability to communicate mathematical ideas rather than just the details of formal proofs.
…
Benson Farb, a mathematician at the University of Chicago and a student of Thurston, said in an email, “in my opinion Thurston is underrated: his influence goes far beyond the (enormous) content of his mathematics. He changed the way geometers/topologists think about mathematics. He changed our idea of what it means to ‘encounter’ and ‘interact with’ a geometric object. The geometry that came before almost looks like pure symbol pushing in comparison.”
Reactions like this are hard to explain: About the Proof&Progress article, http://golem.ph.utexas.edu/category/2006/10/wittgenstein_and_thurston_on_u.html#c005263 says:
“Reading Thurston’s response was one of the most stirring intellectual experiences of my life. It truly struck a cord with my own conception of mathematics. To me, it has the status that the Declaration of Independence has to many Americans, or the U.N. charter has to other global citizens.”
See these for a better summary:
http://www.math.columbia.edu/~woit/wordpress/?p=5059
http://terrytao.wordpress.com/2012/08/22/bill-thurston/
http://lamington.wordpress.com/2012/08/22/bill-thurston-1946-2012/
Edit [2012-09-28]: He has also done work in computer science! A fundamental result in data structures (on the number of rotations needed to transform one binary tree into another) was proved in a paper by Sleator–Tarjan–Thurston (with 278 citations). According to DBLP, he has three STOC papers.
See also: http://arxiv.org/abs/math/0503081 (“Mathematical Education”)
Edit [2016-02-20]: A collection of reminiscences about Thurston, in the Notices of the AMS, issues December 2015 and January 2016.
Are there Fibonacci numbers starting with 2012? (continued)
Almost 8 months ago I left the first part of this post unfinished planning to complete it in the morning; seems I slept too long. (Or as this guy said after a 2-year hiatus: “Sorry for the pause guys. I was in the bathroom.”)
Recall: To get a power of 2 that starts with a prefix (like ), we want such that the fractional part of lies between those of and (all logarithms here to base 10), and similarly to get a Fibonacci number starting with , we want (with some hand-waving) such that the fractional part of lies between those of and . The more general problem is:
Problem: Given an irrational number and an interval , find such that lies in the interval .
Here is one method, based on Edward Burger’s book Exploring the Number Jungle. Let be the midpoint of the interval . Then we are trying to find such that is close to .
- Find a fraction approximating , such that . (These are the convergents of the continued fraction of , but in practice it seems you can also get away with taking semi-convergents that may not satisfy this property.)
- Let be the closest integer to . Note that this automatically means
- Write with . This you can do quite easily with the Euclidean algorithm.
- Then for and , we have (it is a simple exercise to prove this)
- This means that the distance between and is small, modulo 1. If this distance turns out to be still too large, start with a bigger convergent .
I think I had some code to post as well (hey, what’s the actual Fibonacci number that starts with 2012?), but it needs to be cleaned up… probably this works (in Sage).
The thing we’re doing here is called inhomogeneous Diophantine approximation.
Are there Fibonacci numbers starting with 2012?
Do there exist powers of 2 whose first four digits are 2012?
Are there Fibonacci numbers whose first four digits are 2012?
If the answer is obvious to you (or you don’t care), you can stop reading.
The answer for both is:
- Yes.
- There are infinitely many such numbers.
- In fact, the fraction of (powers of 2 / Fibonacci numbers) starting with 2012 is exactly
Similarly with any other prefix p (of any length) in place of 2012. Proof follows.
A number x starts with a prefix p if and only if for some k ≥ 0,
Thus a power of 2, say 2^{n}, starts with p iff
for some
Taking logarithms to base 10 and simplifying, this is equivalent to
for some
This is saying that the fractional part of lies between the fractional parts of and For example, if , this means that the fractional part of lies between and .
Similarly, for Fibonacci numbers, as is (or should be) well-known, the nth Fibonacci number F_{n} is the closest integer to , where is the golden ratio. So starts with iff
Taking logarithms to base 10 and simplifying, while ignoring the annoying which becomes irrelevant in the limit (this line is not rigorous), this is equivalent to
which means that the fractional part of lies between the fractional parts of and . For , this means that the fractional part of lies between and .
In either case, we are trying to make the fractional part of , for some irrational number , lie in some interval. The relevant fact is this:
Theorem 1: for any irrational number , the sequence (where denotes the fractional part of ) is dense in .
or, in other words,
Theorem 1: For any irrational number , the sequence is dense modulo .
Proving this theorem is a good exercise.
This means that for any interval you want, you can always find some such that the fractional part of lies in your interval. In fact, because the sequence is dense, you can find an infinite sequence of such that the fractional parts of converge to the midpoint (say) of the desired interval. This proves the first two facts of the answer, and for the third we need a stronger theorem:
Theorem 2 [Equidistribution theorem]: For any irrational number , the numbers are uniformly distributed modulo 1.
This means that for any interval of size (say), the fraction of integers for which lies in the interval satisfies
This proves the third fact. The fraction of Fibonacci numbers (or of powers of a number that is not a power of 10) that start with a prefix is exactly where log is to base 10.
That much is standard. And non-constructive. We are assured of the existence of such numbers, but how do we actually find one?
The answer (or one answer), as it so often does in these problems, involves continued fractions. Here is one method, [to be continued when I wake up :p]
Edit: Continued here.
(1+ix/n)^n
[Posting some images here for possible future reuse.]
A non-rigorous argument: when is large enough so that is small, is roughly (hand-waving) the point on the unit circle at arc length (and hence angle) :
So multiplication by roughly corresponds to rotation by angle . Multiplication by , which is multiplication by n times, roughly corresponds to rotation by angle . As , “roughly” becomes exact.
Animation for :
Image generated from Python-generated SVG files; code available if anyone wants.
In particular, once one accepts the fact/definition that (for instance, show that the function satisfies ), it is true that is a rotation by π, that is,
Serieshelpmate in 19
Here’s a brilliant problem.
Consider the following chess position.
Black is to make 19 consecutive moves, after which White checkmates Black in one move. Black may not move into check, and may not check White (except possibly on his last move). Black and White are cooperating to achieve the aim of checkmate. (In chess problem parlance, this problem is called a serieshelpmate in 19.) How many different solutions are there?
This problem is due to Kauko Väisänen, and appears in A. Puusa, Queue Problems, Finnish Chess Problem Society, Helsinki, 1992 (Problem 2).
Hint: the above is quoted from Richard Stanley’s Enumerative Combinatorics.
How does Tupper’s self-referential formula work?
[I write this post with a certain degree of embarrassment, because in the end it turns out (1) to be more simple than I anticipated, and (2) already done before, as I could have found if I had internet access when I did this. :-)]
The so-called “Tupper’s self-referential formula” is the following, due to Jeff Tupper.
Graph the set of all points such that
in the region
where N is the following 544-digit integer:
48584506361897134235820959624942020445814005879832445494830930850619
34704708809928450644769865524364849997247024915119110411605739177407
85691975432657185544205721044573588368182982375413963433822519945219
16512843483329051311931999535024137587652392648746133949068701305622
95813219481113685339535565290850023875092856892694555974281546386510
73004910672305893358605254409666435126534936364395712556569593681518
43348576052669401612512669514215505395545191537854575257565907405401
57929001765967965480064427829131488548259914721248506352686630476300
The result is the following graph:
Whoa. How does this work?
At first sight this is rather too incredible for words.
But after a few moments we can begin to guess what is going on, and see that—while clever—this is perhaps not so extraordinary after all. So let us calmly try to reverse-engineer this feat.