In the prime of life (part 2)

A little more searching turned up this paper by I. Korec called “Real time generation of primes by a one dimensional cellular automaton with 9 states”, which is pretty much what it says on the box. He shows a 1D CA where the cell at the origin is in a particular state (“1”) in generation t if and only if t is prime.

The rule list is rather lengthy and he doesn’t explicitly give it (nor did I find it elsewhere). Instead he shows the history for the first 99 generations and says you can infer most of the rules from that; the rules that don’t enter in until after that point he lists. So I cut and pasted his history and wrote a little Python script to extract the rules list, from which I created a Golly .rules file. I guess it would’ve been possible to make the states look like Korec’s symbols but I didn’t bother; I just used different colors. Korec’s states “.”, “/”, “0”, “1”, “L”, “R”, “r”, “V”, and “v” are states 0 through 8, respectively.

The initial state for the CA is just a “0” (state #2 in this rules file) in one cell. The CA will be built toward the right and the first cell will be “0” in non prime generations, “1” (state #3) otherwise. It looks like this at generation 30:Screen Shot 2015-11-04 at 8.13.42 PMAt generations 3, 11, 113, 307, 311, and 1103 the leftmost cell is green, so I’m thinking it works.

 

Advertisements

In the prime of life

Today, Nov 3 (11/3 or 11/03 or 3/11), is the 307th day of 2015. And 3, 11, 113, 1103, 311, and 307 are all prime. Ignore Amazon, THIS is PrimeDay. (But next year it’s March 11, because 308 is not prime, but 71 is.)

So since I’ve been playing with cellular automata lately, here’s some prime CA material.

Dean Hickerson came up with primer, a Life pattern that generates prime numbers, back in 1991. Nathaniel Johnston wrote about it in a 2009 blog post, mentioning twin and Fermat prime variants devised by Hickerson and Jason Summers, and then going on to present patterns that generate Mersenne primes, prime quadruplets, cousin primes, and sexy primes.

Primer looks like this once it gets going:

Screen Shot 2015-11-03 at 10.28.37 AMWhich looks pretty complicated but it isn’t really so much. What you have are some puffers that lay down three rows of period 30 glider guns, one vertical and two horizontal. In the horizontal rows each gun in the top row kills the glider produced by the corresponding gun in the bottom row, unless there’s a gap in the first row’s output in which case the bottom row gun makes a glider: what you have there is an inverter, where a gap in the top row’s output becomes a glider in the bottom row’s, and vice versa.

Coming in to each of the top row guns is a glider which gets kicked back, killing the top row’s glider in the process and creating a gap. That kicked back glider travels up to the vertical row where it gets kicked back again to interact with the top row gun again. Obviously this circuit takes a shorter amount of time for the guns at the left (kicking back to the guns on the bottom of the vertical row) than for the guns at the right (kicking back to guns higher up). In fact what happens is there is a gap every 12 gliders coming out of the first top row gun, every 20 gliders for the second, every 28 gliders for the third… every 4(2n+1) for the nth. After inversion, there’s a glider coming out of the nth bottom row gun every 30\times 4(2n+1) generations. There’s also a puffer seen toward the right that starts up the kickback reactions by sending a glider toward the next vertical gun when it’s ready.

Then there’s a lightweight spaceship gun sending spaceships west every 120 generations. But if a glider comes off the bottom row it kills a spaceship. So the first gun would kill every third spaceship (if nothing killed any others), the second would kill every fifth spaceship, the third would kill every seventh, and so on. Which is just the Sieve of Eratosthenes. What’s left is a spaceship passing a certain point at generation 120n if and only if n is prime.

Hickerson’s primer and three improvements by Jason Summers are included in the patterns folder that comes with Golly, as are the Fermat and twin prime generators. The Fermat generator, also by Summers, has four tubs which are destroyed at about generations 50; 1,490; 30,290; and 7,863,890 (corresponding to the second through fifth Fermat primes 5, 17, 257, and 65537). If a sixth Fermat prime is generated it destroys a pond and shuts the pattern down. Since the sixth Fermat prime is known, as of 2014, to be at least 2^{(2^{33})}+1, the pond will not be destroyed in fewer than about 10^{2,560,000,000} generations, which will take a while depending on your computer.

Also included in the Golly patterns is a CA by Adam P. Goucher (under Calcymon-primer in the Other Rules folder). It’s a 10-state CA with a Moore neighborhood which is designed to allow a primer that’s a little simpler than Hickerson’s Life primer. Goucher’s primer in its initial state looks like this:Screen Shot 2015-11-03 at 11.13.31 AMTwo cells! Here it is after about 70 generations having produced 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, and 31:Screen Shot 2015-11-03 at 11.12.42 AM

It works kind of similarly to Hickerson’s primer; here the kicked back single cell “gliders” (red going up, green going down) get re-kicked with a delay to increase the spacing between, so on the first trip they knock out every third output spaceship (being produced on the diagonal blue line), every fifth one on the second trip, every seventh one on the third, and so on. Much less messy and faster than the Life version, though I don’t know if it can be adapted for Fermat primes, and if so it’ll still take longer than you might want to wait to find the sixth one.

Anyway, happy Prime Day!

Enigma 1775

Spoiler for New Scientist Enigma 1775 “Third Symphony”  (Follow the link to see the puzzle.)

First consider 3-digit cubic numbers, and cubic numbers plus 3. Filtering out all but the ones with one 3, no repeated digits, no zeros, and non multiples of 3, all that’s left is 732. But 732 is not triangular, is not a single-digit prime followed by a 2-digit prime (not (p)(pp)), does not start or end with 3 (not 3xx or xx3), and is not (pp)(p). So none of these work.

Now consider 3-digit triangular numbers. After filtering we have 153, 231, 351, 378, 435. Of these 231 and 435 are products of three primes; neither is 3xx or xx3; one is (p)(pp) and the other is (pp)(p). So these are two of the numbers.

The remaining number must be non triangular, non cubic or cubic plus 3, and have 3 of the 4 remaining properties. Enumerating (p)(pp) and (pp)(p) numbers that pass our filter, there are two numbers with both properties, 237 and 537. But both are not 3xx or xx3, and both are products of only two primes. So our fourth number must be (p)(pp) or (pp)(p) but not both, and must be 3xx or xx3, and must be a product of 3 primes.

Of the (p)(pp) and (pp)(p) numbers, only one is a product of 3 primes, and it’s xx3: 273.

So the three numbers are 231, 273, and 435.

 

Primes at regular intervals

5 is prime. So are 5+6 (11), 5+2*6 (17), 5+3*6 (23), and 5+4*6 (29) — five prime in arithmetic progression. But 35 isn’t prime, and that’s obvious because it’s 5+5*6.

In general no arithmetic progression starting with prime p can have more than the first p entries prime.

But here’s another thing; consider 7+k*6. For k = 0, 1, 2… you have 7, 13, 19, 25, 31, 37, 43, 49. The eighth entry is divisible by 7, of course, but also the fourth entry is divisible by 5. In fact the progression modulo 5 is 2, 3, 4, 0, 1, 2, 3, 4… Clearly one out of every five entries will be divisible by 5.

On the other hand consider 7+k*30: 7, 37, 67, 97, 127, 157, 187, 217… None is divisible by 5, and in fact 7+k*30 mod 5 = 7 mod 5 + (k mod 5) * (30 mod 5) = 2 + 0 = 2. Nor are any of the numbers in the progression divisible by 2 or 3 (or, by implication, 4 or 6) since 30 mod 2 = 30 mod 3 = 0. 187 is 11 * 17, so we only get six primes in this progression, but that’s more than we’d get with any common difference less than 30. (And more than 0, wise guy.)

Generally the progression pkq will contain a composite in its first p1 terms if p1 is a prime < p and q mod p1 ≠ 0.

So let’s say we want to find a progression of seven primes; what do we need? We need one of two things; either p = 7 and q mod p1 = 0 for all primes through 5, or p > 7 and q mod p1 = 0 for all primes through 7. That is, in the first case, q must be a multiple of 2*3*5 = 30. We’ve already seen 30 doesn’t work, but we can try multiples of 30, and we find q = 150 does work: 7, 157, 307, 457, 607, 757, 907 are all prime (and 1057 is a multiple of 7). For the second case q must be a multiple of 2*3*5*7 = 210, so we won’t find a progression with smaller common difference than 150.

In fact, in principle, with q a multiple of 210 we could get a progression of up to ten primes… though not eleven; 210 mod 11 = 1. But we don’t know which multiple of 210 we need, nor which starting prime except that we need p mod 11 = 1 if we want to get ten primes.

Well, a little search program will turn it up. Use p = 199 and q = 210. That gives you, in fact, ten primes: 199, 409, 619, 829, 1039, 1249, 1459, 1669, 1879, 2089. 2299 obviously is a multiple of 11.

With the first nine of these (or the last nine for that matter) we can get a prime magic square:

1669 199 1249
619 1039 1459
829 1879 409

This is the smallest magic square (in the sense of having the smallest magic constant) consisting of primes in arithmetic progression. (The smallest prime magic square, though, is

17 89 71
113 59 5
47 29 101

— see http://mathworld.wolfram.com/PrimeMagicSquare.html.)

The smallest common difference generating a progression of k primes is the kth element (starting with k=1) of: 0, 1, 2, 6, 6, 30, 150, 210, 210, 210… and the smallest corresponding ps are 2, 2, 3, 5, 5, 7, 7, 199, 199, 199… These are A033188 and A033189 in oeis.

Do the prime numbers contain arithmetic progressions of length k for all k? So it was conjectured for a long time, but the conjecture was not proven until 2004.

For more on this, see http://mathworld.wolfram.com/PrimeArithmeticProgression.html.

An Odd Evening

The recent proof of the weak Goldbach Conjecture calls for revisiting this gem, originally published in the 1970s in Manifold and later collected in Seven Years of Manifold: 1968-1980.

An odd evening

by Ian Stewart

As dusk settles gently over the undulating English countryside we find our hero Rosen Crantz, research student, discussing his latest ideas with his supervisor, Prof Guilden Stern, a none-too-successful number-theorist.

Crantz: Guilden, I’m stuck on my research problem.

Stern: What, the one about prime numbers?

Crantz: Yes. I was going to prove it for each prime number in turn, using that paper of Randy and Hartlisnujam…

Stern: You mean A Complete List of all Prime Numbers, Journal of Infinity, volumes 173 onwards?

Crantz: Yes, but they’ve only published the even primes so far – I think they got stuck somewhere.

Stern: I had a letter form Hartlisnujam a few weeks ago. He said they’d started off well with 2 – that’s prime of course – and they decided to run through all the even numbers first in the hope of finding some more. He said they’d got up to about 8346318892823676 so far but hadn’t found any.

Crantz: Perhaps there aren’t any other even primes?

Stern: But what about that theorem of Dirichlet’s you know, the one that says that there are an infinite number of primes in any arithmetic progression? The even numbers form an arithmetic progression, don’t they?

Crantz:I guess so. I’ve forgotten most of what I did at school. It’s very puzzling.

Stern: Perhaps Dirichlet made a mistake? He did with his principle, you know.

Crantz: Wasn’t that Riemann? Anyhow, it seems unlikely. Maybe we could prove there exist infinitely many even primes?

Stern: By modifying Euclid’s proof for arbitrary primes, you mean?

Crantz: Exactly. We’ll work with just even primes and see what happens. Suppose there’s only a finite number…

Stern: We can miss out 2, we know about that…

Crantz: So let’s suppose that there are only finitely many even primes greater than 2, say p1, …,pn. Now what? Euclid forms p=p1…pn+1 and…

Stern: That won’t work. It’s odd.

Crantz: Very odd.

Stern: Ha. So why not define p=p1…pn+2?

Crantz: OK. Then p is even so it must be divisible by some even prime, say q. And q can’t be any of the p’s since they leave a remainder 2 when you divide p by them…

Stern: …and it can’t be two, since if 2 divides p then it divides p1…pn, so it divides one of the p’s… but that p is prime and greater than two so it can’t be divisible by two.

Crantz: So q is an even prime not equal to 2,p1,…,pn,…

Stern: Contrary to our assumption. So there must be an infinite number of even primes altogether.

Crantz: I guess that does it. Dirichlet was right after all.

Stern: I’ll write to Hartlisnujam about it.

Crantz: I wonder if it’ll help my problem?

Stern: What is your problem?

Crantz: Uh… well… I think my girlfriend is…

Stern: Your research problem.

Crantz: Oh, yeah. It’s a sort of converse to Goldbach’s Conjecture.

Stern: You mean “every even number is the sum of two primes?”

Crantz: Yes. I want to prove that every prime is the sum of two even numbers. You see, if I could prove that, then…

Stern: But it’s false, surely? What about 3? If 3 is the sum of two even numbers, then one of them is 2… so the other is 1. And that’s odd.

Crantz: Very odd.

Stern: Ha. You need extra hypotheses. Why not assume your prime is even?

Crantz: I thought of that. But suppose we take an even prime q and assume that q=x+y where x and y are even – say x=2u and y=2v. Then q=2(u+v) so 2 divides q. But q is prime – contradiction.

Stern: So that disproves it for even primes.

Crantz: Does it? I never realised…

Stern: Which means you only need look at odd primes.

Crantz: But I can’t wait for Randy and Hartlisnujam to get to them

Stern: Well, anyway you’ve disposed of half the possible cases.

Crantz: Plus 3, which you did.

Stern: Then write it up and publish it. That way, if you do work out the odd ones, you get two papers out of it.

Crantz: I thought they weighed publications, rather than counting them?

Stern: No, that was before they started printing Mosaic on stone tablets. No; five papers and you’re a lecturer, fifteen a senior lec-

Crantz: Wait! Wait! Where in the proof have we assumed that q is even?

Stern: Oh, where we – no. We didn’t. We haven’t! The same proof works for odd primes too!

Crantz: I can see it now! Falsity of the Converse Goldbach Conjecture by R.Crantz –

Stern: And G. Stern…

Crantz: Yes. We could publish it in the Notices

Stern: The Journal

Crantz: The Bulletin

Stern: The Proceedings

Crantz: The Transactions

Stern: The Annals

Crantz: … The Ivanov Gos. Ped. Inst. Uc. Zap. Fiz. -Mat. Nauki –

Stern: (thumping him on the back) Nasty cough you’ve got there.

Crantz: What a reference!

Stern: Fame! Fame! Oh, wait till I see Stevie Smale…

Crantz: We can present it at the International Congress of Mathematicians. We might even get a Fields Medal.

Stern: Two Fields Medals.

Crantz: I’ll be a professor in no time. They make thousands, you know. Absolutely rolling in it. I hear one of them recently sold his thirteenth century cellar…

Stern: No! Really?

Crantz: And I won’t even have to write thirty-one papers and two –

Stern: I could do a lecture tour in the USA!

Crantz: A sort of Malcolm Muggeridge?

Stern: Not exactly; more a Charles Dickens or a – what was that American chap’s name?

Crantz: Twain?

Stern: No, I’ll hire a car.

Crantz: And I could do a tour of Paris – lunch at the Sorbonne, dinner at the Institut – I might even get to meet Bourbaki! Yes! Yes! (He pauses, suddenly puzzled.) Wait a minute. What about 2?

Stern: 2?

Crantz: 2.

Stern: What of it? Go on, go on!

Crantz: 2=0+2.

Stern: Brilliant.

Crantz: 2 is prime. 0 and 2 are even.

Stern: Oh, BOTHER!

Crantz: Maybe we could patch it up…

Stern: But where have we assumed things are non-zero? I don’t see it. It’s odd.

Crantz: Very odd.

Primary season

Two big math stories both relating to prime numbers:

First, a proof (not yet peer reviewed, but looking solid) of the Weak Goldbach Conjecture (Every odd number greater than 5 can be written as the sum of three prime numbers).

And second, progress toward proving the Twin Primes Conjecture (There is an infinite number of pairs of primes whose difference is 2): proof that there is an infinite number of prime pairs whose separation is less than a finite upper limit, specifically 70 million.

 

Enigma 1740

Spoiler for New Scientist Enigma 1740: “Sudoprime” (Follow the link to see the puzzle.)

Label the squares:

A - - - B
C D - E F
- G H I -
J K - L M
N - - - O

A is 5 and H is 9. C, D, F, I, K, L, M, N, and O must be odd and not 5.

AC must be 53 or 59. Try 59 first:

Then CD must be 97. K cannot be 7 or 9 so must be 1 or 3. Then DGK is 743, 751, or 761. L cannot be 7 or 9 so must be 1 or 3. If DGK is 743 then GHI is 491 and L cannot be 1 or 3. Dead end. If DGK is 751 then GHI is 593 and again L cannot be 1 or 3. Dead end. So DGK is 761, GHI is 691, and L is 3. EIL must be 613. This means O must be 1. F cannot be 1 or 7 or 9 so must be 3; then EF can only be 63 which is not prime. Dead end.

So AC must be 53. CD can be 31 or 37. Try 37:

Same argument as above except we conclude F must be 9, so EF is 69 which is not prime. Dead end.

Then CD is 31. N cannot be 3 or 9 so must be 1 or 7. K, L, and O must be 3 or 7. So LM and MO are 31 and 17 or 71 and 13. Either way M is 1. Try 31 and 17:

Then F is 9. I is 1 or 7. The 3-digit primes ending in 13 or 73 are 113, 173, 313, 373, 613, 673, 773. None is legal for EIL. 

So LM and MO are 71 and 13. Then I is 1 or 3. The 3-digit primes ending in 17 or 37 are 137, 317, 337, 617, 937. Only 617 is legal. Then EF is 67. K is 3. GHI is 491 or 691. But 143 is not prime so DGK is 163. B is 4. The only possibilities for JN are 41 and 47, but we already have BF = 47 so JN is 41.

The grid is:

5 - - - 4
3 1 - 6 7
- 6 9 1 -
4 3 - 7 1
1 - - - 3

and the answers required are 617 and 41.