Number Coverings

Pick a number. Let that number be 127. We say that a number ‘covers’ 127 if it contains the digits of 127, in order. Though not necessarily together. So, 127, of course, covers 127. 701220212987 also covers 127. 301742 does not.

Question: Given a k-digit number, how many n-digit numbers cover that k-digit number?

My first thought was this. If an (n+1)-digit number covers a k-digit number, the covering either occurs in the last n-many digits, or the covering includes the first digit. 1209 vs 4127, for example. Suppose that f(n,k) is the number of n-digit numbers that cover a k-digit number. If, in the (n+1)-digit number, the covering includes the first digit, then that digit is fixed since it must be the same as the first digit of the k-digit number, and the remaining n-many digits must must cover the remaining (k-1)-many digits, of which there are f(n,k-1) ways to do. If, in the (n+1)-digit number, the covering does not include the first digit, then that first digit can be anything except for 0, and whatever the first digit of the k-digit number is – thus giving 8 choices for that first digit. Since the first digit isn’t included in the covering, then the k-digit number must be covered by the remaining n-many digits, of which there are f(n,k) ways to do so.

This suggests the recurrence,

But this is, in fact, wrong.

The problem is that if you take an (n+1)-digit number, and pop off the highest digit, you are not guaranteed that what remains is an n-digit number. Consider 10029, for example. Pop off the 1, and you’re left with 29. Same goes for popping off the first digit of the k-digit number. But if f(n,k) is counting numbers based on a given length, this causes a problem.

The solution is to look at the problem from the other side. If you take an (n+1)-digit number and pop off the lowest digit, you are always guaranteed that the result is an n-digit number. 10030, popping off the lowest digit, gives 1003, a 5-digit number becoming a 4-digit number. Looking at the problem this way, you never run into the same issue.

So, let’s apply the same logic, except from the back.

Given an (n+1)-digit number, either the last digit is involved in covering the k-digit number, or it is not. If it is not, then the first n-many digits form an n-digit number that covers the k-digit number, and the last digit of the (n+1)-digit number can be anything. This suggests f(n,k)*9 ways of going about this, f(n,k) choices for the first n-many digits, and 9 choices for the last digit. If the last digit is involved in the k-digit number covering, then that last digit must be the same as the last digit of the k-digit number, which means there is 1 choice for it. That, and the first n-many digits of the number must cover the first (k-1) digits of the k-digit number. This suggests f(n,k-1)*1 ways of going about this. This leads to the recurrence,

This solves our 0-padding problem, and is in fact correct.

But, this isn’t enough. Notice that in our recurrence, we call f for a lesser value of n, as well as a lesser value of k. We need some initial conditions, fixed values of f that the higher values reference. For example, F(n+1) = F(n) + F(n-1) is not the Fibonacci numbers, until we define F(1) = 1 and F(2) = 1.

In our case, notice that f(n,k) = 1 if n = k. Given a k-digit number, there is only one k-digit number that covers it. Namely, itself.

This isn’t quite enough – it gives an initial condition for n. Basically, if we keep calculating f(n,k) for lower values of n, we can stop when we have n = k. But we need an initial condition for k, as well. If we calculate f(n,k) for lower values of k in the same way, for fixed n, when would we stop?

Consider f(n,0). That is, the number of n-digit numbers that cover a 0-digit number. That doesn’t sound like it makes much sense, but notice that, in a sense, -any- n-digit number covers a 0-digit number. So f(n,0) is just the number of n-digit numbers. How many is that? The first digit can be anything but 0, leaving 9 choices, and we have 10 choices for the remaining (n-1)-many digits. Thus,

For convenience, let us define f(0,0) = 1. That is, there is 1 way to cover a 0-digit number with a 0-digit number. And that is to do nothing at all. This is in-keeping with our f(k,k) = 1 restriction.

And this is enough. Bringing everything together, we have

Coding that up relatively quickly in a small ruby script, we find that there are 26010 many 7-digit numbers that cover any given 4-digit number.

Which is interesting. Though not half as interesting as the derivation of that recursive function, I think.

Now, you could theoretically solve for the closed form of f(n,k), but it looks relatively nasty. Something much more interesting is to define the following function.

