I previously commented on the odd solicitation I received from the "Institute of Advanced Scientific Researches". I observed in passing that the name was odd, as most North Americans would be more likely to use "research" instead of "researches".
Over the past couple of days, the Institute has apparently changed its name to the "Institute of Advanced Scientific Research". But instead of thanking me for correcting their English, they are now threatening me.
I have now received several incoherent e-mail messages from "Zahra K. Khalafi" who claims to be the "Director of Institute of Advanced Scientific Research" and accuses me of writing "fake" and "counterfeit" messages. He states he will "take action by the law and we will see you in court in USA or CANAD" [sic] and asks if I am a "Canadian government agent". Really, I have no idea what he is complaining about. I found his institute's solicitation odd, and I said so. I found his Institute's name odd, and he apparently changed it. It seems to me he should be grateful.
If Mr. Khalafi wants to encourage other researchers to join his efforts, inviting people to join editorial boards and then threatening to sue them is probably not the optimal way to go about it.
Wednesday, July 30, 2008
Saturday, July 26, 2008
Another Healie-Feelie Book
The recent flood in my basement ruined a perfectly good book. Actually, the book was perfectly awful: it is Healing Crystals and Gemstones: From Amethyst to Zircon by Flora Peschek-Böhmer and Gisela Schreiber. (I won't say how it came to be in my basement, but I will say that I don't own it.)
This book is typical of the "healing crystal" literature: a lack of understanding of basic geology and chemistry, combined with healing claims that are not substantiated in any way, resulting in dangerous advice for people with serious health conditions.
The book is littered with errors. Even the very first sentence is incorrect, when it claims that all gemstones originate from hot magma. (Opal, for example, can be sedimentary.) The authors claim "jasper ... always has a trigonal structure", when in fact jasper essentially doesn't form crystals at all. On page 150, the authors claim that fluorite is "also known as feldspar", when in fact feldspar is an entirely different mineral. On page 75, the authors confuse native antimony with the mineral stibnite, which is actually antimony sulfide. On page 85 the authors claim that that aragonite is silicon dioxide, not calcium carbonate. The mineral Charoite is consistently misspelled as "Chaorite". They claim that the crystal structure of Herkimer diamonds is similar to that of real diamond, when in fact they crystallize in completely different systems. They claim that kunzite is "aluminum acetate-lithium", when in fact it is a lithium aluminum silicate; no acetate at all is contained in it. They claim that Magnesite "consists almost entirely of pure magnesium", when in fact it is just magnesium carbonate. They claim that Magnesite "was first discovered in Africa", when in fact its co-type localities are in Greece and Italy.
The authors recommend the use of various minerals without noting health problems associated with them. For example, the authors recommend actinolite to stimulate "the inner organs such as the liver and the kidneys", but fail to note that the tiny fibers of actinolite have been associated with severe and potentially life-threatening respiratory disorders. They recommend using orpiment "externally as a powder to treat sexual disorders", but this is not a good idea, as orpiment is arsenic sulfide.
But the most serious problem with the book is the repeated and unsubstantiated health claims, all made without a single reference to any study in support of them. Someone with serious health problems might be persuaded to use the entirely ineffective remedies suggested in this book instead of seeking effective medical treatment. Cancer is unlikely to be helped by toumaline, sugilite, or lapis lazuli. High blood pressure cannot be improved with sodalite, lapis, or chrysoprase. Diabetes sufferers will find no relief with citrine or pyrite. Kidney ailments will not be improved with jade. For ulcers you should see your family doctor, not wear jasper or topaz.
Ahh, well, I doubt any of this will convince the healie-feelie crowd. When they're done with this, they can move on to the other immortal works of Flora Peschek-Böhmer, such as Urine Therapy: Nature's Elixir for Good Health. Urine therapy, in case you didn't know, consists of drinking your own urine. Great idea! You can use it to wash down some crystals of orpiment.
This book is typical of the "healing crystal" literature: a lack of understanding of basic geology and chemistry, combined with healing claims that are not substantiated in any way, resulting in dangerous advice for people with serious health conditions.
The book is littered with errors. Even the very first sentence is incorrect, when it claims that all gemstones originate from hot magma. (Opal, for example, can be sedimentary.) The authors claim "jasper ... always has a trigonal structure", when in fact jasper essentially doesn't form crystals at all. On page 150, the authors claim that fluorite is "also known as feldspar", when in fact feldspar is an entirely different mineral. On page 75, the authors confuse native antimony with the mineral stibnite, which is actually antimony sulfide. On page 85 the authors claim that that aragonite is silicon dioxide, not calcium carbonate. The mineral Charoite is consistently misspelled as "Chaorite". They claim that the crystal structure of Herkimer diamonds is similar to that of real diamond, when in fact they crystallize in completely different systems. They claim that kunzite is "aluminum acetate-lithium", when in fact it is a lithium aluminum silicate; no acetate at all is contained in it. They claim that Magnesite "consists almost entirely of pure magnesium", when in fact it is just magnesium carbonate. They claim that Magnesite "was first discovered in Africa", when in fact its co-type localities are in Greece and Italy.
The authors recommend the use of various minerals without noting health problems associated with them. For example, the authors recommend actinolite to stimulate "the inner organs such as the liver and the kidneys", but fail to note that the tiny fibers of actinolite have been associated with severe and potentially life-threatening respiratory disorders. They recommend using orpiment "externally as a powder to treat sexual disorders", but this is not a good idea, as orpiment is arsenic sulfide.
But the most serious problem with the book is the repeated and unsubstantiated health claims, all made without a single reference to any study in support of them. Someone with serious health problems might be persuaded to use the entirely ineffective remedies suggested in this book instead of seeking effective medical treatment. Cancer is unlikely to be helped by toumaline, sugilite, or lapis lazuli. High blood pressure cannot be improved with sodalite, lapis, or chrysoprase. Diabetes sufferers will find no relief with citrine or pyrite. Kidney ailments will not be improved with jade. For ulcers you should see your family doctor, not wear jasper or topaz.
Ahh, well, I doubt any of this will convince the healie-feelie crowd. When they're done with this, they can move on to the other immortal works of Flora Peschek-Böhmer, such as Urine Therapy: Nature's Elixir for Good Health. Urine therapy, in case you didn't know, consists of drinking your own urine. Great idea! You can use it to wash down some crystals of orpiment.
Strange Solicitation
Today I received an odd solicitation to join the editorial board of a journal I've never heard of, the Journal of Advanced Researches on Computer Science. It is published by an institute I've never heard of, the "Institute of Advanced Scientific Researches".
The solicitation was strange for a number of reasons. First, this "Institute" seems to publish (or want to publish) 16 different journals; yet as I write this, many of them seem to have no editorial board listed. Second, the name of the Institute itself is odd; no native English speaker would be likely refer to "researches", as "research" is typically a mass noun, like "information". Also, the solicitation letter was filled with grammatical errors. Third, I can find no information about this "Institute" online, nor any of the people associated with it, except for the person who wrote the solicitation letter, "Kavin Kalfi".
So, does anyone else know about this "Institute"?
The solicitation was strange for a number of reasons. First, this "Institute" seems to publish (or want to publish) 16 different journals; yet as I write this, many of them seem to have no editorial board listed. Second, the name of the Institute itself is odd; no native English speaker would be likely refer to "researches", as "research" is typically a mass noun, like "information". Also, the solicitation letter was filled with grammatical errors. Third, I can find no information about this "Institute" online, nor any of the people associated with it, except for the person who wrote the solicitation letter, "Kavin Kalfi".
So, does anyone else know about this "Institute"?
Friday, July 25, 2008
Friday Moose Blogging
Here are some photos by my colleague Doug Payne, taken during his recent trip to Algonquin Park. No surprise, there's a moose or two. Moose twins, too.
Thursday, July 24, 2008
SIGAPL dissolved
A sad day for the APL community: SIGAPL, the ACM special interest group on APL, has been dissolved by the ACM SIG governing board.
I first learned APL in 1973 at the IBM Scientific Center in Philadelphia (long gone). At the insistence of my father, I had written to several large computing companies, asking for a summer job. Only IBM replied favorably, and I had a rather intimidating interview with Ken Iverson and Adin Falkoff in their offices on Market Street. To my delight, they hired me for a vague project about whether it was better to learn APL by reading other people's programs first, or writing one's own.
I remember going home with a copy of the APL\360 user's manual, which was initially very mysterious to me, and had an exotic smell like bacon. I had learned programming from Kemeny's book on BASIC, and APL was a revelation. I immediately took to the language and ended up spending the next few years of my life involved in APL in various ways: coding in APL for financial institutions, writing my own extended precision arithmetic package and selling it to IBM, etc. I was programming on IBM machines, using a printing terminal with an APL typeball.
I soon discovered the newsletter of SIGAPL, called "Quote-Quad". (The unusual name comes from the special APL symbol for character input, which was formed by typing a "quad" (shift-L) and overstriking it with a quote (shift-K).) At that time I eagerly awaited every issue, filled with incredible one-liners that accomplished results you would need hundreds of lines in BASIC to duplicate, puzzles like the self-replicating APL expression puzzle (type it in and you get exactly the same result back), and proposals to extend APL in bizarre and mind-expanding ways. It was really the golden age of APL.
It's clear that the passion and excitement about APL has decreased since then, although I still use APL on at least a weekly basis to do experimental mathematics: Dyalog APL on my Sun workstation, and APLX on my Macintosh. In many ways it is far superior to Maple and Mathematica, although the lack of easy availability of extended precision and symbolic arithmetic is a pain. I can code a quick-and-dirty solution to a problem faster in APL than I can in any other language. People who see it always stare open-mouthed: what is that? they say, and they want to borrow a manual.
The dissolution of SIGAPL is the passing of an age.
I first learned APL in 1973 at the IBM Scientific Center in Philadelphia (long gone). At the insistence of my father, I had written to several large computing companies, asking for a summer job. Only IBM replied favorably, and I had a rather intimidating interview with Ken Iverson and Adin Falkoff in their offices on Market Street. To my delight, they hired me for a vague project about whether it was better to learn APL by reading other people's programs first, or writing one's own.
I remember going home with a copy of the APL\360 user's manual, which was initially very mysterious to me, and had an exotic smell like bacon. I had learned programming from Kemeny's book on BASIC, and APL was a revelation. I immediately took to the language and ended up spending the next few years of my life involved in APL in various ways: coding in APL for financial institutions, writing my own extended precision arithmetic package and selling it to IBM, etc. I was programming on IBM machines, using a printing terminal with an APL typeball.
I soon discovered the newsletter of SIGAPL, called "Quote-Quad". (The unusual name comes from the special APL symbol for character input, which was formed by typing a "quad" (shift-L) and overstriking it with a quote (shift-K).) At that time I eagerly awaited every issue, filled with incredible one-liners that accomplished results you would need hundreds of lines in BASIC to duplicate, puzzles like the self-replicating APL expression puzzle (type it in and you get exactly the same result back), and proposals to extend APL in bizarre and mind-expanding ways. It was really the golden age of APL.
It's clear that the passion and excitement about APL has decreased since then, although I still use APL on at least a weekly basis to do experimental mathematics: Dyalog APL on my Sun workstation, and APLX on my Macintosh. In many ways it is far superior to Maple and Mathematica, although the lack of easy availability of extended precision and symbolic arithmetic is a pain. I can code a quick-and-dirty solution to a problem faster in APL than I can in any other language. People who see it always stare open-mouthed: what is that? they say, and they want to borrow a manual.
The dissolution of SIGAPL is the passing of an age.
Wednesday, July 23, 2008
Christian Compassion
From the Toronto Sun comes this heartwarming story of Christian compassion.
Sex offender Patrick White is really, really sorry that he committed fraud and sex-related offenses in the US and Canada. He's really, really sorry that he sexually abused mentally retarded men. In fact, he's so sorry that he will pay for counselling for his victims, but only if it's "Christian counselling".
How generous!
Never fear, White is assured of a place in his Christian heaven, because, as he says, "God has forgiven me".
Sex offender Patrick White is really, really sorry that he committed fraud and sex-related offenses in the US and Canada. He's really, really sorry that he sexually abused mentally retarded men. In fact, he's so sorry that he will pay for counselling for his victims, but only if it's "Christian counselling".
How generous!
Never fear, White is assured of a place in his Christian heaven, because, as he says, "God has forgiven me".
Mark Shea Thinks Scientists Are Stupid, Makes Gaffe
Over at Catholic Exchange, Mark Shea relates an anecdote that demonstrates, for him, that scientists are sadly lacking in emotional intelligence:
Long ago, I remember watching some film about human evolution narrated by Richard Leakey, Jr. It was interesting as such films go, but you got the sense as it went along that it explained everything at the cost of leaving everything out—like scientists in a Far Side cartoon analyzing humor.
The crowning moment of the film, for me, was when Leakey stood in front of the gorgeous twenty-thousand-year-old cave paintings in Lascaux, France and, with genuine puzzlement in his voice, wondered aloud “Why did they do this? What was the purpose?”
I had the distinct impression he would have expressed equal bafflement were he standing in the Louvre. There seemed to be a gene missing somewhere. He was a man who knew a great deal about human origins and yet, however smart he was, there was something about him that was radically out of touch with, well, what it meant to be human. You felt he needed tape on his glasses, a pocket protector, high water trousers and D&D dice in his pocket to complete the image he seemed to project with such earnest unconsciousness.
I'm a little skeptical that the film went exactly as Shea claims it did. People's memories are notoriously unreliable, and events are rewritten in brains to conform to a person's individual narrative: in this case, Shea's commitment to the Catholic faith as the essential guide to understanding the world.
But assuming Shea's memory was correct, he seems to have entirely missed the point of Leakey's question. Shea doesn't seem to have any awareness that there is a debate among archaeologists about Lascaux's purpose. Was it continuously occupied, or only visited periodically? Was it part of a shaman's ritual to improve chances during the hunt, a record of previous successful hunts, or simply a decoration? Why are there no images of reindeer, which formed a major part of the diet of the artists? Do the painted dots really represent an accurate map of the night sky, as suggested by Michael Rappenglueck?
If you have scientific training, then questions like these seem natural and interesting. If you don't, and are immersed in dogma that preaches simple answers to difficult questions, then even asking this kind of question demonstrates some moral failing. I'd wager that Leakey knows a lot more about people, and their goals, desires, and questions, than Mark Shea does.
Long ago, I remember watching some film about human evolution narrated by Richard Leakey, Jr. It was interesting as such films go, but you got the sense as it went along that it explained everything at the cost of leaving everything out—like scientists in a Far Side cartoon analyzing humor.
The crowning moment of the film, for me, was when Leakey stood in front of the gorgeous twenty-thousand-year-old cave paintings in Lascaux, France and, with genuine puzzlement in his voice, wondered aloud “Why did they do this? What was the purpose?”
I had the distinct impression he would have expressed equal bafflement were he standing in the Louvre. There seemed to be a gene missing somewhere. He was a man who knew a great deal about human origins and yet, however smart he was, there was something about him that was radically out of touch with, well, what it meant to be human. You felt he needed tape on his glasses, a pocket protector, high water trousers and D&D dice in his pocket to complete the image he seemed to project with such earnest unconsciousness.
I'm a little skeptical that the film went exactly as Shea claims it did. People's memories are notoriously unreliable, and events are rewritten in brains to conform to a person's individual narrative: in this case, Shea's commitment to the Catholic faith as the essential guide to understanding the world.
But assuming Shea's memory was correct, he seems to have entirely missed the point of Leakey's question. Shea doesn't seem to have any awareness that there is a debate among archaeologists about Lascaux's purpose. Was it continuously occupied, or only visited periodically? Was it part of a shaman's ritual to improve chances during the hunt, a record of previous successful hunts, or simply a decoration? Why are there no images of reindeer, which formed a major part of the diet of the artists? Do the painted dots really represent an accurate map of the night sky, as suggested by Michael Rappenglueck?
If you have scientific training, then questions like these seem natural and interesting. If you don't, and are immersed in dogma that preaches simple answers to difficult questions, then even asking this kind of question demonstrates some moral failing. I'd wager that Leakey knows a lot more about people, and their goals, desires, and questions, than Mark Shea does.
Sunday, July 20, 2008
Rutgers Graduate Student Finds New Prime-Generating Formula
Studying prime numbers is like playing the guitar. No, really, let me explain.
The guitar is a simple instrument: six strings, some frets, a sound hole. You strum with the right hand, and form chords with the left. What could be simpler? Any reasonably coordinated person can learn to play a simple song, such as "Heart of Gold", passably in a few hours.
In the same way, the prime numbers have a simple definition: the integers greater than 1 that are divisible only by themselves and 1. Any reasonably intelligent person can learn to test a small number for primality, or understand Euclid's proof that there are infinitely many prime numbers, in a short amount of time.
Yet the guitar is also fiendishly difficult. Those studying classical guitar know well how some pieces take hundreds of hours to master. Techniques such as tremolo might take years, especially if you start learning as an adult.
In the same way, the prime numbers contain within them enough subtlety that many problems remain unsolved after hundreds of years. Goldbach conjectured in 1742 that every even number greater than 2 is the sum of two primes, and today this conjecture is still unsolved. (It is known to hold for every even number less than 1018.) And a proof of the Riemann hypothesis, which would have extremely important consequences for the distribution of primes, will net you a million dollars from the Clay Mathematics Institute -- probably more than you'll get from appearing on American Idol.
For a long time mathematicians have sought a simple formula that would generate all the prime numbers, or even infinitely many distinct prime numbers. Some have even gone so far as to claim that no such formula exists -- a statement of very questionable veracity that depends entirely on one's definition of "formula". If you define formula to mean "polynomial with integer coefficients", then it's not hard (and I leave it as a challenge to the reader) to prove that no such polynomial can generate only primes, other than the trivial example of a constant polynomial. Euler's polynomial x2 + x + 41 comes close: it generates primes for x = 0, 1, 2, ..., 39, but fails at x = 40.
A slight variation, though, leads to a genuine prime-generating polynomial. It is a consequence of the Davis-Matiyasevich-Putnam-Robinson work on Hilbert's 10th problem that there exists a multivariate polynomial with integer coefficients that takes on only negative and prime values when integers are substituted for the variables, and every prime is generated by some choice of the variables. In 1976, Jones, Sato, Wada, and Wiens actually wrote down such a polynomial. It has 26 variables.
Another prime-generating formula comes from a 1947 paper of W. H. Mills. Mills proved that there exists a real number A such that [ A3n ] is a prime number for all integers n ≥ 1. Here [ x ] is the greatest integer function, the greatest integer ≤ x. Unfortunately, nobody knows a good way to calculate A other than testing the numbers the formula is supposed to generate for primality, and then constructing A by working backwards.
So many people have worked on the prime numbers that it seems unlikely that there could be a simple prime-generating function that has been overlooked until now.
Rutgers graduate student Eric Rowland has defied the odds, however, and has found a new one. In a paper just published in a journal I edit, the Journal of Integer Sequences, Rowland defines his formula and proves it generates only 1's and primes. (1 is generally not accepted as a prime number, for a variety of reasons. For one thing, if 1 were a prime, then positive integers would not have a unique factorization into primes.) To be precise, I should say that the unusual property of the formula was originally conjectured by a team led by Matt Frank at a mathematics summer school in 2003 where Rowland was attending, but it was not proved until now.
Here is Rowland's formula. We define a(1) = 7, and for n ≥ 2 we set
a(n) = a(n-1) + gcd(n,a(n-1)).
Here "gcd" means the greatest common divisor. So, for example, we find a(2) = a(1) + gcd(2,7) = 8. The prime generator is then a(n) - a(n-1), the so-called first differences of the original sequence.
For example, here are the first 23 values of the a sequence:
7, 8, 9, 10, 15, 18, 19, 20, 21, 22, 33, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 69
and here are the first differences of these values:
1, 1, 1, 5, 3, 1, 1, 1, 1, 11, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 23
If we ignore the 1's, then, the Rowland formula starts by generating the primes 5, 3, 11, 3 (again), and 23. The reader can easily program up the formula and find lots more primes. Removing duplicates, the first few are
5, 3, 11, 23, 47, 101, 7, 13, 233, 467, 941, 1889, 3779, 7559, 15131, 53, 30323, ...
Why does it work? The proof is too involved to give here, but it is not that difficult. The interested reader can go to Rowland's paper for the details.
Rowland has been involved with mathematics for some time. He attended UC Santa Cruz and graduated with highest honors in math in 2003. Since then he has been a graduate student at Rutgers University, studying with Doron Zeilberger. Rowland describes himself as an "experimental mathematician", and uses the computer algebra system Mathematica for his experiments. Rowland tells me that he tried to prove the formula from time to time over a four-year period, but once the crucial insight was found, "I had an outline of the proof within a few days and all the details within a few weeks."
Are there any other formulas like Rowland's? Apparently yes. Benoit Cloitre, a French mathematician, recently proved that if you set b(1) = 1 and
b(n) = b(n-1) + lcm(n,b(n-1)) for n ≥ 2,
then b(n)/b(n-1)-1 is either 1 or prime for all n ≥ 2.
Will Rowland's formula lead to more efficient ways to generate large primes? If so, cryptographers would love it. But it seems unlikely. As Rowland explains in his paper, his formula only produces the prime p after first generating (p-3)/2 1's, so it takes a really long time to generate a large prime. He has a method for skipping over those useless 1's, but doing so essentially requires an independent test for primality.
Are there still unsolved properties of Rowland's prime generator? Yes. For example, is there anything special about the choice a(1) = 7? Other choices, such as a(1) = 8, always generate primes and 1's, but others, such as a(1) = 532, do not. (This choice generates 9 after less than 20 steps.) However, Rowland conjectures that for each starting value of a(1), there exists a point after which the first differences are always either 1 or prime. Rowland also doesn't know if his formula eventually generates all odd primes, although he believes it probably does.
Rowland has a number of other projects in the works. He told me, "I'm working on several things, mostly trying to finish up a backlog of papers. But one newer project is putting bounds on the frequency of 1's in the Kolakoski word. Another is something I'm not ready to fully divulge, but it has to do with values of the p-adic logarithm. A longer term project of mine is extending what is known about the arithmetic of Pascal's triangle modulo m and, generally, additive cellular automata."
What problem would Rowland most like to solve? "I'd really like to solve the 3n+1 problem, because I think it would tell us something very interesting about representations of integers. Dividing by 2 in base 2 just means dropping the last 0, and mapping n -> 3n+1 in base 3 just means appending 1. The problem is that we don't know how to get these two bases to talk to each other -- and of course perhaps there isn't a way -- but a solution to the 3n+1 problem might show us how to do this."
Solving the 3n+1 problem would indeed be a great achievement. In the meantime, however, he can take pleasure in his prime formula. Blending simplicity and mystery, Eric Rowland's formula is a delightful composition in the music of the primes, one everyone can enjoy.
Update, July 31 2008: Rowland has his own post describing his discovery.
The guitar is a simple instrument: six strings, some frets, a sound hole. You strum with the right hand, and form chords with the left. What could be simpler? Any reasonably coordinated person can learn to play a simple song, such as "Heart of Gold", passably in a few hours.
In the same way, the prime numbers have a simple definition: the integers greater than 1 that are divisible only by themselves and 1. Any reasonably intelligent person can learn to test a small number for primality, or understand Euclid's proof that there are infinitely many prime numbers, in a short amount of time.
Yet the guitar is also fiendishly difficult. Those studying classical guitar know well how some pieces take hundreds of hours to master. Techniques such as tremolo might take years, especially if you start learning as an adult.
In the same way, the prime numbers contain within them enough subtlety that many problems remain unsolved after hundreds of years. Goldbach conjectured in 1742 that every even number greater than 2 is the sum of two primes, and today this conjecture is still unsolved. (It is known to hold for every even number less than 1018.) And a proof of the Riemann hypothesis, which would have extremely important consequences for the distribution of primes, will net you a million dollars from the Clay Mathematics Institute -- probably more than you'll get from appearing on American Idol.
For a long time mathematicians have sought a simple formula that would generate all the prime numbers, or even infinitely many distinct prime numbers. Some have even gone so far as to claim that no such formula exists -- a statement of very questionable veracity that depends entirely on one's definition of "formula". If you define formula to mean "polynomial with integer coefficients", then it's not hard (and I leave it as a challenge to the reader) to prove that no such polynomial can generate only primes, other than the trivial example of a constant polynomial. Euler's polynomial x2 + x + 41 comes close: it generates primes for x = 0, 1, 2, ..., 39, but fails at x = 40.
A slight variation, though, leads to a genuine prime-generating polynomial. It is a consequence of the Davis-Matiyasevich-Putnam-Robinson work on Hilbert's 10th problem that there exists a multivariate polynomial with integer coefficients that takes on only negative and prime values when integers are substituted for the variables, and every prime is generated by some choice of the variables. In 1976, Jones, Sato, Wada, and Wiens actually wrote down such a polynomial. It has 26 variables.
Another prime-generating formula comes from a 1947 paper of W. H. Mills. Mills proved that there exists a real number A such that [ A3n ] is a prime number for all integers n ≥ 1. Here [ x ] is the greatest integer function, the greatest integer ≤ x. Unfortunately, nobody knows a good way to calculate A other than testing the numbers the formula is supposed to generate for primality, and then constructing A by working backwards.
So many people have worked on the prime numbers that it seems unlikely that there could be a simple prime-generating function that has been overlooked until now.
Rutgers graduate student Eric Rowland has defied the odds, however, and has found a new one. In a paper just published in a journal I edit, the Journal of Integer Sequences, Rowland defines his formula and proves it generates only 1's and primes. (1 is generally not accepted as a prime number, for a variety of reasons. For one thing, if 1 were a prime, then positive integers would not have a unique factorization into primes.) To be precise, I should say that the unusual property of the formula was originally conjectured by a team led by Matt Frank at a mathematics summer school in 2003 where Rowland was attending, but it was not proved until now.
Here is Rowland's formula. We define a(1) = 7, and for n ≥ 2 we set
a(n) = a(n-1) + gcd(n,a(n-1)).
Here "gcd" means the greatest common divisor. So, for example, we find a(2) = a(1) + gcd(2,7) = 8. The prime generator is then a(n) - a(n-1), the so-called first differences of the original sequence.
For example, here are the first 23 values of the a sequence:
7, 8, 9, 10, 15, 18, 19, 20, 21, 22, 33, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 69
and here are the first differences of these values:
1, 1, 1, 5, 3, 1, 1, 1, 1, 11, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 23
If we ignore the 1's, then, the Rowland formula starts by generating the primes 5, 3, 11, 3 (again), and 23. The reader can easily program up the formula and find lots more primes. Removing duplicates, the first few are
5, 3, 11, 23, 47, 101, 7, 13, 233, 467, 941, 1889, 3779, 7559, 15131, 53, 30323, ...
Why does it work? The proof is too involved to give here, but it is not that difficult. The interested reader can go to Rowland's paper for the details.
Rowland has been involved with mathematics for some time. He attended UC Santa Cruz and graduated with highest honors in math in 2003. Since then he has been a graduate student at Rutgers University, studying with Doron Zeilberger. Rowland describes himself as an "experimental mathematician", and uses the computer algebra system Mathematica for his experiments. Rowland tells me that he tried to prove the formula from time to time over a four-year period, but once the crucial insight was found, "I had an outline of the proof within a few days and all the details within a few weeks."
Are there any other formulas like Rowland's? Apparently yes. Benoit Cloitre, a French mathematician, recently proved that if you set b(1) = 1 and
b(n) = b(n-1) + lcm(n,b(n-1)) for n ≥ 2,
then b(n)/b(n-1)-1 is either 1 or prime for all n ≥ 2.
Will Rowland's formula lead to more efficient ways to generate large primes? If so, cryptographers would love it. But it seems unlikely. As Rowland explains in his paper, his formula only produces the prime p after first generating (p-3)/2 1's, so it takes a really long time to generate a large prime. He has a method for skipping over those useless 1's, but doing so essentially requires an independent test for primality.
Are there still unsolved properties of Rowland's prime generator? Yes. For example, is there anything special about the choice a(1) = 7? Other choices, such as a(1) = 8, always generate primes and 1's, but others, such as a(1) = 532, do not. (This choice generates 9 after less than 20 steps.) However, Rowland conjectures that for each starting value of a(1), there exists a point after which the first differences are always either 1 or prime. Rowland also doesn't know if his formula eventually generates all odd primes, although he believes it probably does.
Rowland has a number of other projects in the works. He told me, "I'm working on several things, mostly trying to finish up a backlog of papers. But one newer project is putting bounds on the frequency of 1's in the Kolakoski word. Another is something I'm not ready to fully divulge, but it has to do with values of the p-adic logarithm. A longer term project of mine is extending what is known about the arithmetic of Pascal's triangle modulo m and, generally, additive cellular automata."
What problem would Rowland most like to solve? "I'd really like to solve the 3n+1 problem, because I think it would tell us something very interesting about representations of integers. Dividing by 2 in base 2 just means dropping the last 0, and mapping n -> 3n+1 in base 3 just means appending 1. The problem is that we don't know how to get these two bases to talk to each other -- and of course perhaps there isn't a way -- but a solution to the 3n+1 problem might show us how to do this."
Solving the 3n+1 problem would indeed be a great achievement. In the meantime, however, he can take pleasure in his prime formula. Blending simplicity and mystery, Eric Rowland's formula is a delightful composition in the music of the primes, one everyone can enjoy.
Update, July 31 2008: Rowland has his own post describing his discovery.
Friday, July 18, 2008
Friday Moose Blogging
Here's a great youtube video of 2 baby moose and their mother playing in a sprinkler in an Alaskan backyard.
When a Creationist Says the Sky is Blue...
When a creationist says the sky is blue...
go outside and check.
That's the wise advice of my friend and co-author, Wesley Elsberry.
It seems particularly apt this week, with yet another outbreak of creationist misrepresentation:
I don't think creationists are always dishonest, but (1) they uncritically accept anything that supports their view instead of examining it critically and (2) they are not particularly concerned with making sure that their sources are correct.
go outside and check.
That's the wise advice of my friend and co-author, Wesley Elsberry.
It seems particularly apt this week, with yet another outbreak of creationist misrepresentation:
- Over at Uncommon Descent, William Dembski claims, citing Michael Asher, that "The American Physical Society, an organization representing nearly 50,000 physicists, has reversed its stance on climate change and is now proclaiming that many of its members disbelieve in human-induced global warming." Only problem is, the American Physical Society has done nothing of the sort. Instead, the APS's Forum on Physics & Society has published an issue with two opposing articles, one in favor of the human-caused global warming theory and one attempting to cast doubt on it. The latter article was written by Christopher Monckton, a man with apparently no scientific training who has a history of statements of debatable veracity.
Even Asher himself has been forced to concede that his description of the Forum on Physics & Society's issue was incorrect, admitting in an update at the bottom in a much smaller typeface that "After publication of this story, the APS responded with a statement that its Physics and Society Forum is merely one unit within the APS, and its views do not reflect those of the Society at large." - Next, at The Panda's Thumb, Nick Matzke points out that Casey Luskin gets nearly everything wrong when describing the Alternberg meeting. Luskin claims the NCSE opposed the meeting for political reasons (false; it didn't oppose it at all) and that Rutgers philosopher Jerry Fodor was one of the Alternberg 16 (false, as one can easily check here). Even more importantly, Luskin imagines the meeting as some sort of significant challenge to the theory of evolution, when in fact the participants claim just the opposite.
- Finally, I've been contacted by some cretin named Bill Crofut, who proclaims himself a "an unlettered Traditional Roman Catholic, militant young-Earth Biblical creationist and geocentrist". Crofut proffered a quote by Birch and Ehrlich from a 1967 Nature article as evidence against evolution. Only problem is, the quote was stripped of context and is a well-known quote mine. When confronted with the evidence of his misrepresentation, Crofut told me he was "a son of Satan".
I don't think creationists are always dishonest, but (1) they uncritically accept anything that supports their view instead of examining it critically and (2) they are not particularly concerned with making sure that their sources are correct.
Thursday, July 17, 2008
World Religious Leaders Praise Saudi King's Anti-Atheist Bigotry
Saudi King Abdullah spoke at a Madrid conference sponsored by the Muslim World League, and spoke against religious extremism. Good, as far as it goes.
Unfortunately, he whitewashed the role of religion in the world's problems. According to King Abdullah, religion (especially his) is blameless, claiming that "Islam is a religion of moderation and tolerance". Ironically, the conference apparently took place in Spain instead of Saudi Arabia, because Saudi Arabia is "the only Arab Muslim country to ban all non-Islamic religious practices on its soil, even though it has a large community of expatriates professing other faiths."
Instead, he chose to blame the world's problems on "secularism" and atheists: "If we wish this historic meeting to succeed, we must focus on the common denominators that unite us, namely, deep faith in God, noble principles, and lofty moral values, which constitute the essence of religion" and that the world's problems are "a consequence of the spiritual void from which people suffer when they forget God, and God causes them to forget themselves." Despite blaming the world's problems on atheists, he also denied their existence, claiming that "we all believe in one God, who sent messengers for the good of humanity in this world and the hereafter".
Did any of the 200 religious and political leaders present speak against this anti-atheist bigotry? Nope. Instead, they fell over themselves to praise King Abdulalh. Ronald Lauder, president of the World Jewish Congress, "said the conference was a 'significant and timely development.'" Catholic Cardinal Tauran called it "an act of great courage". Jesse Jackson apparently called the speech "a distinguished one in its contents and noble message" (may not be an exact quote). Abdullah Tariq said, "It is a great beginning of a valuable call from a generous King."
I'm really sick of hypocritical religious leaders telling me that not accepting their wild and unsupported claims about their deities is some sort of moral failing. It's religion that is to blame for Saudi Arabia's medieval treatment of women. It's religion that is to largely blame for the Saudi hijackers who crashed planes into the World Trade towers on September 11. It's religion that is largely to blame for overpopulation and our worsening ecological crisis. Let's have some religious leaders forthrightly admit this, and then we can have some dialogue.
Unfortunately, he whitewashed the role of religion in the world's problems. According to King Abdullah, religion (especially his) is blameless, claiming that "Islam is a religion of moderation and tolerance". Ironically, the conference apparently took place in Spain instead of Saudi Arabia, because Saudi Arabia is "the only Arab Muslim country to ban all non-Islamic religious practices on its soil, even though it has a large community of expatriates professing other faiths."
Instead, he chose to blame the world's problems on "secularism" and atheists: "If we wish this historic meeting to succeed, we must focus on the common denominators that unite us, namely, deep faith in God, noble principles, and lofty moral values, which constitute the essence of religion" and that the world's problems are "a consequence of the spiritual void from which people suffer when they forget God, and God causes them to forget themselves." Despite blaming the world's problems on atheists, he also denied their existence, claiming that "we all believe in one God, who sent messengers for the good of humanity in this world and the hereafter".
Did any of the 200 religious and political leaders present speak against this anti-atheist bigotry? Nope. Instead, they fell over themselves to praise King Abdulalh. Ronald Lauder, president of the World Jewish Congress, "said the conference was a 'significant and timely development.'" Catholic Cardinal Tauran called it "an act of great courage". Jesse Jackson apparently called the speech "a distinguished one in its contents and noble message" (may not be an exact quote). Abdullah Tariq said, "It is a great beginning of a valuable call from a generous King."
I'm really sick of hypocritical religious leaders telling me that not accepting their wild and unsupported claims about their deities is some sort of moral failing. It's religion that is to blame for Saudi Arabia's medieval treatment of women. It's religion that is to largely blame for the Saudi hijackers who crashed planes into the World Trade towers on September 11. It's religion that is largely to blame for overpopulation and our worsening ecological crisis. Let's have some religious leaders forthrightly admit this, and then we can have some dialogue.
Sunday, July 06, 2008
All People of Good Will Agree With Me
Dr. Henry Morgentaler, the single person most responsible for making abortion safe and legal in Canada, was recently given a national award, the Order of Canada. Not surprisingly, the Catholic hierarchy is outraged. But their outrage took a pernicious dimension when Archbishop Thomas Collins of the Toronto archdiocese said in interview that he called on "all people of good will, to protest this act of dishonour".
Archbishop Collins evidently believes that one cannot be a person of good will and still support the right to abortion. I've met a lot of anti-abortion activists. Most are sincere people who, though misguided, honestly believe that they are acting ethically. But so do people who argue for the right to abortion. It is really offensive for the Archbishop to suggest that the only way you can be a "person of good will" is to agree with the Catholic Church's position.
Archbishop Collins evidently believes that one cannot be a person of good will and still support the right to abortion. I've met a lot of anti-abortion activists. Most are sincere people who, though misguided, honestly believe that they are acting ethically. But so do people who argue for the right to abortion. It is really offensive for the Archbishop to suggest that the only way you can be a "person of good will" is to agree with the Catholic Church's position.
Thursday, July 03, 2008
William Carlos Williams with a Handtruck
From my niece Rachel comes this inspired bit of silliness: an English professor couldn't find the departmental handtruck, so he put out a request on the local listserv. In response, he got 12 odes to the missing handtruck, done in the style of William Carlos Williams, John Donne, and other famous poets. I particularly like this one, by Carl Rapp.
This Is Just to Say
I have pinched
the hand truck
that I happened to run across in
a convenient location
and which
you were probably
saving
for your own future toils
Forgive me
it was so “dependable”
so red
and so obviously up for grabs
Can't you just hear Garrison Keillor reciting it?
This Is Just to Say
I have pinched
the hand truck
that I happened to run across in
a convenient location
and which
you were probably
saving
for your own future toils
Forgive me
it was so “dependable”
so red
and so obviously up for grabs
Can't you just hear Garrison Keillor reciting it?
Subscribe to:
Posts (Atom)
