Month: October 2013

Prime-generating fractions

Posted on by John

I posted a couple prime-generating fractions on Google+ this weekend and said that I’d post an explanation later. Here it goes.

The decimal expansion of 18966017 / 997002999 is

.019 023 029 037 047 059 073 089 107 127 149 173 199 227 257 …

where each group of three digits is a prime number.

The fraction 4099200041 / 999700029999 produces primes in groups of four digits:

.0041 0043 0047 0053 0061 0071 0083 0097 0113 0131 0151 0173 0197 0223 0251 0281 0313 0347 0383 0421 0461 0503 0547 0593 0641 0691 0743 0797 0853 0911 0971 1033 1097 1163 1231 1301 1373 1447 1523 1601…

What’s going on here? Both fractions come from infinite sums involving prime-generating polynomials. No polynomial in one variable will generate only primes, but several do produce a long sequence of primes.

Euler discovered in 1772 that n2 – n + 41 is prime for values of n from -40 to 40. The second fraction above comes from Euler’s polynomial:

\frac{4099200041}{999700029999} = \sum_{n=1}^\infty \frac{n^2 - n +41}{10^{4n}}

The digits in the decimal expansion stop being prime after the 40th quartet because Euler’s polynomial isn’t prime for n = 41.

The first fraction above comes from a similar polynomial discovered by Legendre, n2 + n + 17. It produces primes for n = -16 to 15.

\frac{18966017}{997002999} = \sum_{n=1}^\infty \frac{n^2 + n +17}{10^{3n}}

You can make your own prime-generating fraction by finding a prime-generating polynomial and using the process above. Euler’s polynomial produces 4-digit primes before becoming composite, so the denominator in the sum is 104n. Legendre’s polynomial produces 3-digit primes for the corresponding denominator in the sum is 103n.

Related math posts

 

Frequently asked questions

Posted on by John

Here, in no particular order, are a few questions people frequently ask me.

What kind of work do you do?

I’m a consultant working in math, statistics, and computing. Sometimes this means modeling, coming up with a mathematical description of a problem and seeing what I can learn from it. Sometimes this means seeing what can be learned from a set of data and determining what to do next, what decisions to make, what data to collect next, etc. Sometimes this means developing software, especially coming up with algorithms to implement math models efficiently.

I also teach. I’ve taught undergraduate and graduate courses in math and statistics. I’m not doing any classroom teaching these days, but teaching is a component of my consulting. Sometimes I serve as an interpreter, helping non-technical people digest technical material, and sometimes people ask for technical mentoring. I’ve also done some expert testimony, which is kind of a form of teaching.

Can you recommend an introductory statistics book?

No.

What programming language do you use?

In the last year or so I’ve used C++, Python, C#, R, Mathematica, sed, awk, and a little JavaScript. Over my career I’ve written more C++ than anything else, and lately I’ve mostly used Python. I’ve also worked with Perl, Java, and PowerShell, though not recently.

Why do you prefer Python to R?

I’d rather do math in a general-purpose language than do general-purpose programming in a math language.

R is designed for interactive statistical computing, and it’s good for that. But I do a lot more than interactive statistical computing. Even on a statistical project, there’s usually non-statistical work to do, such as munging text files or creating a user interface. The statistical software may just be one component in a larger system. It’s easier to do general programming in a language designed for general programming.

I like using Python for convenience or C++ for speed.

How do you charge for consulting?

My first choice is to charge by the project if a project is well-defined. But if that’s not possible, or if a project is open-ended, I’ll charge by the hour.

How do you run your Twitter accounts?

I use my personal account live and I mostly schedule my daily tip tweets in advance.

Why don’t you use XeTeX?

This may seem like an odd question, but it’s actually one I get very often. On my TeXtip twitter account, I include tips on how to create non-English characters such as using \AA to produce Å. Every time someone will ask “Why not use XeTeX and just enter these characters?”

If you can “just enter” non-English characters, then you don’t need a tip. But a lot of people either don’t know how to do this or don’t have a convenient way to do so. Most English speakers only need to type foreign characters occasionally, and will find it easier, for example, to type \AA or \ss than to learn how to produce Å or ß from a keyboard. If you frequently need to enter Unicode characters, and know how to do so, then XeTeX is great.

Can I use your code?

If I post code online, you’re free to use it however you wish. This page has links to code some people have found useful. And here are some articles with code that I’ve written for Code Project.

How can you test a random number generator?

Here’s a book chapter I wrote on that.

Update: The book chapter covers testing a non-uniform random number generator built on a solid uniform random number generator. This is the case most people care about. Not many people write their own core generator, nor should they. But I’ve also written a few posts on testing uniform generators with DIEHARDER, NIST, and PractRand.

How do you type math characters in HTML?

