a(n)=a(n−1)+gcd(n,a(n−1)).

September 6, 2015 4:30 PM

Go ahead: Press the button. A number is printed on the tape. Press again and another number appears. Keep going. A few more. Notice anything special about those numbers? The sequence begins: 5, 3, 11, 3, 23, 3, 47, 3, 5, 3, 101, 3, 7, 11, 3, 13, 233, 3, 467, 3, 5, 3, . . .
posted by Wolfdog (25 comments total)

BTW, bit-player.org is the blog of Brian Hayes. Among other things, he wrote some of the "Computer Recreations" columns for Scientific American back in the '80s. Thanks for reminding me of bit-player. Since google reader died off, I sometimes forget to check on a lot of infrequently updated but very interesting blogs.
posted by smcameron at 4:49 PM on September 6, 2015

Gosh (pardon my language). I hated those "what number comes next in this sequence?" questions on the SAT and GRE exams. I usually got them right, but they made my head hurt.

That one above is particularly painful....

Side query: was there a decent replacement for google reader? I miss it....
posted by CrowGoat at 5:05 PM on September 6, 2015 [1 favorite]

CrowGoat: Feedly.
posted by pdb at 5:33 PM on September 6, 2015 [5 favorites]

I quite like inoreader.
posted by muddgirl at 5:41 PM on September 6, 2015 [3 favorites]

Mod note: Extant suggestions notwithstanding, the recommend-a-reader-replacement discussion should probably be an Ask if folks want to get into it, rather than taking over this thread.
posted by cortex (staff) at 5:47 PM on September 6, 2015 [4 favorites]

80085
posted by jonmc at 5:50 PM on September 6, 2015 [7 favorites]

I hated those questions too. I always came up with a valid sequence that wasn't the one that the examiner was thinking of. I'm pretty sure there's an infinite number of algorithmicly defined sequences that start with any given list of integers.
posted by monotreme at 5:58 PM on September 6, 2015 [1 favorite]

I hated those questions too. I always came up with a valid sequence that wasn't the one that the examiner was thinking of. I'm pretty sure there's an infinite number of algorithmicly defined sequences that start with any given list of integers.

I suspect that there's a proof of that as well.

Yep.
posted by leotrotsky at 6:24 PM on September 6, 2015 [11 favorites]

There's something really aesthetically appealing about this sequence (to me).
posted by spacewaitress at 6:30 PM on September 6, 2015

(mandatory aside for button-based threads)
DON'T PUSH THE BUTTON
posted by oneswellfoop at 6:51 PM on September 6, 2015 [2 favorites]

.
posted by Samuel Farrow at 8:21 PM on September 6, 2015

online encylopedia of integer sequences
posted by jcruelty at 9:13 PM on September 6, 2015 [2 favorites]

Just to be clear, the formula in the title is *not* the formula that produces the sequence.
posted by mark k at 11:15 PM on September 6, 2015

ok so answer please for those of us who didn't have the math unit installed
posted by feckless fecal fear mongering at 11:34 PM on September 6, 2015

For those who want to peek, Google search is a great tool for finding out what a particular sequence signifies.
posted by Devonian at 1:06 AM on September 7, 2015

FFFM: the numbers are prime, which means that they can't be divided evenly by any number except themselves, and 1. For instance, 3, 5, and 7 are prime. 9 isn't prime, because it can be divided by 3. There is at present no formula that gives you (e.g.) the 1000^th prime number: the only way to work it out is to start enumerating numbers, get rid of all the ones that aren't prime, and keep going until you reach the 1000^th one.

Prime numbers are very interesting for all sorts of reasons, and very big primes are used in things like cryptography and computer security. A formula that gave you all the primes and only the primes would be very useful, especially if you didn't have to calculate the ones in between. The weird thing is, though, we have all sorts of formulas that almost do things like that, but they don't quite do it. This one, for instance, will (apparently) generate a list of primes - but it has lots of repetitions and things out of order, so you can't say "well, this very long number is a prime, show me the next 1,000 primes". It's like there's someone behind the scenes doling out formulae, and they're deliberately hiding the good ones from us! But someday ...
posted by Joe in Australia at 1:32 AM on September 7, 2015

I know what prime numbers are. What is the next number in the sequence?
posted by feckless fecal fear mongering at 8:36 AM on September 7, 2015

