by Eric Rowland
Every year at the NKS Summer School there are lots of systems that are discovered to have interesting behavior. In 2003, one of these was the recurrence a[n] == a[n-1] + GCD[n, a[n-1]]. With initial condition a[1] = 7, several participants empirically discovered that the difference sequence a[n] – a[n-1] is always 1 or prime.
In[1]:= a[1] = 7;
In[2]:= a[n_] := a[n] = a[n - 1] + GCD[n, a[n - 1]]
In[3]:= Differences[a /@ Range[300]]
Out[3]= {1, 1, 1, 5, 3, 1, 1, 1, 1, 11, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, \
1, 23, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, \
1, 1, 47, 3, 1, 5, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, \
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, \
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 101, 3, 1, 1, 7, 1, 1, 1, 1, 11, 3, 1, \
1, 1, 1, 1, 13, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, \
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, \
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, \
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, \
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, \
1, 1, 1, 1, 1, 233, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, \
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, \
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, \
1, 1, 1, 1, 1}
This was a surprising discovery, since previously there was no known reliable prime-generating formula that wasn’t expressly engineered for this purpose.
Several years later, I was able to mathematically prove that this recurrence only produces 1’s and primes, and my paper was published yesterday in the Journal of Integer Sequences. The editor of that journal, Jeffrey Shallit, posted an introduction to the paper that gives nice context and goes into a little more detail than I have here.
July 21, 2008 at 9:45 pm
what do you mean exactly by expressly engineered for this purpose?
is there a real difference between discovery and engineering an algorithm? would you know the difference if I show you a set of engineered formula versus discovered?
Russ
July 22, 2008 at 1:14 am
Yes, you probably can’t always tell the difference. But often it’s a matter of simplicity. I think engineered objects tend to be more complex, in some sense, than objects that were found by search or just randomly written down. It’s a matter of size — the more components, the larger the space you have to search through.
In the case of prime-generating formulas, we can tell that previous formulas were explicitly constructed to generate primes because in practice they don’t generate any primes at all. So they certainly weren’t discovered (by random search) to have this property. For example, Mills’ function (http://mathworld.wolfram.com/MillsTheorem.html), as far as we can tell, requires you to explicitly put in any primes you will ever get out.
July 31, 2008 at 8:33 am
[...] zeta de Riemann publicados há uns anos na Internet. Adenda de 31-7-2008: Eric Rowland publicou aqui o seu próprio post (A simple recurrence that produces complex behavior — and primes!) sobre a [...]
August 2, 2008 at 3:25 am
I created a Demonstration to explore the recurrence, and it was recently published:
http://demonstrations.wolfram.com/PrimeGeneratingRecurrence/
You can grab the source code and play with it yourself, if you’d like.