Primes (sorry)

kenewbie

I was playing around trying to find a function which matches the prime numbers (futile, I know) when I stumbled upon this little thing:

f(n) = n^2 - (n-1)^2 (for n>1, it seems)

which gives

f(2) = 3
f(3) = 5
f(4) = 7
f(5) = 9 (off by -2)
f(6) = 11
f(7) = 13
f(8) = 15 (-2)
f(9) = 17
f(10) = 19

and so on. I only verified this up to n = 32 (at which point you get 32^2 = 1024 and the numbers become cumbersome to work with by hand, for me at least), but it seems like the function f(n) returns prime number n, only with a few false positives thrown in between (at -2 or -4 off).

At least it does not seem to skip any primes :)

I cannot seem to get any obvious patters within the false positives. The gap seem to vary, it is not the case that the function is off only when n itself is prime, and so on. The only thing i can see that the first 32 n implies is that if f(n) is off by -4 then f(n+1) is off by -2 and then f(n+2) = Pn. (well, not Pn, but the next P after f(n-1) at least).

Now I understand that such a simple function which seems so close to the primes must have been extensively studied, so I wondered if anyone knew of any interesting properties here, or perhaps a paper or a book or something.

k

Code:

edit: included below is the table for as far as I went with it, leading zero for readability.

f(02) = 004 - 001 = 3
f(03) = 009 - 004 = 5
f(04) = 016 - 009 = 7
f(05) = 025 - 016 = 9  (-2)
f(06) = 036 - 025 = 11
f(07) = 049 - 036 = 13
f(08) = 064 - 049 = 15 (-2)
f(09) = 081 - 064 = 17
f(10) = 100 - 081 = 19
f(11) = 121 - 100 = 21 (-2)
f(12) = 144 - 121 = 23
f(13) = 169 - 144 = 25 (-4)
f(14) = 196 - 169 = 27 (-2)
f(15) = 225 - 196 = 29
f(16) = 256 - 225 = 31
f(17) = 289 - 256 = 33 (-4)
f(18) = 324 - 289 = 35 (-2)
f(19) = 361 - 324 = 37
f(20) = 400 - 361 = 39 (-2)
f(21) = 441 - 400 = 41
f(22) = 484 - 441 = 43
f(23) = 529 - 484 = 45 (-2)
f(24) = 576 - 529 = 47
f(25) = 625 - 576 = 49 (-4)
f(26) = 676 - 625 = 51 (-2)
f(27) = 729 - 676 = 53
f(28) = 784 - 729 = 55 (-4)
f(29) = 841 - 784 = 57 (-2)
f(30) = 900 - 841 = 59 
f(31) = 961 - 900 = 61

MrJB

If you simplify your function:
f(n) = n^2 - (n-1)^2 = n^2 - ( n^2 - 2n + 1) = 2n - 1
You can see that it produces all the odd numbers. So, your function will produce all the primes (except for 2) and it will give you many false positives since not every odd number is prime.

kenewbie

Ouch!

Thanks a lot. I feel like I should have seen that myself, but alas :)

k

Similar Threads for: Primes (sorry)
Thread	Forum	Replies
More primes..	Linear & Abstract Algebra	8
primes	Brain Teasers	12
primes	Calculus & Beyond Homework	3
primes in 4n+1/3	Linear & Abstract Algebra	5
sum of primes	Linear & Abstract Algebra	13

MrJB	If you simplify your function: f(n) = n^2 - (n-1)^2 = n^2 - ( n^2 - 2n + 1) = 2n - 1 You can see that it produces all the odd numbers. So, your function will produce all the primes (except for 2) and it will give you many false positives since not every odd number is prime.

kenewbie	Ouch! Thanks a lot. I feel like I should have seen that myself, but alas :) k