See this page. I prefer writing math in LaTeX, but when I’m writing HTML I like to stay in HTML if I can. I’ll use LaTeX for displayed equations, but I try to stick to HTML inline so the page doesn’t look like a ransom note.

How can I contact you?

See this page.

By the way, if you send a message to one of my daily tip Twitter accounts, I might not see it. I get more responses there than I can read. It’s better to send me email.

Contrasting Hilbert and DARPA

Posted on by John

This morning I ran across a list of 23 math problems compiled by DARPA [link went away]. I assume their choice of exactly 23 problems was meant to be an allusion to Hilbert’s famous list of 23 math problems from 1900.

Some of Hilbert’s problems were a little broad, but most had crisp mathematical statements. DARPA’s list is the opposite: a few of the questions have a crisp statement, but most are very broad. Hilbert’s problems were pure. DARPA’s problems are applied.

One of the questions that stood out to me concerns computational duality.

Duality in mathematics has been a profound tool for theoretical understanding. Can it be extended to develop principled computational techniques where duality and geometry are the basis for novel algorithms?

I think it’s safe to say the answer is “yes” because it already has been done to some degree, though the question remains as to how much more can be done.

Fibonomial coefficients

Posted on by John

Binomial coefficients can be defined by

{n \choose k} = \frac{n(n-1)(n-2)\cdots(n-k+1)}{k(k-1)(k-2)\cdots 1}

Edouard Lucas defined the Fibonomial coefficients analogously by

{n \choose k}_{\cal F} = \frac{F_nF_{n-1}F_{n-2}\cdots F_{n-k+1}}{F_kF_{k-1}F_{k-2}\cdots F_1}

where Fj is the jth Fibonacci number.

Binomial coefficients satisfy

{n \choose k} = {n-1 \choose k} + {n-1 \choose k-1}

and Fibonomial coefficients satisfy an analogous identity

{n \choose k}_{\cal F} = F_{k-1}{n-1 \choose k}_{\cal F} + F_{n-k+1}{n-1 \choose k-1}_{\cal F}

Incidentally, this identity can be used to show that Fibonomial coefficients are integers, which isn’t obvious from the definition.

Similar math posts

Visualizing suffix primes

Posted on by John

A few months ago I wrote about suffix primes, prime numbers such that all their “suffixes” are prime. For example, 653 is prime, and it’s a suffix prime because 53 and 3 are primes.

James Griffin pointed out that the primes have a natural tree structure, the parent of each number being that number with its most significant digit removed. There are two separate trees: one for numbers ending in 3 and another for numbers ending in 7. The numbers 2 and 5 are isolated nodes with no descendants.

There are 4260 suffix primes, about half ending in 3 and half ending in 7. A full list is available here. The graph of either tree is a mess, but here we show the first three levels of the graph for numbers ending in 3.

And here’s the corresponding graph for numbers ending in 7.

How bushy are these trees? The number of nodes at each level increases up to a maximum of 545 nodes at level 9 then decreases. The levels of the suffix primes in their respective trees is given in the histogram below.

 

How many ways can you parenthesize an expression?

Posted on by John

Mathematical diagrams are usually rectangles, sometimes triangles. So pentagonal diagrams are odd.

Here’s a pentagonal diagram from a paper by John Baez and Mike Stay. Why is it a pentagon?

There are five ways to parenthesize an expression with four terms, and the diagram is showing how all ways of parenthesizing four terms are related.

How do we know that there are five ways to parenthesize four terms? We could list them, but then how do we know we didn’t leave out a possibility?

It turns out that the number of ways to parenthesize an expression with n+1 terms is Cn, the nth Catalan number. An expression for the Catalan numbers can be derived by starting with a recurrence relation that the numbers must satisfy and then producing their generating function. The end result is the following identity:

C_n = \frac{1}{n+1}{2n\choose n}
If we set n = 3, we get C3 = 5, confirming that there are five ways to parenthesize four terms.

The Catalan number pop up in many applications. For example, Richard Stanley has posted a 96-page PDF file of combinatorial problems whose solution involves Catalan numbers.

Here’s an odd observation regarding Catalan numbers. If Cn is an odd Catalan number, then n = 2k – 1. And it appears that if k ≥ 9, the last digit of Cn is always 5, though this has not been proven.

The toolbox metaphor

Posted on by John

Applied mathematicians speak of various areas of math as tools in their toolbox, things that can be used to model various situations: differential equations, Monte Carlo simulation, statistical models, etc.

Maybe palette would be a better metaphor than toolbox. Toolbox implies that a problem has been stated and needs to be solved. A palette suggests an array of possibilities to capture some aspect of reality. Maybe toolbox is a better metaphor for ways to work with a model, but not for forming a model.