Does the sequence $ (2\mathbb{N}+1 )^2 +4 $ find primes particularly well?

Question

Here is a sequence I came across while reading and I was wondering if it could be used fairly effectively to find primes: $ (2\mathbb{N}+1)^2+4 $. It's basically taking successive odd numbers, squaring them and adding four to them. The first 9 terms of the sequence contain a whopping 7 primes! There's also quite a few semiprimes. But I'm sure the percentage of primes goes down fairly quickly as you continue the sequence. Still, does this sequence filter for primes particularly well or not?

What about the sequence: $ 1^2+4, (1)(3)+4, 3^2+4, (3)(5)+4, 5^2+4,(5)(7)+4, 7^2+4, ...? $ Does this one do better?

Answer 1

Using $x^2 + x + 41$ for $0 \leq x \leq 999,$ we find 581 primes. The smaller numbers are not the $x$ values, they are just the count of primes. I guess when the count $c$ is from $1 \leq c \leq 40$ we do have $x = c - 1,$ not with larger $c.$

Mon Jul  2 19:50:42 PDT 2018
  1     41   2     43   3     47   4     53   5     61   6     71   7     83   8     97
  9    113  10    131  11    151  12    173  13    197  14    223  15    251  16    281
 17    313  18    347  19    383  20    421  21    461  22    503  23    547  24    593
 25    641  26    691  27    743  28    797  29    853  30    911  31    971  32   1033
 33   1097  34   1163  35   1231  36   1301  37   1373  38   1447  39   1523  40   1601
 41   1847  42   1933  43   2111  44   2203  45   2297  46   2393  47   2591  48   2693
 49   2797  50   2903  51   3011  52   3121  53   3347  54   3463  55   3581  56   3701
 57   3823  58   3947  59   4073  60   4201  61   4463  62   4597  63   4733  64   4871
 65   5011  66   5153  67   5297  68   5443  69   5591  70   5741  71   6047  72   6203
 73   6361  74   6521  75   7013  76   7351  77   7523  78   7873  79   8231  80   8597
 81   8783  82   8971  83   9161  84   9547  85   9743  86   9941  87  10141  88  10343
 89  10753  90  11171  91  11383  92  11597  93  11813  94  12251  95  12473  96  12697
 97  12923  98  13151  99  13381 100  13613 101  14083 102  14321 103  14561 104  15541
105  15791 106  16553 107  16811 108  17333 109  17597 110  17863 111  18131 112  18401
113  18947 114  19501 115  20063 116  20347 117  20921 118  21211 119  21503 120  22093
121  22391 122  22691 123  22993 124  23297 125  23603 126  23911 127  24533 128  24847
129  25163 130  25801 131  27431 132  27763 133  28097 134  28433 135  28771 136  29453
137  30491 138  30841 139  31193 140  31547 141  32261 142  32621 143  32983 144  33347
145  33713 146  35573 147  35951 148  36713 149  37097 150  37483 151  37871 152  38261
153  38653 154  39047 155  39443 156  39841 157  40241 158  41047 159  41453 160  42683
161  44351 162  44773 163  45197 164  46051 165  48221 166  48661 167  49103 168  49547
169  49993 170  50441 171  50891 172  51343 173  51797 174  52253 175  52711 176  53171
177  53633 178  54563 179  55501 180  56923 181  57881 182  58363 183  59333 184  61297
185  62791 186  64303 187  64811 188  66347 189  66863 190  67901 191  68947 192  69473
193  70001 194  71597 195  72671 196  74297 197  74843 198  75391 199  75941 200  76493
201  77047 202  78721 203  79283 204  79847 205  81551 206  83273 207  84431 208  85597
209  86183 210  86771 211  88547 212  92153 213  92761 214  93371 215  93983 216  94597
217  95213 218  96451 219  97073 220  98323 221  99581 222 100213 223 100847 224 101483
225 102121 226 102761 227 104047 228 104693 229 105341 230 110597 231 111263 232 112601
233 113947 234 115301 235 115981 236 116663 237 118033 238 120103 239 121493 240 122891
241 123593 242 124297 243 125003 244 125711 245 126421 246 127133 247 128563 248 129281
249 131447 250 132173 251 133631 252 134363 253 138053 254 138797 255 141041 256 141793
257 142547 258 144061 259 146347 260 147881 261 149423 262 150197 263 152531 264 153313
265 154097 266 154883 267 155671 268 157253 269 158047 270 158843 271 160441 272 162853
273 163661 274 164471 275 169373 276 170197 277 171023 278 171851 279 172681 280 174347
281 176021 282 179393 283 180241 284 181943 285 184511 286 185371 287 187963 288 188831
289 189701 290 190573 291 191447 292 192323 293 193201 294 194963 295 197621 296 199403
297 200297 298 201193 299 204797 300 205703 301 207521 302 208433 303 209347 304 210263
305 213023 306 213947 307 215801 308 216731 309 219533 310 220471 311 221411 312 226141
313 227093 314 229003 315 229961 316 232847 317 234781 318 235751 319 236723 320 238673
321 240631 322 243583 323 245561 324 247547 325 248543 326 249541 327 251543 328 253553
329 255571 330 258613 331 259631 332 260651 333 261673 334 262697 335 263723 336 265781
337 268883 338 270961 339 272003 340 273047 341 274093 342 276191 343 279353 344 280411
345 285731 346 286801 347 287873 348 288947 349 290023 350 291101 351 292181 352 293263
353 294347 354 295433 355 300893 356 301991 357 303091 358 304193 359 305297 360 307511
361 308621 362 311963 363 313081 364 318701 365 319831 366 322097 367 323233 368 327797
369 331241 370 332393 371 337021 372 338183 373 341681 374 346373 375 348731 376 349913
377 351097 378 353471 379 354661 380 355853 381 357047 382 358243 383 359441 384 361843
385 363047 386 365461 387 367883 388 369097 389 372751 390 381347 391 382583 392 383821
393 386303 394 388793 395 391291 396 392543 397 393797 398 396311 399 398833 400 402631
401 403901 402 406447 403 407723 404 410281 405 411563 406 419297 407 420593 408 421891
409 423191 410 424493 411 427103 412 428411 413 433663 414 434981 415 445597 416 446933
417 452297 418 453643 419 454991 420 459047 421 460403 422 464483 423 467213 424 468581
425 472697 426 474073 427 476831 428 478213 429 482371 430 483761 431 487943 432 490741
433 497771 434 499183 435 502013 436 503431 437 504851 438 507697 439 509123 440 510551
441 514847 442 516283 443 517721 444 519161 445 522047 446 523493 447 524941 448 526391
449 527843 450 530753 451 533671 452 535133 453 541001 454 549863 455 551347 456 552833
457 557303 458 560293 459 564793 460 570821 461 572333 462 573847 463 576881 464 578401
465 581447 466 582973 467 587563 468 593711 469 595253 470 599891 471 604547 472 609221
473 610783 474 617051 475 620197 476 623351 477 628097 478 629683 479 631271 480 644047
481 647261 482 648871 483 650483 484 653713 485 655331 486 656951 487 658573 488 660197
489 661823 490 668347 491 674903 492 683143 493 686453 494 688111 495 689771 496 691433
497 693097 498 694763 499 701447 500 703123 501 704801 502 706481 503 708163 504 709847
505 714911 506 723391 507 726797 508 731921 509 738781 510 743947 511 745673 512 747401
513 750863 514 754333 515 757811 516 759553 517 761297 518 763043 519 766541 520 770047
521 773561 522 778847 523 780613 524 782381 525 785923 526 787697 527 789473 528 791251
529 798383 530 800171 531 809141 532 810941 533 816353 534 825413 535 827231 536 830873
537 834523 538 836351 539 847361 540 849203 541 852893 542 860297 543 864011 544 865871
545 867733 546 869597 547 871463 548 873331 549 875201 550 877073 551 880823 552 882701
553 886463 554 894011 555 895903 556 899693 557 901591 558 907297 559 909203 560 911111
561 918763 562 922601 563 924523 564 930301 565 932231 566 936097 567 938033 568 939971
569 941911 570 947743 571 949691 572 951641 573 953593 574 959461 575 971251 576 983113
577 985097 578 987083 579 989071 580 993053 581 997043
Mon Jul  2 19:50:42 PDT 2018

