3x[sup]2[/sup] + 3x + 1, eh?
Hey, that’s one I found while I was trying to get to sleep one night, instead of counting sheep: 3[sup]3[/sup] + 4[sup]3[/sup] + 5[sup]3[/sup] = 6[sup]3[/sup]
If there’s an n^4 in there, it must grow that fast. It doesn’t matter if there’s a subtraction instead of an addition in front of it. In fact, a subtraction sign before the n^4 would mean that all the values after a certain point are negative numbers and hence not primes at all. If there’s a n^5 or some higher power, it grows even faster.
In any case, any formula of the form (a(i)*x^i) + (a(i-1)*x^(i-1)) + (a(i-2)*x^(i-2)) + . . . + (a(2)*x^2) + (a(1)*x) + a(0) clearly can’t produce just primes unless a(0) is 1. (Here a(i), a(i-1), a(i-2), . . . , a(2), a(1), a(0) are integers.) If the integer a(0) is 0, then whenever x is a composite number, the output of the formula is a composite number. If a(0) is 2 or greater, then whenever x is divisible by a(0) the output of the formula is also divisible by a(0). There’s probably a proof that even if a(0) is 1, the output must be sometimes composite, but I can’t come up with it immediately.
I’m not accusing you of lying. I’m saying that you probably either made a mistake in the computer program or your program didn’t actually check as many values as you think you did. You set the program running and didn’t notice that it didn’t actually test very many values.
By what reasoning? The additive inverse of a prime in the naturals still has all the necessary properties–it has exactly two divisors, and whenever it divides a product, it divides one of the factors. It may not be prime in N, but it definitely looks prime in Z.
bryanmcc -
I’m not sure exactly in what sense the FRACTRAN game preserves the process of the Sieve of Eratosthenes. I think it’s actually a much more basic algorithm. I think it’s based on this algorithm:
~ check if N is divisible by N - 1 (subtract repeatedly; find the remainder)
~ check if N is divisible by N - 2
…
~ check if N is divisible by 2
If N is not divisible by any of those, then it must be prime. If at some point we find that it is divisible, jump out of the loop and test N + 1 for primality.
Also, regarding the discrepancy between the lists: I actually wrote a FRACTRAN-1 interpreter in C++ to test them both (this is definitely to date the most work that has gone into an SDMB post by me :)), and they both seem to work just fine, at least up to the first 40 primes (it’s not the most sophisticated prime-generating algorithm, and it gets pretty slow pretty quickly ;)). The list of fractions I posted can be found on page 147 of The Book of Numbers by Conway and Guy.
I’m now almost certain that the formula was working on equal powers of a set of consecutive integers, rather than consecutive powers of the same integer (which, as Wendell points out, grows too quickly).
It’s possible that the testing process was faulty, but I’d be more inclined to dismiss it as that if I had been using a language that was easygoing about unterminated loops and the like (if the 2 to Sqr(p) loop had been unterminated, we would only be checking the result for evenness) - but this wasn’t the case, in fact the language (a compiler implementing a very crude and reduced-instruction version of BASIC -my admission of which I am sure will win me no respect whatever) did not even permit compound calculations on a simgle line;
w=x+(y*z) simply wasn’t possible; it would have to be
w=y*z
W=y+w
The guy I showed it to at work thought it was obvious and did some jiggery-pokery, ending up with a different version, very much like what ultrafilter did above (which my math skills are now too rusty to permit me understanding).