Things we did not know

Stanislaw Ulam was a Polish-American mathematician whose work spanned many areas of both continuous and discrete mathematics. He did pioneering research in chaos theory and Monte Carlo algorithms, and also invented the concept of a measurable cardinal in set theory. His essential modification of Edward Teller’s original H-bomb design is used by nearly all the world’s thermonuclear weapons, while he co-originated the Graph Reconstruction conjecture. His name is also associated with the equally notorious 3n+1 conjecture. Thus he was involved in some strange corners of math.

Today Ken and I want to talk about some strange facts observed by Ulam and others that we did not know or fully appreciate.

Perhaps you can use them, perhaps you may enjoy them, but they are all kind of fun. At least we think so. Ulam’s autobiography Adventures of a Mathematician shows his sense of fun, and he was described by Gian-Carlo Rota in these words:

Ulam’s mind is a repository of thousands of stories, tales, jokes, epigrams, remarks, puzzles, tongue-twisters, footnotes, conclusions, slogans, formulas, diagrams, quotations, limericks, summaries, quips, epitaphs, and headlines. [H]e simply pulls out of his mind the fifty-odd relevant items, and presents them in linear succession. A second-order memory prevents him from repeating himself too often before the same public.

There is another reason for discussing this today. Class is underway and we both are trying to get things going and we wanted to start a discussion out. We are working on a longer, more technical one, about—“that would be telling”—so let us do this now. Note: fifty extra points for where that phrase comes from—with a search.

Even before we come to Ulam’s famous observation about the pattern of prime numbers in a spiral, some things strike us as strange about spirals. Here we mean the simple spiral walk pattern starting from an origin square in the infinite planar lattice: We can begin with any number ${c}$ in place of ${1}$—thus if we begin with ${41}$ this is the same as adding ${40}$ to all the numbers. One basic fact is that if we take any ray from the origin that goes through the center of another cell, then the ${m}$th number skewered along that ray is given by a quadratic function of ${m}$. For instance, the horizontal ray ${1,2,11,28,\dots}$ is given by ${4m^2 - 3m + 1}$, the northeast ray ${1,3,13,31,\dots}$ by ${4m^2 - 2m + 1}$, and the ray of north-northeast knight’s moves ${1,14,59,136\dots}$ by ${16 m^2 - 3m + 1}$. Similar rays originating from other squares also have quadratic formulas.

If we sequence the numbers that fall on full lines rather than rays, however, we do not get a quadratic function. For instance, the numbers that fall on the horizontal axis in order are ${1,2,6,11,19,28,\dots}$ They do not fit any polynomial formula at all—one has to do integer division by 2 (throwing away remainders) to get a formula. Indeed, this sequence doesn’t have an entry in OEIS, the Online Encyclopedia of Integer Sequences. [Update: see this.] Likewise, the northwest-southeast line ${1,5,9,17,25,37,\dots}$ has all the odd squares but no nice formula. Nor does the line of knight moves ${1,14,22,59,75,136,160,\dots}$.

But there is a singular exception. The southwest-northeast diagonal gives ${1,3,7,13,21,31,43,\dots}$, which has the formula ${m^2 + m + 1}$. Why does this happen?

If we add ${40}$ to this sequence, we get: $\displaystyle 41,43,47,53,61,71,83,97,113,131,151,173,197,223,251,281,313,347,383,421,461,\dots$

Each of these numbers is prime. The sequence is all prime until you substitute ${m = 40}$ to get ${40^2 + 40 + 41 = 1,\!681}$, which is ${41^2}$. Of course, this is the famous prime-generating formula of Leonhard Euler. The extreme good fortune of this formula has been “explained” using class-number theory, but we did not notice the strange diagonal exception until writing this post.

## Ulam’s Prime Plot

The story goes that Ulam became bored during a long lecture in 1963, doodled a number spiral like the one pictured above, and circled the primes to see what the plot would look like. He was struck by how many substantially long diagonal segments of primes there were, going northwest as well as northeast.

This also happens if we start the spiral with numbers ${c}$ other than ${1}$. Here is a plot for ${c = 0}$ from Helgi Rudd’s beautiful website devoted to Ulam’s spiral: Of course, ${c = 41}$ gives Euler’s sequence as a huge diagonal swath through the origin, but as Wikipedia’s article notes, the effects of Euler’s formula show up on other diagonals with larger values of ${m}$ even with ${c = 1}$.

Despite connections noted in both sources to earlier theorems and conjectures about quadratic polynomials, it is still considered that this affinity for diagonals has not been sufficiently “explained.” The larger picture that strikes us the most is given immediately on the front page of Rudd’s site. Many unsolved problems in number theory, including the Riemann Hypothesis itself, involve the idea of how much the primes behave like a “random” sequence. This supports belief in the Goldbach Conjecture and the Twin Primes Conjecture, with probabilistic reasoning like Freeman Dyson’s in our previous post.