Follow the link and either read the explanation of the sequence and work it out yourself, or push the actual button until you get to the term you want. It's not intended to be a puzzle to figure out what's next.
posted by Wolfdog at 8:54 AM on September 7, 2015

I guess you missed the part about those of us without math enabled. I'll try asking again, perhaps this time I could get an answer minus a) condescension, and b) snippiness.

What is the next number in the sequence and why?
posted by feckless fecal fear mongering at 9:02 AM on September 7, 2015 [1 favorite]

No really, it's not a guess the next number puzzle.
posted by nom de poop at 9:28 AM on September 7, 2015

FFFM: If all you seriously care about is the next number, then it is 941. The code that actually generates the numbers is quoted in the article:

var n = 2, a = 7; // initial values

function nextG() {
var g = gcd(n, a);
n = n + 1;
a = a + g;
return g;
}

where it then prints the number if g != 1.

But this article is not really about the particular numbers and only a little bit about the particular sequence. Maybe a couple more sentences about the article will help you understand why the article is interesting :)

This article is less about this being a 'next number puzzle' and more a rumination on sequences that generate prime numbers. At first blush, you might think it essentially impossible to create a sequence where every term in the sequence is a prime number. You might think that the _only_ way to get a list of prime numbers is to step through every number and throw out the ones that are not prime -- super inefficient, right? But this sequence does generate only primes, with the catch that terms repeat and are out of order, so still pretty inefficient if you are interested in enumerating all primes. Many sequences for generating only primes exist, actually, and the article talks a bit about them. The cool thing about this sequence though is that the operations needed to generate the primes are pretty simple -- just need to add and find the greatest common divisor, which can be done pretty quickly with the remainder operator.
posted by getao at 10:38 AM on September 7, 2015 [1 favorite]

var n = 2, a = 7; // initial values

function nextG() {
var g = gcd(n, a);
n = n + 1;
a = a + g;
return g;
}

ok so here's the thing: do you have any idea how actually few people (self included) can understand anything about that collection of characters? Might as well be saying abracadabra.

If all this is is a nifty bit of programming that spits out prime numbers, cool. There is a major problem with the framing here if that is the case.
posted by feckless fecal fear mongering at 12:33 AM on September 8, 2015

I suppose a recipe might say something like "Trim a veal filet and slice it into medallions; sweat chopped shallots in olive oil and reserve; sauté the medallions briefly and remove them to a heated plate; deglaze with red wine, add the shallots with a few spoons of reduced stock and then strain it over the medallions." A chef (or even a competent cook) would be able to understand that, but someone without this background would need pages of explanation to be able to understand what's going on and adapt the recipe to their circumstances.

It's the same here: this is a recipe for producing prime numbers in an interesting way. A longer version of it (that skips the boring results which the formula also produces) would be something like this:

Take two numbers, which we will call a and n. The first time you use this formula, a will equal 2 and n will equal 7. Then keep repeating this formula:

Calculate the greatest common divisor of a and n. Call that number g.
Prepare for the next iteration of this formula by adding 1 to n and adding g to a.

If g (the greatest common divisor of a and n) was equal to 1, then skip the next step. Otherwise, g is a prime number. Print it out.

Now do this formula again, but using the new values of a and n.
posted by Joe in Australia at 1:04 AM on September 8, 2015

Mod note: FFFM, it's okay not to totally get this or just not like it, but you need to drop the angry demanding thing here.
posted by taz (staff) at 2:00 AM on September 8, 2015 [3 favorites]

fffm, fwiw, I was trying to figure this thing out too, one result of which was this spreadsheet (self link).

The variables "a", "g", and "n" are put in their eponymous columns.
The row numbers are the different steps in the sequence, e.g. Row 1, is step 1, where we initialize the values.
Every row we step down we reapply the rules
The "a" for this row = the "a" from the previous row plus the "g" from the previous row,
The "g" for this row = the Greatest Common Denominator of this row's "a" and this row's "n"
The "n" for this row = the "n" in the row directly above, plus 1

I can guess why they wanted to skip 1's in the article; as we step down row by row, the procedure makes an more and more 1's.
posted by otherchaz at 2:46 AM on September 8, 2015 [1 favorite]