The idea is that we take all the numbers f(n,k), for a given k, and string them out as the coefficients of a sum of powers of x. Then, even though we can’t express f(n,k) in a nice, convenient way, you can show using the above recurrence that

Which, at the very least, is interesting in its simplicity. To find the value of f(n,k), simply take the coefficient on the term of the series expansion of F(x,k). All the information of that sequence, wrapped up in one convenient function. Neat : )

New Year! School, That Is

So, I got back from Alaska. A … long time ago. Pictures will be forthcoming. After that, it was pretty much straight back to CMU. And back into the thick of things.

Theoretically, this semester was supposed to be easy. Four classes: Intro to Psychology, Special Topics in Thermal Physics, Probabilistic Simulations, and a graduate course in Discrete Mathematics.

Four courses. Nothing, compared to things I’ve done previously.

So, my prolonged silence might cause you to ask … what happened?

And what happened, for the most part, seems to be this. I agreed to TA a section of Calculus in 3D. That sucks up a large percentage of my time, grading and preparing. Discrete Mathematics, by the nature of the course, takes a -tremendous- amount of time. I basically spent a week thinking about 3 problems and didn’t get anywhere, only to get them all in the last two days before it was due. Those two by themselves seem to be the largest contributors, plus scads and scads of psych reading, which is driving me nuts.

But … so much math. Fascinating, exciting, beautiful math.

Some problems I’d like to discuss, when I have the time, would be …

Suppose you were to color the edges of a complete graph on n vertices with k many different colors. Let f(k) be the largest value such that you can color the complete graph on f(k) vertices with k colors – such that no three edges form a monochromatic triangle. The problem is to show that . I relish, absolutely relish, interesting constants falling out in unexpected places.

Similar setup, but in this case show that . This is very, very long … but very rewarding.

One problem I've been trying to write up, for a very long time (and my inability to complete it basically started this trend towards little to no writing), is calculating Graham's Number – one of the largest numbers ever put to practical use. It is big. So big you can't really comprehend it in terms of value. And yet … we can calculate it! And that, in my opinion, is very exciting.

Plus! Some interesting recursions, and some simulation tricks … We're doing some very interesting things in thermal I would love to share, but I'm struggling with the 'how', without teaching thermal physics from the ground up. I'm sure I will figure something out. But, in any case … interesting maths ahead.

Vacation Vacation

I’m taking a vacation from my vacation … going to Alaska for a week or so! No maths until I get back, and hopefully some new maths then. Feel free to leave any interesting math problems. Or, perhaps, where you would go and what you would do if you could travel through time and space. I’ll see you all on the other side! With pictures.

Many Integrations By Parts

In the spirit of the previous post, one thing that you do in calculus of variations – a lot – is integration by parts. It’s incredible how useful that one trick is. See, they teach you these things in calculus for a reason!

But, I was fiddling around yesterday, and got this nice result, applying many integrations by parts. For integers n, m,

Which I thought was kind of nice.

Calculus of Variations and the Italian Challenge

One thing I did this summer was a course on the so called ‘Calculus of Variations’. A good example question would go something like this.

Consider the set of all functions y, continuous with continuous derivatives, such that y(0) = 0, and y(1) = 1. Find the function y that minimizes the value of

J is called a functional, taking a function and returning a real number.

Taking, for example, y(x) = x (notice that it satisfies the smoothness requirements, and the boundary conditions), the above integral comes out to 4/3. So we know that the minimum value of the integral is, at most, 4/3.

Suppose you thought that the minimzing function were a quadratic polynomial, . The smoothness conditions are necessarily satisfied. For y(0) = 0, that requires c = 0. y(1) = a + b, so y(1) = 1 requires b = 1 – a. So we’re looking for a function of the form . If you evaluate the integral for that function, you get

If you minimize the above expression with respect to a, you find that the minimum value occurs when a = 5/22, and that J(y) = 347/264, or approximately 1.314, ever so slightly less than 4/3. So,

performs slightly better than y(x) = x … but that isn’t enough to show it’s an absolute minimizer.