• If we randomly choose odd numbers with the same density as the primes, then a spiral plot of them looks like “white noise”—nothing like Ulam’s spiral.
• But if we note that odd numbers of the form ${6n+3}$ cannot be prime, and exclude them, then the randomly-generated plots of the same density begin to look streakier.
• Excluding other congruences, and other exclusions noted on the site, makes the pictures look closer and closer to Ulam’s.

Thus the prime pictures exhibit some of their non-random structure, along lines of more-extreme deficiencies shown by George Marsaglia for some 1960s-vintage pseudorandom generators. How the primes can be random and non-random at the same time relates to that other post we’re working on, but “we’re not telling.”

## Binomial Coefficients

In 1947, Nathan Fine proved that almost all binomial coefficients are even. This seems strange to me. More precisely let ${T_{2}(n)}$ be the number of odd binomial coefficients ${\binom{m}{k}}$ with ${0 \le k \le m < n}$. Then ${T_{2}(n)=o(n^2)}$. Even stronger: $\displaystyle .812556n^{\log_{2} 3} \le T_{2}(n) \le n^{\log_{2} 3}.$

See this for some related facts.

## Percentages

This one comes from here.

Let’s say you invest \$10 in the market and you make a 10 percent return. You now have \$11. Now, let’s say you lose 10 percent. Out of \$11, that’s \$1.10 leaving you with \$9.90 which means you are down ten cents on the deal. You gained the same percentage as you lost yet you came out behind.

Well, you might speculate it has to do with the order of the transaction. After all, the 10 percent you lost was bigger than the 10 percent you gained because you were already up on the deal. That means reversing the order should have the opposite effect. Right?

Start with \$10. Now lose 10 percent first. You have nine dollars. Then gain ten percent. That’s 90 cents leaving you with…\$9.90.

Yep. You lost money again.

Strange as it may seem, a gain and a loss of the exact same percentage will always leave you with less cash – regardless of the order in which they occur.

I wonder if we can use this simple but strange fact in some algorithm analysis?

## Your Friends Have More Friends Than You Do

Suppose you take the average ${n}$ of the numbers of friends each of your friends has, and compare that with your own number ${m}$ of friends. Chances are ${n}$ will be significantly higher than ${m}$. This leaves a lot of people wondering, why are my friends more popular, more vivacious, more successful, than I am?

This phenomenon has been well documented on Facebook and other contexts where “friend” is rigorously quantified. It is ascribed to a 1991 paper (titled as above) by the sociologist Scott Feld, but Ken and I would be surprised if it hadn’t already been noted in connection with the collaboration graph of mathematicians. Ken recalls a talk given by Donald Knuth on properties of this graph 30 years ago at Oxford, a few years after a paper by Tom Odda that also cites studies by Ron Graham and others, but has no recollection of this being mentioned.

It is easy to explain in those terms. Think of Paul Erdős, who famously had hundreds of collaborators. Many people were touched by him. But each of them had averages ${n}$ that included Erdős, which alone was probably enough to boost ${n}$ over their own valence ${m}$ in the graph. More generally, let us assign to every node ${u}$ a “collaborativeness potential” ${p_u}$, and consider various ways to generate random graphs in which the probability of an edge ${(u,v)}$ depends on ${p_u}$ and ${p_v}$. For instance, every node ${u}$ might pick a set ${S_u}$ of 100 potential co-authors ${v}$ at random, and the edge is placed with probability ${(p_u + p_v)/2}$. Potential connections within ${S_u}$ will have a higher chance of succeeding with those ${v}$ having ${p_v > p_u}$, who in turn will expect to have more successful connections.

The result is shown with more rigor by Steven Strogatz in this New York Times column. Still, we find it strange as a raw fact of life.

## Open Problems

What is your favorite strange fact?

[fixed ${T_{2}(n)=o(n)}$ to ${o(n^2)}$ for the binomial coefficients; added update about x-axis of Ulam spiral]

1. September 14, 2014 2:24 pm

“almost all binomial coefficients are even”

maybe even more interesting is that if we mark the even ones in pascal’s triangle, we get sierpinski’s sieve.

2. September 15, 2014 4:25 am

Regarding the Percentages one, Nayuki  has noted that it can be nice to use log scales; perhaps “nepers”  or “log points” (1 neper = 100 log points), then in the case you have here, we get first a gain of ~9.5 log points, then a loss of ~10.5 log points, leaving the net gain as -1 log points, and the same result considering the loss first.

