## You're reading: Posts Tagged: integer sequences

### Prime-generating functions

A few weeks ago I heard someone casually refer to ‘that formula of Euler’s that generates primes’. I hadn’t heard of this, but it turns out that in 1772 Euler produced this formula:

$f(x) = x^2 + x + 41\text{.}$

Using this, $$f(0)=41$$, which is prime. $$f(1)=43$$, which is also prime. $$f(2)=47$$ is another prime. In fact this sequence of primes continues for an incredible forty integer inputs until $$f(40)=41^2$$. It might generate more primes for higher inputs, but what’s interesting here is the uninterrupted sequence of forty primes.

This got me wondering. Clearly $$f(0)$$ is prime because 41 is prime, so that much will work for any function

$f(x) = x^2 + x + p$

for prime $$p$$, since $$f(0)=0^2+0+p=p$$. Are there other values of $$p$$ that generate a sequence of primes? Are there any values of $$p$$ that generate longer sequences of primes?

I wrote some code to investigate this. Lately, I’ve taken to writing C++ when I need a bit of code, for practice, so I wrote this in C++.

I figured the cases where $$f(0)$$ is prime but $$f(1)$$ isn’t weren’t that interesting, since $$f(0)$$ is trivially prime. In fact, $$f(x)=x g(x)+p=p$$ when $$x=0$$ for any prime $$p$$, but saying so doesn’t seem worth the effort.

So I kept track of the primes $$p$$ whose functions $$f(x)=x^2+x+p$$ generate more than one prime, and the lengths of the sequences of primes generated by each of these. This produced a pair of integer sequences.

I put the primes that work into the OEIS and saw that I had generated a list of the smaller twin in each pair of twin primes. I was momentarily spooked by this, until I realised it was obvious. Since $$f(0)=p$$ and $$f(1)=1^2+1+p=p+2$$, any prime this works for will generate at least a twin prime pair $$p,p+2$$.

What about the lengths of the sequences of consecutive primes generated? The table below shows the sequences of consecutive primes generated for small values of $$p$$. Most primes that generate a sequence produce just two, and $$p=41$$ definitely stands out by generating forty.

I was pleased to see this sequence of lengths of primes generated was not in the OEIS. So I submitted it, and it is now, along with the code I wrote. (I discovered along the way that the version where sequences of length one are included was already in the database.)

Anyway, I amused myself by having some C++ code published, and by citing Euler in a mathematical work. Enjoy: A371896.

### The OEIS now contains 300,000 integer sequences

The Online Encyclopedia of Integer Sequences just keeps on growing: at the end of last month it added its 300,000th entry. Especially round entry numbers are set aside for particularly nice sequences to mark the passing of major milestones in the encyclopedia’s size; this time, we have four nice sequences starting at A300000. These were sequences that were originally submitted with indexes in the high 200,000s but were bumped up to get the attention associated with passing this milestone.

### Solomon Golomb (1932-2016)

“I’m proud that I’ve lived to see… so many of the things that I’ve worked on being so widely adopted that no one even thinks about where they came from.” ((Solomon W. Golomb – 2016 Laureate of the Franklin Institute in Electrical Engineering)) Solomon Golomb (1932-2016)

Solomon Golomb, who died on Sunday May 1st, was a man who revelled in the key objects in a recreational mathematician’s toolbox: number sequences, shapes and words (in many languages). He also carved out a distinguished career by, broadly speaking, transferring his detailed knowledge of the mathematics behind integer sequences to engineering problems in the nascent field of digital communications, and his discoveries are very much still in use today.

### GCHQ Christmas puzzles winners and solutions announced

The first puzzle is a super-fun 25×25 nonogram puzzle

Before Christmas, the benign megasurveillance bods at GCHQ released a set of festive puzzles, in the form of a Christmas card and associated website. An initial nonogram puzzle led to a sequence of increasingly fiendish teasers, and solvers of the final set of puzzles were invited to email in their answers, with the correctest winning a fancy paperweight, signed book and, GCHQ were at pains to stress, not an Imitation-Game-style secret job offer.

### Discovering integer sequences by dealing cards

Let’s play a game:

1. Imagine you have some playing cards. Of course if you actually have some cards you don’t need to imagine!
2. Pick your favourite natural number $n$ and put a deck of $n$ cards in front of you. Then repeat the next step until the deck is empty.
3. Take $2$ cards from the top of the deck and throw them away, or just take $1$ card from the top and throw it away. The choice is yours.

If you pick a small $n$, such as $n=3$, it’s pretty easy to see how this game is going to play out. Choosing to throw away $2$ cards the first time means you’re then forced to throw away $1$ card the next time, but only throwing away $1$ card the first time leaves you with a choice of what to throw away the next time. So for $n=3$ there are exactly $3$ different ways to play the game: throw $2$ then $1$, throw $1$ then $2$, or throw $1$ then $1$ then $1$.

Now, here comes the big question. How does the number of different ways to play this game depend on the size of the starting deck? Or in other words, what integer sequence $a_0$, $a_1$, $a_2$, $a_3$, $a_4$, … do we get if $a_n$ represents the number of different ways to play the game with a deck of $n$ cards? (We already know that $a_3=3$.)

### OEIS Foundation Appeal

If you’ve worked with or used any sequences of integers lately (and let’s face it, you have) you might have looked them up in the OEIS. I’ve used it twice today, and it’s still before 9.30am. As you may have gathered from our extensive banging on about it, we’re huge fans of the Online Encyclopedia of Integer Sequences.

If you have visited their site recently, you might have noticed an extra paragraph of red text near the top – yes, they’re doing a Wikipedia, and asking for their users (which is realistically everyone) to donate so they can keep going. It’s a hugely worthy cause, and here at the Aperiodical, we think it’s worth supporting. The OEIS is owned and maintained by The OEIS Foundation Inc., a nonprofit company.

Head over to the OEIS for lists of integers with various properties, and to find out more.