You could continue on in this way, checking other functions but – let’s be honest. You’re really shooting blindly, because you don’t know the form of the function. Expanding out polynomial minimizers, it may lead you to the taylor expansion of the actual minimizer, but it would be messy and unsatisfying.

Using techniques in the Calculus of Variations, you can solve the problem with some degree of elegance. Elegance that I won’t put forth in detail here – I really just meant for this to be a brief introduction. But you can turn such a minimization problem into an associated differential equation problem. The nice thing about this is that, in comparison to these beasts, differential equations are relatively well understood. The associated problem is as follows. If y(x) minimizes J(y), then y(x) must satisfy this differential eqation problem, with boundary conditions y(0) = 0, y(1) = 1,

You can solve that using your favorite technique to yield the function,

Evaluating J(y), this yields

And this, you can show, is the absolute minimizer of J. Notice, interestingly, the quadratic solution was actually quite close to being the real minimizer. Neat!

Now, you can do all kinds of nice things with this. For example, describing shapes with functions, you can find the shape a hanging cable of fixed length assumes. You can find the curve that minimizes the amount of time it takes to slide a bead along a wire of that curve (the assumption here is, sliding under gravity). And suppose you were an ancient African queen, promised howevermuch land you could encompass with a bull hide, you might be interested in maximizing the total area you could encompass with a fixed amount of material. Many many things.

Of course, Mathematicians always have to go and take things to the next level, which brings me to the Italian Challenge. Now, as the story was presented to me, in Italy, they have these tests for professorships at universities. However, if the administration has a particular candidate in mind, they’ll tailor the test for their strengths. Some candidate must’ve been an expert at calculus of variations, because we have the following problem.

Consider the set of functions, continuous with a continuous first derivative, over the range of x from 0 to 1. We also have the restriction that y(0) = 0, and y(1) = 1. Given

Prove that J(y) has no minimizer of that set of functions.

I’m fascinated. In essence, given any function y(x), you can always find a function w(x) such that J(y) is greater than J(w).

This is interesting on a number of levels. Notice, for instance, that each term of the integrand is positive. Thus we know that, for any function y(x), J(y) is strictly greater than 0. So the values of J are bound from below, but have no minimum! Very interesting.

The associated differential equation problem goes as follows. If y(x) minimizes J(y), y(x) must satisfy y(0) = 0, y(1) = 1, and

Notice, interestingly, you’re not guaranteed that y”(x) exists or is continuous.

But, if J(y) has no mimimizer, and we know that if y(x) minimizes J(y) it satisfies that differential equation, there must be something wrong with that differential equation. It can’t have a solution – because then J(y) has a minimizer. But why?

I don’t know…

A Nice Substitution

I wasn’t always a math person. I used to be much more into reading books. I would read just about anything. Fast, too. But then … I stopped. I remember, the first book I bought but distinctly didn’t read was P.D. James’ Death of an Expert Witness. I picked it up again yesterday, years after the fact, and so far … it’s not bad. Maybe I will get into this ‘reading’ thing again.

But, a small calculation is in order, one that has been bothering me.

Consider the function,

An infinite power tower of x’s. I’ve done some things with this function before, but not this, I believe.

It is certainly questionable, what such a power tower actually means. For the purpose of this calculation, we imagine taking a number x, then raising x to that power, then raising x to the resulting power, then raising x again, etc. This creates a sequence of finite power towers, and we define f(x) to be the limit of that sequence, as the height of the tower goes to infinity.

For some values of x, clearly this sequence diverges to infinity. 2 to the 2nd, etc, etc, etc, rapidly becomes unmanagable. 2^2^2^2^2 has 19729 digits. f(x) for values such as these can be taken as infinite.

But! Over some x, f(x) is actually well defined, finite, seemingly smooth, and many other nice things as well. Consider f(1), which equals 1. f(0) is another matter all together…

That being so, what is the maximal x for which f(x) is finite, and what is f(x) at that point?

My thinking went something like this: I have no idea. But it might be kind of cool to calculate the derivative of f(x).

Looking at the definition of f(x), there’s one substitution that’s just itching to be made.