3. September 15, 2014 9:59 am

To me, the strangest mathematical fact is Euclid’s proof that there are an infinite number of primes. That was the first number theory proof I had ever seen and was very surprised that it was possible to figure this out.

4. September 15, 2014 10:16 am

\$11^2+12^2+13^2=14^2+15^2\$

• September 15, 2014 1:17 pm

1^2+2^2+3^2+…+24^2 = 70^2

5. September 15, 2014 10:27 am

Typo in Binomial Coefficients section:
T_2(n) = o(n) should read T_2(n) = o(n^2)

• September 15, 2014 2:24 pm

Thanks—fixed. Other examples in these comments are “favorite strange facts”, not other typo fixes. 🙂

6. September 15, 2014 11:11 am

Since 1.1 * 0.9 = 0.9 * 1.1; and in general (1 + x) * (1 – x) = 1 – x^2, which for |x| < 1 gives 1-x^2 < 1; I'm not sure just how unusual this fact is to apply to some algorithm analysis.

7. September 15, 2014 1:43 pm

have long thought that maybe primes were mankinds 1st encounter with mathematical fractals. however there is still not a definitive mathematical definition. but the case is much stronger. it seems while utterly fundamental they are still poorly understood in many ways.

8. September 15, 2014 2:07 pm

I can’t think of a single math fact which wouldn’t feel strange to some extent… but my favorite one’s the Banach–Tarski paradox. Even though the intermediate pieces aren’t measurable, it’s still a strange fact. Wonders of the axiom of choice…

9. September 15, 2014 7:28 pm

I have asked something about the Collatz Problem on an earlier post (math disease) and I am posting it here again…

Let c(n) be the number of steps to convert n to 1 using the Collatz rules. I just noticed that c(5) = 5. Are there any other number n such that c(n) = n? Or is there a simple explanation as to why only 5?

I am just a little bit curious about this and I am thinking it must have some relation with power of 2.

• September 17, 2014 2:02 am

I don’t know if there are other cases, but they are surely much harder to find, simply because 5 is the only solution to the equation 3x+1 = 2 ^(x-1). Other potential cases are therefore the outcome of the Collatz chaos.

• September 18, 2014 2:56 am

I have checked a numbers up to a million and none appear to have the same property. I think that as n grows it becomes very unlikely that c(n) >= n and maybe 5 is the only number with such property. Maybe it has something to do with the equation you have pointed above. Thanks

10. September 15, 2014 9:09 pm

ps, the ulam function aka collatz conjecture seems like one of the most remarkable open problems in math by certain criteria & have banged on it for decades. it has massive research on the subj, hard to even track it all. also terence tao has an interesting blog pg on it. alas though it seems that paradoxically at any given moment, almost nobody is “working on it”. maybe there is some quantifiable phenomenon about that similar to your property on friendship cliques above? anyway more in collatz conjecture experiments

11. September 16, 2014 2:03 am

Congratulations!

12. September 16, 2014 3:23 am

The independence of the Continuum Hypothesis seems quite puzzling to me.

13. September 16, 2014 12:55 pm

Dear Dick,

Congratulations for the Knuth prize.

best,

Rafee Kamouna.

14. September 16, 2014 1:02 pm

The horizontal axis sequence not in the OEIS is there in two parts: Starting with 1, the east path is A054552 and the west path, A054567. Also, as Jerry Friedman has pointed out in alt.usage.english, “that would be telling” goes back to at least 1830 Ireland.

• September 17, 2014 8:40 am

Indeed, many other “parts” (rays) are there; the point is that the combined sequence is not.

• September 17, 2014 9:13 pm

Ah! It belatedly occurred to me to subtract 1 from that sequence, using the 0-based spiral. This is A035608, which occurs in expanding the generating function ${x(1+3x)/((1+x)(1-x)^3)}$. It goes 0, 1, 5, 10, 18, 27, 39, 52, 68, 85,… and has formula ${n^2 + \lfloor n/2 \rfloor}$. The connection to the Ulam spiral is also noted there, by Emilio Apricena in 2009. This “restores the honor of the OEIS” as I see Peter Luschny desired :-).

15. September 16, 2014 2:50 pm

Interesting blog! Some of my favourite strange mathematical facts are:

1)
13^2 = 169
1 + 6 + 9 = 16
16^2 = 256
2 + 5 + 6 = 13

2)
You can prove that there exist two irrationals A and B such that A to the power of B is rational without actually having to know what A and B are. Consider the identity:

(sqrt(2)^sqrt(2))^sqrt(2) = 2

