Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Primes (sorry)

  1. Aug 4, 2008 #1
    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 (Text):

    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
     
     
    Last edited: Aug 4, 2008
  2. jcsd
  3. Aug 4, 2008 #2
    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.
     
  4. Aug 5, 2008 #3
    Ouch!

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

    k
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Primes (sorry)
  1. Prime question (Replies: 3)

  2. Ramsey Primes (Replies: 8)

  3. Prime Numbers (Replies: 1)

  4. Prime ideals (Replies: 9)

  5. Prime Ideals (Replies: 1)

Loading...