If we have an infinite power tower of x’s, and drop one off (the bottom most), we still have an infinite power tower of x’s, and the substitution can be made. The rest is standard implicit differentiation.

While the above isn’t really a nice looking function, it’s certainly much more reasonable that having infinitely tall towers flopping about.

And it does suggest something interesting. Notice, being a rational function, if the denominator goes to zero, f’(x) is going to explode to infinity. If that happens, f(x) is going to, effectively, explode as well.

At the very least, if the denominator goes to zero … it would be bad. This all suggests it might have some bearing on our problem. Letting the denominator go to zero, we can solve for f(x) at that point as

This, along with our initial definition of f(x), gives us something to work with.

So, at the above x value, the derivative blows up, and the function goes to infinity. Interestingly, our condition on the denominator of f’(x) also gives us an easy way of calculating f(x) at that point.

And, fiddling with Mathematica seems to confirm all this.

But … what’s bothering me is that I feel like I did too much work. The first time I saw this problem, this quiet little Asian kid whipped out the e^(1/e) like it was a trivial and self evident result. Was he seeing something that I’m not seeing? I don’t know…

I think it’s worth thinking about, in any case. Not too long, perhaps, but worth thinking about. And now, back to murder and mayhem. After all, isn’t that what summer is all about?

Open to Interpretation

This is a more open ended thing. I’m trying to cram and finish a presentation in these last couple of days, so I don’t have much time for my own maths. But, looking at this picture, lifted from Mathworld,

What are some questions that immediately spring to mind? One in particular springs out at me.

Increasingly, I find that being able to ask interesting questions is as important a skill, if not more so, than being able to answer them.

So, interesting math questions – go.

Questionable Integration: An Interesting Calculation

As I was walking home from lunch today, burdened by thoughts of simulated annealing, and cross-entropy minimization, I happened to look down as I was crossing a bridge. And on the road below, a pair of boys, side by side, in matching uniforms and backpacks, looked to be walking toward school. But, right as I looked, a telephone pole stood right between us, blocking my few of the inner half of each boy – it looked like one boy, stretched to the point of absurdity. And yet still realistic. Then the moment passed.

I love moments like that. Tiny, fleeting things. Seeing the world, slightly skewed. I remember one time, riding my bike, coming up behind a bird sitting in the middle of the road. The bird took off, flying away from me. But, for a moment, my eyes fixed on his tail, and I imagine we hit the exact same velocity for that one second. It was like the entire world blurred away, leaving me and the bird moving as one. And then it was over.

And that has absolutely nothing to do with what I’d like to talk about today.

Consider the function frac(x). frac removes the integer part of x, leaving the fractional part. So frac(5.25) = 0.25. Of course, frac(0.25) = 0.25, as well. frac(pi) = pi – 3, giving the fractional part by just subtracting off the integer part. Clearly, frac(n) = 0, for any integer n. This becomes important.

For x from 0 to 10 looks like this,

The problem today is to evaluate the following integral.

I love naming constants F. F, for fox. There is supposedly a physicist who, in all his papers, names all his constants variations on ‘k’.

frac(1/x) looks like the following.

As x gets bigger, 1/x goes from one integer to the next faster and faster – hence the faster transitions in frac(1/x) seen as x goes to 0. But, can we calculate the area under these multitudinous curves? And is it anything nice at all?

And the answer is, interestingly – yes. The first step is to divide the curve up into more managable parts.

Just as with frac(x), there is a discontinuity every time 1/x is an integer – these discontinuities define each of the individual curves in the graph. We can thus break the integral around these discontinuities. Integrating for when 1/x is between 1 and 2, between 2 and 3, 3 and 4, etc. In each of these intervals, frac(1/x) is a continuous curve.

In terms of x then, this breaks the integral into the intervals 1/2 to 1, 1/3 to 1/2, 1/4 to 1/3, etc.

Thus, the first transformation of the integral is this.

So, let’s consider just the integral over one of the intervals.

