Which powers of 2 do not contain the digit 7?

Which powers of 2 do not contain the digit 7? A quick search reveals the following examples.

2^0 = 1 
2^1 = 2 
2^2 = 4 
2^3 = 8 
2^4 = 16 
2^5 = 32 
2^6 = 64 
2^7 = 128 
2^8 = 256 
2^9 = 512 
2^10 = 1024 
2^11 = 2048 
2^12 = 4096 
2^13 = 8192 
2^14 = 16384 
2^16 = 65536 
2^18 = 262144 
2^19 = 524288 
2^22 = 4194304 
2^23 = 8388608 
2^25 = 33554432 
2^28 = 268435456 
2^33 = 8589934592 
2^41 = 2199023255552 
2^42 = 4398046511104 
2^49 = 562949953421312 
2^50 = 1125899906842624 
2^54 = 18014398509481984 
2^61 = 2305843009213693952 
2^71 = 2361183241434822606848

These exponents are listed in the On-line Encyclopedia of Integer Sequences as A035062.

I have continued the search for exponents up to 10¹⁰, and found no other powers of 2 that do not contain the digit 7. If we suppose that the decimal digits of powers of 2 are random, then it is extremely unlikely that other examples exist. Observe that 2ⁿ has approximately decimal digits, so the probability that 2ⁿ does not contain the digit 7 is approximately rⁿ where

Given that no examples exist for , we can estimate the probability of an additional example via the infinite sum 

This probability is so small that it almost defies comprehension. Imagine that every person in the State of New York picked a random combination for the Powerball lottery, that they all picked the same numbers purely by chance, and they all won the jackpot. Absurd as it is, this event is more probable than finding another power of 2 which does not contain the digit 7, unless there is some hidden pattern in the digits which has escaped our attention.

I wrote a Python program to conduct my search. Since powers of 2 grow very rapidly, it is not efficient to generate all of their digits, so I only kept track of the last 70 digits. If a 7 is not found in the last 70 digits, then the last 400 digits are checked using the three-argument pow function. If a 7 is not found in the last 400 digits, then n is printed, but no further checks are made. Here is my code:

n = 0
N = 1
while 1:
    if not('7' in str(N)) and not('7' in str(pow(2, n, 10**400))):
        print "2^" + str(n)                   
    n += 1
    N = (N * 2) % 10**70

My interest in this question was inspired by a blog post by John D. Cook.

Bayes’ Theorem and the Fake Facebook Lottery Winner

After the recent $587.5 million Powerball jackpot, the following picture was posted to Facebook, where it was shared over 2 million times.

It is not too hard to figure out that the picture is a fake. The most obvious clue is that the numbers are out of order. The numbers on an authentic Powerball ticket are always in ascending order, except for the last number. But I was doubtful for another reason — Bayes’ theorem.

There are two scenarios that must be considered. The first scenario is that Nolan actually did win the jackpot, and he wishes to share his good fortune with a random stranger. The second scenario is that Nolan did not win the lottery, and the picture is a fake. (Other scenarios are theoretically possible, but we will disregard them.)

Let us define some events. Let A be the event that a player selected at random wins the Powerball jackpot, and let B be the event that a player selected at random would make an offer similar to the one shown above. We wish to estimate the conditional probability of A given B. According to Bayes’ theorem, the probability can be computed as follows:

The probabilities in this formula are difficult to estimate, but let’s make an attempt. We know that there were two winners in the drawing, and I will guesstimate that about 20 million people bought tickets, so P(A) = 1/10,000,000.

The other probabilities are more difficult to predict. It certainly seems unlikely that a lottery winner would offer to give $1 million to a complete stranger. Perhaps it’s even more unlikely that a (randomly selected) non-winner would pretend to win the lottery and offer to share it with a stranger. But it does not seem reasonable to suppose that the first event is 10 million times more likely than the second. So we must conclude that the denominator is dominated by its second term, hence P(A|B) must be close to zero. In other words, the picture is (probably) fake.

A function that is surjective on every interval

The intermediate value theorem states that if f is a continuous real-valued function on the closed interval [a, b], and if c is any real number between f(a) and f(b), then there exists c in [a, b] such that f(x) = c. A function that satisfies the conclusion of this theorem is called a Darboux function.

Although every continuous function is a Darboux function, it is not true that every Darboux function is continuous. Perhaps the simplest example is f(x) = sin(1/x) for x not 0, f(0) = 0. The graph of this function is known as the topologist’s sine curve. The importance of this curve lies in the fact that it is connected but not path-connected.

This function is only discontinuous at 0, but the British mathematician John H. Conway constructed a Darboux function that is discontinuous at every point. In fact, it has the stronger property that it is surjective on every nonempty open interval. That is, if a, b, and y are real numbers with a < b, then there exists a real number x such that f(x) = y. This function is called Conway’s base 13 function, because it is defined in terms of the base 13 digits of the argument.

I wish to propose another example of a function that is surjective on every interval. The function is defined as follows:

if the limit exists,

otherwise.

In addition to being surjective on every interval, my function has a number of other appealing properties. It is defined using a simple formula instead of arcane digit manipulations. The function is equal to zero almost everywhere. Most remarkably, it is periodic and every positive rational number is a period.

I challenge the reader to verify these claims for herself or himself. My proof is available here.

What is a tangent line?

In this post I will give my answer to a question from David Wees.

Does anyone know of a good explanation of what tangent lines are that doesn’t dive straight into the definition of the derivative? #mathchat

— davidwees (@davidwees) October 18, 2012