Answer 2

No, this finds primes particularly bad. If you reduce this sequence mod 5, you get $0, 3, 4, 3, 0, 0, 3, 4, 3, 0, 0, 3, 4, 3, 0, 0, \cdots$.

Out of the first $1000$ terms, only $217$ of them are prime.

Answer 3

If you want to take successive odd numbers you need to triple them and add $2$ or $4$ to find prime numbers.

$P_1 = 3 \cdot odd +2 $ or $P_2 = 3 \cdot odd + 4$

This sequence also contains composite numbers (OEIS - A038509), since consecutive numbers of this form get also into multiplication with a particular order. The form:

$3 \cdot even +5$ or $3\cdot even+7$ also works well. All you have to is to check if the number of this form is a prime or composite (HINT: Arithmetic progressions).

Answer 4

The probability that a number of size approximately $x$ is prime is (heuristically) $1/\ln(x)$, so the expected number of primes from a polynomial of degree $2$ for the values $n = 1,2,\ldots,x$ is approximately

$$ \int \frac{1}{\ln(x^2)} \sim \frac{x}{2 \log(x)} $$

Conjecturally, however, you have to take into account the extra information coming from congruences. For example, your polynomial is never divisible by $2$, so this should mean there are twice as many primes. Similarly, your polynomial is never divisible by $3$, whereas a random number is only prime to three $1 - 1/3$ of the time. OTOH, your polynomial is divisible by five for $1 - 2/5$ of the time instead of $1-1/5$. For a general prime $p$, a random number is not divisible by $p$ exactly $1-1/p$ of the time, but your polynomial is not divisible either all the time if $-1$ is not a square modulo $p$ (i.e. $p \equiv -1 \mod 4$) or $1-2/p$ of the time if $-1$ is a square modulo $p$ (i.e. $p \equiv 1 \mod 4$). So you would conjecture the number of primes for the first $x$ values would be approximately

$$\frac{x}{2 \log(x)} \cdot 2 \cdot \prod_{p \equiv 3 \mod 4} \frac{1}{1 - \frac{1}{p}} \prod_{p \equiv 1 \mod 4} \frac{1 - \frac{2}{p}}{1 - \frac{1}{p}} $$

$$= \frac{x}{\log(x)} \prod_{p > 2} \left(1 - \frac{\chi(p)}{p-1}\right),$$ where $\chi$ is the conductor $4$ character. The product converges, although this is not immediately obvious. One can estimate this to be

$$\sim \frac{x}{\log(x)} \cdot 1.372.$$

So I guess the answer (conjecturally) is "slightly, but asymptotically not as good as $2x+1$"

The basic reason you see lots of primes is because your polynomial is never divisible by $2$ or $3$, and most small numbers with this property are prime. (For example, of numbers less than $100$ prime to $6$, close to 70% are prime.)