Now, let A = sqrt(2)^sqrt(2) and B = sqrt(2). If A is irrational, then A and B are the two irrationals and the proposition is proven. If, however, A is rational, then A’ = B’ = sqrt(2) are such that A’ ^ B’ = A = rational, and the proposition is again proven, since sqrt(2) is irrational.

3)
My favourite proof of Pythagoras’ theorem, by virtue of dimensional analysis:

Consider a rectangular triangle of hypotenuse c (opposite to vertex C), legs a (opposite to vertex A) and b (opposite to vertex B), and angle alpha between a and c, at vertex B. This triangle is uniquely determined by c and alpha alone.

The area of such triangle – by dimensional arguments – can only be equal to

Area(ABC) = c^2 f(alpha)

where f(alpha) is some dimensionless function of the dimensionless angle alpha.

Now consider the point D on the hypotenuse such that CD is perpendicular to the hypotenuse. It’s easy to see that the angle between the segments AC and CD is also alpha. By the same reasoning as above, the areas of the rectangular triangles BCD and ACD are

Area(BCD) = a^2 f(alpha)
Area(ACD) = b^2 f(alpha)

Thus, since Area(ABC) = Area(BCD) + Area(ACD), and f(alpha) cannot be zero for a non-degenerate triangle, we find that c^2 = a^2 + b^2.

16. September 16, 2014 3:08 pm

Oh, I would also like to let you know about my “proof” that P is not equal to NP. It goes like so: N is shorthand for NO which, in Objective-C, represents the boolean value FALSE, which – in C – has the value 0. Thus, N = 0. Since P is not equal to N, then P is not equal to 0. Now, assume that P = NP. Since P != 0, we can divide both sides of P = NP by P, resulting in 1 = N. But this is a contradiction, since N = 0. Hence, P != NP. 🙂

17. September 16, 2014 3:36 pm

Strange Fact —

“On the average, numbers* are even.”

* positive integers

Because 4 is doubly even, 8 is triply even, 16 is quadruply even, etc.

18. September 17, 2014 12:48 pm

The Prisoner, I’m guessing

19. September 17, 2014 4:02 pm

The fact that almost all binomial coefficients are even is a consequence of the Lucas’ theorem.

20. September 17, 2014 6:07 pm

I spent a bit of time musing about Ulams diagonal primes while stuck in traffic today, and in the end I’m not convinced there’s anything special about them.

Even numbers occupy half the plane in chess-board fashion, so the only patterns you can ever expect to find in the first place are diagonal lines.

So how common are those ?

If I run a couple of trivial simulations where I don’t plot in the prime numbers, but just random odd numbers with a frequency distribution roughly the same as prime numbers I get … Diagonal lines.

I tried to do some basic statistics on the count, direction and lengths of diagonal runs, but found nothing that would tell prime numbers from random numbers apart.

So no, I don’t buy it: It’s just our brains finding patterns, like it finds faces on Mars and Virgins on toast.

• September 17, 2014 8:41 pm

We addressed this in the post by linking to Helgi Rudd’s plots of random odd numbers, devoid of “diagonal Martian canals”, then random plots excluding other congruences. Take a look at his site. Ulam wasn’t blowing smoke, and Scientific American even put this on its cover in March 1964.

21. September 17, 2014 9:48 pm

Speaking of math dis-eases, I had a bad case of Ulam’s Reconstruction Syndrome (URC) all through the 80s. It’s a lot like malaria, with seasonal flare-ups every spring.

22. September 17, 2014 11:47 pm

The Facebook Data Science team has quantified the friendship paradox in this preprint: http://arxiv.org/pdf/1111.4503v1.pdf

“83.6% of users have less friends than the median friend count of their friends. All these individuals experience that more than half of their friends have more friends than they do. For completeness, we also note that 92.7% of users have less friends than the average friend count of their friends”

• September 18, 2014 12:22 am

Thanks!

23. September 18, 2014 8:36 am

As I recall, the first time I saw computer generated fractals was in 1987. I thought there must be some complicated program to generate such things. Then the person who wrote the program showed me that the program was quite short.

I guess this was the strangest mathematical fact I’ve ever seen. Simple programs can generate complicated output.

• September 25, 2014 6:34 am

Regarding computer programs, this is strange that works. One of my favorite, the winner of the Obfuscated C Code contest:
http://www.ioccc.org/1988/phillipps.c

24. December 7, 2014 7:57 am

Easy as heaven! 🙂

25. June 3, 2015 4:05 am

I have found that If a number is a prime number then either (P+1) is a multiple of 6 or (P-1) is a multiple of 6

• June 3, 2015 2:41 pm

“If a number is a prime number then either (P+1) is a multiple of 6 or (P-1) is a multiple of 6”
Not true. It fails for the prime numbers 2 and 3.
It is obvious for all other primes.

26. 