Recall that a secant line to the graph of y = f(x) is a line that intersects the graph in at least one point (p, f(p)). This figure shows a secant line (in blue) to the curve y = x^2 (in red) at the point (1,1).

This particular secant line crosses from above to below, because the secant line lies above the curve when we are immediately left of the intersection point, and it lies below the curve when we are immediately to the right of the intersection point.

We could also draw another secant line that crosses from below to above, as shown here. Note that this new secant line has a greater slope than the previous secant line.

Now we can give a mathematically precise definition of a tangent line. A secant line to the curve y = f(x) at the point (p, f(p)) is said to be a tangent line if the following two conditions are satisfied.

1. Every secant line with lesser slope crosses from above to below at (p, f(p)).
2. Every secant line with greater slope crosses from below to above at (p, f(p)).

The following picture shows a tangent line to the graph of y = x^2. Notice that if the slope were increased then the line would cross from below to above, and if the slope were decreased then it would cross from above to below.

It is tempting to suppose that a tangent line cannot cross the curve, but this is not the case.

In this case, the tangent line crosses from above to below. If the slope were decreased, then it would still cross from above to below. However, if the slope were increased, then it would cross from below to above. This is consistent with our definition of the tangent line.

Credit: The idea for this definition of tangent line was inspired by the book Calculus Unlimited by Jerrold Marsden and Alan Weinstein, which develops calculus without the concept of limit.

Exploring patterns in Pascal’s triangle using Excel

There are many interesting patterns hidden within Pascal’s triangle. For example, if we color every odd number, we obtain a pattern resembling the Sierpinski triangle. (Image credit: Wikimedia commons)

Other patterns can be generated by coloring the numbers according to their remainder after dividing by 3, 4, 5, etc. Many of these patterns are explored in the book Visual Patterns in Pascal’s Triangle by Dale Seymour, and they are analyzed more deeply in a scholarly article by Andrew Granville with the improbable title Zaphod Beeblebrox’s Brain and the Fifty-ninth Row of Pascal’s Triangle.

It is a good activity for students to create these patterns themselves by calculating Pascal’s triangles and coloring the squares. But it is also possible to generate these patterns quickly in Excel using conditional formatting.

Pascal’s triangle can be generated quickly by copying a simple formula. Just enter the number 1 in D3, enter the formula =C3+D3 in D4, and then copy this formula to a square block of cells starting with D4 in the upper left corner.

Since the numbers grow very quickly, it is convenient to use the MOD function to reduce the numbers. I entered a modulus (initially 2) in B3, and changed the formula in D4 to =mod(C3+D3,$B$3). Finally, I created a conditional formatting rule to highlight all cells whose values are greater than 0.

Below is a screenshot of the result. Note that I have zoomed out as far as possible. My Excel spreadsheet is available here. (Warning: 2 MB)

Update: Patrick Honner brought to my attention a nice video by Debra Borkovitz which demonstrates how to create these patterns in Excel.

 

Parabola through three points

Chris Harrow asked the following question on Twitter:

What happens when you rotate a parabola through 3 points?

— Chris Harrow (@chris_harrow) September 8, 2012

My interpretation is that we fix three non-collinear points in the plane, and we wish to describe all parabolas passing through these points. (There are infinitely many of these, since the axis of symmetry need not be vertical.)

For simplicity, I assumed that the three fixed points are (0,0), (1,0), and (0,1). This is reasonable because any three non-collinear points can be moved to (0,0), (1,0), and (0,1) by an affine transformation (linear transformation + translation), and because the image of a parabola under an affine transformation is again a parabola.

The general equation of a conic section is Ax^2 + Bxy + Cy^2 + Dx + Ey + F = 0, where A, B, and C are not all zero. A conic is a parabola (possibly degenerate) if and only if B^2 = 4AC. Since the parabola is assumed to contain (0,0), (1,0), and (0,1), we find that F = 0, A + D = 0, and C + E = 0. Furthermore, A cannot be zero, since we cannot draw a horizontal parabola through these points. So we may assume, after dividing through by A, that A = 1.

Combining these equations leaves us with a one-parameter family of parabolas:

I created a GeoGebra animation to explore how changing the value of B affects the parabola. It would be interesting to explore the curves traced out by the vertex and the focus as B varies. Wolfram Alpha produced some formulas, but they are not easy to interpret.

Arranging numbers in a grid: Solution

In a previous post, I described the problem of counting arrangements of the numbers 1 through 16 in a 4×4 grid so that squares with consecutive numbers never touch, even at a corner.

This is a difficult problem, because the set of solutions has little obvious structure. It seems unlikely that a simple formula would exist. On the other hand, naive brute-force is not effective, because there are 16! = 20,922,789,888,000 permutations. Even using a computer, this is too many possibilities to check.

The Monte Carlo method is an effective way to estimate the number of solutions. We simply generate a large number of random arrangements, and count the arrangements which have no consecutive numbers touching.  When I ran this simulation with one million trials, there were 838 successes; so the estimated total number of solutions is 16! * 838 * 10^-6, which is approximately 17.5 billion.

But I wanted to find the exact number of solutions. After several failed attempts, I settled on a divide-and-conquer algorithm.

For each partition {A, B} of the set {1,2,…,16} into two subsets of equal size, find all valid arrangements of A into the top half of the grid, and find all arrangements of B into the bottom half of the grid. Then we add up the pairs of arrangements that are compatible. An important fact is that compatibility is determined by the two middle rows, so we can “lump” some of the 4×2 arrangements together.

The final answer is 17,464,199,440, which is suspiciously close to the Monte Carlo estimate (other runs were not as close). My Python code is available here.