Rutgers Graduate Student Finds New Prime-Generating Formula | Hacker News Reader

Rutgers Graduate Student Finds New Prime-Generating Formula

recursed.blogspot.com

67 pointsjlhamilton25 comments

The summer school where this was conjectured was http://www.wolframscience.com/summerschool/2003/participants...

As one of the "live experiments" Stephen Wolfram decided to try to find the minimal recursive functions involving arithmetic type operations that produce complex behavior. The article glosses over this, but no one set out to find a function that produced only primes; it just so happened that when enumerating these minimal functions this one was discovered to have a peculiar regularity.

By the way, if you ever discover an efficient way to generate primes, you have a shot at claiming a 100k prize (http://www.eff.org/awards/coop)

Off-topic, but it's interesting how he's reimplemented a substantial fraction of Haskell's Prelude (base library) in Mathematica, probably without knowing it: http://www.math.rutgers.edu/~erowland/programs/ListTricks.m.

The formula (or rather the algorithm) is interesting, but rather impractical. First million of iterations generate only 36 primes, and these are not even sequential:

  3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 47, 53, 
  101, 127, 163, 199, 233, 421, 443, 467, 577, 941, 
  1889, 3779, 7559, 15131, 30323, 60647, 121403, 
  242807, 486041, 972533, 1945649, 3891467, 7783541

the caveat being that the complexity of computing the formula is at best on the order of preexisting techniques, so nifty deep math, but nothing new from a computational point of view (barring more insight happening)

Sure, but nifty deep math is good enough for me.

Since it's a new approach, it's more likely to lead to a better eventual complexity than some technique that's already been milked for all it's worth.

Stay upstream.

I just looked at the article again (blog article, not maths), and I must admit the gcd in the equation does not make it seem so exciting. gcd seems algorithmically very close to other algorithms for computing primes.

On the other hand, playing around with it would probably be fun :-/

Oh, deep math? Is that all?

How boring.

I'm not sure what you mean, there are several legitimate interpretation that come to mind, but could you elaborate?

do you mean a) in the continuum of math that appears on, its deep, but not in the continuum of research mathematics?

b) calling something nifty deep math being overly simplistic?

c) something I'm missing

I was mocking the parent, actually, as if there being "nothing new" computationally somehow made it boring.

Thats fair, but wouldn't it be more constructive to explicitly articulate that?

-- BEGIN TRANSMISSION --

PERHAPS

-- END TRANSMISSION --

Not really.

Man, I went to Rutgers, but it sounds like I picked the wrong major. One of my CS TA's literally did not know what the head and tail of a list are (an American, by the by). And to think, math was just across the hall..

I was an RU math TA. Most of us are not as smart as Eric.

Might be, but the two departments are very different in quality also, at least on the undergrad level (I majored in Math/CS at Rutgers).

This is mostly due to the different nature of the subjects, though - CS enrollment fluctuates hugely with tech fashions, and includes people looking to get ahead in their job, people learning "how computers work", etc. Math, on the other hand, can stay to a more strictly academic curriculum, especially with their honors track.

I forget where I read this (I think something of Alan Kay's), but I like the thought that CS will go the path of biology, on the undergrad level, by breaking up into several fields. Just as "pure" biology majors are separate from the school of pharmacy, "pure" CS majors needs a different focus than future network technicians and Blub programmers.

It really depends. The theory classes are there, you just have to take them. My Discrete II & Algorithmic Analysis class with Professor Kalantari was great and and extremely informative. Other classes that I thought were really interesting, like Compilers and Formal Language and Automata theory sadly only had a few students enrolled. I guess theoretical classes are considered boring, although I guess I could see why others think that when compared to Computer Graphics or something that seems a little more hands on. Now that I'm out though, I do regret not going down the Math/CS route at Rutgers.

Those "unpopular" classes like Formal Languages might not be so unpopular if serious profs taught them, instead of the usual lazy, disorganized people who outsource teaching to the TA's. Maybe some people make a point of avoiding the hard profs, but more people avoid the terrible ones.

> The theory classes are there, you just have to take them.

You're absolutely right, I should have been more specific - I was talking about the required classes, which are mostly taught in large lecture halls (Intro, Algorithms, OS). Another great advantage is how accessible and helpful the professors are, esp. in the smaller classes you mention.

I took a couple of grad level courses with Kalantari, they were great.

Yeah I had that too the first year. The prof got rid of her pretty quickly too. Thankfully though, that situation is not the norm. I had many good TAs while at Rutgers.

I have also developed a Formula that generates only 1 and primes:

  a(n) = 1

I think there might be a bug there, somewhere. I ran it here, and got 4.

You must be using Ruby... ;)

Anyone know whether it's been proven that the formula will generate an infinite number of primes? Or might it start looping back on itself eventually?

Reply on news.ycombinator.com