Built on Facts

Sunday Function

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:

i-d4bb9fe09d6b78eb832985821d8a307f-1.png

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:

i-7b7142f1efa09b47c3b8242f89bcb9f4-graph.png

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.

Comments

  1. #1 Kurt
    August 22, 2010

    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?

  2. #2 Adrian Morgan
    August 22, 2010

    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.

  3. #3 raghuvir jha , india.
    August 22, 2010

    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.

  4. #4 Carl Brannen
    August 22, 2010

    So when do you get the prime number 2?

  5. #5 Matt Springer
    August 23, 2010

    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.

  6. #6 dmab
    August 23, 2010

    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

  7. #7 Anonymous
    August 25, 2010

    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.”

  8. #8 Yehoshau Ya'acov
    November 4, 2010

    Redeuctionally, the science is t = Tv

    The video in posted on your Blog…

    Tky, Yehoshua