What is frac(1/x) over one of these intervals? If int(x) is the integer part of a number, int(pi) = 3, for example, we have the relation that x = int(x) + frac(x). Or, in this case, 1/x = int(1/x) + frac(1/x). Over one of these intervals, 1/x goes from n to n+1, but the integer part of 1/x is simply n. We conveniently can ignore what happens exactly at the endpoints. This gives us, using the previous relation, 1/x = n + frac(1/x), or frac(1/x) = 1/x – n, which we can immediately put to good use.

So we get,

This by itself is relatively nice, but we can do better. Consider the partial summation,

We can then calculate F as the limit of F_N, letting N go to infinity. But, expressing the partial sum, we can rearrange it in a nice way, noting the presence of a telescoping sum, and grouping the sums of reciprocals, in a nice way.

Note the addition of the 1+, to make the harmonic sum complete from 1 to N. Thus, jumping back to F, we have,

And … that’s pretty much all you can do. Except for one more very nice thing. As N goes to infinity, ln(N) and the harmonic sum to N become very close, their difference approaching a constant. This constant was first noticed, and given a name, a very long time ago – the Euler-Mascheroni Constant. I find it fascinating that ln(n) and the harmonic sum grow almost equivalently like that, and that constant has long been of interest to me, because I can never find a satisfying way of calculating it. But, this gives us

And this lets us bring everything together nicely,

An interesting calculation.

And now, I must study.

Real Number Picking: An Interesting Calculation

Let x be a random real number, uniformly distributed between 0 and 1. For sanity’s sake, and since it does not effect the calculations, we’ll say that x is never 0.

x defined as such, it has a very nice property. Given two numbers a and b in the interval (0,1], assuming that a is less than b, the probability that a < x < b is given by P(a < x < b) = b – a. For example, the probability that x is less than 0.5 is clearly 0.5, since half the interval is less than 0.5 – but also because P(0 < x < 1/2) = 1/2 – 0 = 1/2. This is me trying to explain probability theory, without explaining probability theory.

Given such a random number x, let [1/x] be 1/x rounded to the nearest integer. Now, the question is this: What is the probability that [1/x] is even?

To calculate the probability of something, we first have to break it down into a convenient set of events. If [1/x] is even, then one of the following must happen: It must equal 0, or 2, or 4, or … any even integer.

So, let’s analyze those terms. First, it’s interesting to note that on x in (0,1], 1/x minimizes at 1. Thus, 1/x can never be rounded to 0. We’ve simplified our computation, at the very least by a single term.

Second, what does it take for [1/x] = 2*n? 1/x must be within a half of 2*n, on either side. In other words, an equivalent event is 2*n – 1/2 < 1/x < 2*n + 1/2. If 1/x is in that range, it will be rounded to 2*n.

Taking the inequality and inverting it, we can re-express it in terms of x by itself – convenient, given our previous discussion of inequalities involving x.

We can now use the stated formula for P(a < x < b) on this interval!

And from there, the rest is algebra.

I might’ve lied when I said it was simple algebra. The above series of fractions, alternating in sign, and with numerators of the odd numbers, is very close to being the Leibniz, or Gregory, formula for Pi.

Applying that, we can reduce our summation, in a most incredible way,

How about that? Pi showing up, in interesting places, yet again. I invite you to try to explain, heuristically, what that pi is doing here, because it is certainly there, no mistake. A quick experiment on a million random numbers gives an experimental probability of 0.49224. The above calculated value is approximately 0.429204. Very good agreement!

And, an interesting calculation.

Fourth of July, and the State of Mathematics

With everything that’s been going on lately, first Farrah Fawcett dying, then Michael Jackson died, then Billy Mays. Then Jeff Goldblum died, then Sarah Palin died. And Michael Jackson is still dead!

I know you must be thinking – Where did he go? Where has that Fox run off to? Where is that fantastic Mr. Fox?

In what is not a non-sequitur, Roald Dahl hosted a TV show in the early 1960’s called Way Out. Sci-Fi, Fantasy, Horror, it was very much in the spirit of The Twilight Zone. I remember it most clearly for the opening sequence, which involved a hand coming up out of a grave and bursting into flames.

Actually, I don’t remember that at all – but I do remember my father describing that to me. Or, at the very least, that’s how I remember him describing it to me. One of those many things he’s said, almost in passing – but it all adds up over time. Building this image of a time, a world. Important things, small things. James Burke. TV shows. People, places. The Wounded Lion statue in Switzerland. So many things.

