Here's an odd little bit of math for you this Sunday. It's defined in terms of recurrence. Recurrence happens when a function is defined in terms of itself. This happens more than you might think - one famous example is the Fibonacci sequence, which is informally defined by saying "To get the next term in the sequence, add the previous two terms together. The first two terms are 1 and 1." And so you can calculate that the sequence is {1, 1, 2, 3, 5, 8, 13, 21...} and so forth. That sequence turns out to show up in various odd places in math and science, and recursively defined sequences are actually pretty common in physics. This one isn't, as far as I know. It seems to have been discovered in 2003 by students at Stephen Wolfram's NKS Summer School - more on that later. The sequence is defined thus:
This needs an initial value along the lines of the Fibonacci sequence "The first two terms are 1 and 1", and in this case the initial value for the sequence is a(1) = 7. Thus a(2), the second term of the sequence, is equal to a(1) + gcd(2, a(1)).
Here "gcd" refers to the greatest common divisor function. It gives the largest integer that evenly divides the numbers you feed into the function. For instance gcd(18, 12) = 6, because both 18 and 12 can be divided evenly by 6. They can also both be divided by several other numbers, but 6 is the greatest common divisor. So since a(1) = 7 and gcd(2,7) is 1, a(2) = 7 + 1 = 8.
If we calculate the first 50 terms in the sequence, we'll find that they are: 7, 8, 9, 10, 15, 18, 19, 20, 21, 22, 33, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 69, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 141, 144, 145, and 150. If we look at the difference between successive terms, ie, between 7 and 8, between 8 and 9, between 94 and 141 and so forth, we find this daughter sequence: {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}
It appears to be composed mostly of 1s, with a few others thrown in for good measure. But all the ones thrown in seem to be prime numbers. I won't bore you by printing out some absurd number of terms in the sequence, but it will continue to be true. Eric Rowland proved recently that this sequence generates only 1s and primes. The length of the strings of 1s tends to grow larger as you go out, and the primes generated tend to be higher and higher, however it is not yet known whether this sequence eventually generates all the primes. The behavior of this sequence for initial conditions other than a(1) = 7 is not entirely explored. For some other conditions the sequence strictly generates 1s and primes, for others it generates composite numbers before possibly settling down into 1s and primes behavior - but this has not yet been proved.
Here's a figure (from Rowland's paper) which plots the jth occurrence of a non-1 value on the x-axis with the n required to get that value on the y-axis. Lots of regularity, and lots of 1s. Fortunately there's computational shortcuts you can take, as the length of the sequences of 1s is predictable in advance:
There's not much practical use for this. If you want to generate a list of primes, there's vastly more efficient ways. Nonetheless, it's an interesting fact. I suggest reading the Rowland paper for more info, as it's not technically difficult at all.
Now about the fact that this was discovered at the NKS School. Stephen Wolfram is a brilliant guy who most physics and math types think went off the rails with his idea that pretty much everything in physics is really computational in nature. I tend to agree with his critics, not because I (or they) have anything against computation but because so far the idea doesn't really make any predictions and therefore isn't testable. But of course computation is an interesting study in its own right and for all we know it could eventually turn out to have deep relevance in physics. To his credit though, it is certainly possible to discover interesting things by looking at the behavior of simple computational systems. This is one of those interesting things.
- Log in to post comments
Good Post! I understand what you wrote except why does
a(1) = 7? Is that just by definition? Is there is no underlying reason for this?
I think the main application is for people writing those "what is the next number in the sequence" puzzles. I mean:
A: What comes next in this sequence: 7, 8, 9, 10, ?
B: 11.
A: No, you're wrong. It's 15.
dear matt springer , i am your biggest fan in this earth. i always looks your blogs since 2008. i am a third year engineering student here in india. my branch is electrical and electronics. i want to friendship with you . can you give me your mobile number? if yes then send me through gmail. my email id is " raghuvirjha@gmail.com " i want to talk to you. you seem to me an outstanding person. best of luck.
So when do you get the prime number 2?
Right. Should have said all primes other than 2. For that matter I probably should have written a paragraph about why 1 is not defined as a prime in modern math.
2 tends to be a weird prime in other contexts as well. There's more than a few theorems out there which apply only to the odd primes.
vimeo.com/13704095
but with recent revelations about James Randi, I think he likes DICKS!
____________________
THE SECOND COMING!
THE END OF ATHEISM
FOLLOW THE WHITE RABBIT...
...
youtube.com/watch?v=Smwrw4sNCxE
____________________________________________
THE B**BQUAKE - 911
youtube.com/watch?v=yeblvLoVJCA&feature=related
youtube.com/watch?v=cpZZ2PPBzP8&feature=related
youtube.com/watch?v=EvSljPf9on4&feature=related
you are going to pay the price for thisâ¦.
THE RUBBER DUCKY OF PSEUDOSCIENCE III - JAMES RANDI
daddytypes.com/archive/hofman_rubber_duckie.jpg
there is a lot of sh*t to flush!
youtube.com/watch?v=cg2AezJo8aQ
THE HEAD OF THE INFIDEL!
youtube.com/watch?v=ojR-XRt4rrA
Is America burning yet?
Maybe we need some more...
we use the DIVINE against the ESTABLISHMENT... you?
we do better DEMOLITIONS than you, savage...
RENOUNCE YOUR ATHEISM AND JOIN THE SOCIALIST FAITH!
let them know if the MDC continues more people will die...
the WORLD TRADE CENTER PROPHECY - THE DANCE OF DEATH
youtube.com/watch?v=X0Hez25fFrg
FLUSH ATHEISM!
Actually it is a ROYAL FLUSH!!!
Let me show you how ATHEISTS were partially responsible for 911
These ATHEISTS NEED TO BE ON THE TERRORIST WATCH LIST!
You donât even have SCIENCE on your sideâ¦
Youâre a perfect example of when PHILOSOPHY becomes an ENEMY OF LIFE...
stephenlaw.blogspot.com/2010/06/playing-mystery-card.html
not quite samantha with her *supernatural spit*, eh?
this isn't one of your little WORD GAMES...
blasphemy is a DEATH SENTENCE
you people actually BELIEVE the BS you preach!
GOD 1 - atheists 0
youtube.com/watch?v=jQcNiD0Z3MU
Atheists,
you are ENEMIES OF GOD AND ARE GOING TO BE ANNIHILATED...
Repent and turn to God or be destroyed...
YOU HAVE NO CHOICE...
my interpretation of the STATUE FIRE... it symbolizes the SPIRITUAL DEATH of atheism...
salon.com/news/2010/06/15/us_lightning_strikes_jesus_statue
static.guim.co.uk/sys-images/Guardian/Pix/pictures/2010/6/16/1276680110544/The-King-of-Kings-statue--005.jpg
latimes.com/media/photo/2010-06/54332292.jpg
friendlyatheist.com/wp-content/uploads/2010/06/butterjesus-1.jpg
PRINCESS DI IS WEARING A NEW DRESS!
princeofwales.gov.uk/speechesandarticles/a_speech_by_hrh_the_prince_of_wales_titled_islam_and_the_env_252516346.html
______________________________
skepticblog.org/2010/04/06/would-i-ever-pray-for-a-miracle/
Shermer, I WANT TO SEE YOU BEG FOR A MIRACLE...
___________________
we do like your music Lady Gaga, but...
The B**BQUAKE - 911
Let me show you the FATE OF TRAITORS...
loiterink.com/photos/products/182_3424_500x500.jpg
they are incapable of telling the difference between SCIENTIFIC *FACT* AND
RELIGIOUS AND PHILOSOPHICAL *TRUTH*... FATAL ERROR!
they also preach a *VALUE FREE SCIENCE* called *POSITIVISM* that ignores the
inequalities of wealth and power in capitalist civilization...
for a sample taste of PZ Myers' GARBAGE...
scienceblogs.com/pharyngula/2010/06/sunday_sacrilege_imagine_no_he.php
HIJACKING IN PROGRESS!!!
hawaiiwebgroup.com/maui-design/wp-content/uploads/2009/05/website-hijacking.jpg
HIJACKING IN PROGRESS!!!
how can these HEADLESS IDIOTS BET AGAINST GOD!!!
________________________________________
what happens when you LOSE Pascal's Wager...
peterkreeft.com/topics/pascals-wager.htm
____________
you FIGHT PAPER MONSTERS...
THE BOOBQUAKE - 911!
****************************************************
dissidentphilosophy.lifediscussion.net/philosophy-f1/the-boobquake-911-t1310.htm
You need a little garbage disposal, vida supra.
it is not yet known whether this sequence eventually generates all the primes
ALL the primes? That will be quite an "eventually."
http://www.youtube.com/watch?v=xFUli7Ne4o4
Redeuctionally, the science is t = Tv
The video in posted on your Blog...
Tky, Yehoshua