Important things.

And, I meant to write something about that on Father’s Day, and didn’t. Sorry, DadFox. You are best.

Of course, I’ve been meaning to write so much lately.

Which in turn begs the question – just what is it I -have- been doing?

I’m still in Pittsburgh right now, finishing off some math for the summer. Most notably a course in Calculus of Variations – which is some very interesting and exciting stuff – and a research project/experiment in using Monte Carlo techniques (as well as the Cross-Entropy Method, new exciting stuff) to try and solve ‘hard’ graph theory problems. I will probably write about some of that, soon enough.

But, I would like to get back into the habit of writing. There are so many interesting things that need to be shared and explored.

For instance, consider the following game. Player A and Player B both have a die, and they are rolling them, each with a goal in mind. Player A wants to roll a 1, and then another 1, in order. Player B wants to roll a 1, and then a 2, in that order. They will continue to roll until they get their sequence, 11 and 12 respectively. The winner is whoever gets their sequence first. The question is – who is more likely to win? The obvious answer is that they are equally likely. Various arguments can be made, for example that the probability of rolling a 1 is equal to the probability of rolling a 2. However, since I’m asking the question, you should assume the obvious answer is wrong – and in fact, it is. On average, Player B needs 35 rolls to win, but Player A needs 42. Another reason I like this problem, aside from it being non-obvious, is that the answer is (in part, at least) 42.

One thing I’ve been thinking about a lot lately – and I think is a good starting point to get back into writing about maths – is this: Just what is math? I’ve been ‘doing math’ for an awfully long time, and I’m still not sure I know what it is. I know I’ve gone through phases of knowing, thinking I’ve known … but certainty always fades, leaving the question, “But what do you doooooo?”

At first, math is taught as a tool. Basic arithmetic. Algebra. Calculus. Tools to solve certain kinds of problems. To answer certain kinds of questions. How many sheep to I have? How many sheep do I need? What is the interest on this investment going to be? At this rate of increase, how long until our coastal cities are submerged in water? How much fuel do I need to put a man on the moon?

But, as you continue on – it’s the questions themselves that become important. Asked in slightly different ways, perhaps – what if we want to land on Mars, instead of the moon? What is the square root of negative sheep? Sometimes, the questions come, almost naturally, from the math itself – given a function, is there another function that has the first as a derivative? This leads, naturally, to the entirety of differential equations. Again, more tools to answer more questions. But, the questions continue – even in a branch of math as well studied as differential equations, it’s well known that most interesting differential equations cannot be solved analytically at all. Questions questions questions – always new questions. Bring your differential equation tools to bear on this little gem, which I may discuss sometime. I dare you.

The questions come faster than our ability to answer them, for the most part. Higher level math seems to be, from what I can tell, developing new ways of thinking about these questions – new tools, and frameworks to phrase them in, to try to get at an answer. But these new tools create more questions still.

After a while, it seems as though what math is isn’t the tools, it isn’t the arithmetic or the formulae, it’s the questions themselves. But, I feel as though it’s a symptom of something larger. The mere act of asking a question is a product of thinking about something in a certain way – expressing it in a certain framework. Processing an object, concept, or idea, in a way that allows the question to be asked.

And that, I think, is the core of mathematics. It’s a way of thinking about the world and processing it. And in my mind, it’s a fundamentally scientific way of thinking. Testing, exploring, and questioning.

A drunken physicist once told me that I wasn’t a scientist – I was a philosopher! Gauss, however, declared math to be the Queen of Sciences. I imagine it’s clear who I agree with.

But, at this point, I have veered so far off track it should be clear – I don’t know what math is. There is something I am very excited about. It’s … it’s thinking, it’s exploring. It’s fundamentally creative, inquisitive, and incredibly human. I identify it with math, but, as I think we can all agree, anyone who declares math to be anyone single thing is probably wrong.

I do not know what math is – but I will continue to do whatever it is I do do, because I have an excellent time doing it.

Next up! When I get a chance, several interesting calculations.

Happy Fourth of July!