Problems & Puzzles: Puzzles

Puzzle 544.- Yet another  prime Prime Race

Anton Vrba sent the following puzzle.

Let P[y] be a polynomial: P[y] = a0 + a1 y^1 + a2 y^2 + a3 y^3 …

We define the set A={y1, y2, y3, y4,…,y_n} which are the solutions for P[y] prime. The set A contains primes and composites.

We are looking for a polynomial P[y] such that we find in the solution A, a subset B which is a sequence of primes, ie B={ ý1, ý2, , ý3 …. ý_l} all prime, and B is maximized in length.

A clear winner to this problem seems to be P[y] = 60 + y^2, with the solution of sixteen sequential primes B = {7, 11, 13, 17, 19, 31, … 83, 109, 113}, and P[y] is composite for any composite between 7 and 113.

To make the problem more interesting we reward the complexity. For this we consider the length as well as size of the primes involved. Thus defining the complexity of the solution as

C = l^2 ( Σ Ln[ý_i+z] Ln[P[ý_i+z], z=1,2, … l)

Example:

For P[y] = 60+ y^2 and B={7, 11, 13, 17, 19, 31, … 83, 109, 113} we calculate the complexity as: C =16^2 ( Ln[7]Ln[109] + Ln[11]Ln[181] +…. Ln[113]Ln[12829] ) = 114843

Q1. In the context of the problem description find or devise a polynomial P[y] with larger complexity than 114843.

Contribution came from Fred Schneider.

***

Fred wrote:

Here is the largest complexity value I found (for a quadratic*).  It's almost certainly not the largest answer.

I used the primorial of 659 as a seed.  The first prime is 1549.  The last is 574279.  There were 886 primes for a complexity of 6088233235.866535533728691593. It broke at composite 574339 (y is prime for that value).

Running for p=659 and checking v=x^2+195386392201750013541798544537654871502515432074538294594441904432557
192382935256006943963601843734004282823789366203170193705180334957353284201111418857925009006899963167
06288500007348091176674936338348141496596522546808024913768851397382384515827814854033667268002459152
4510

1549 2531 3511 3739 3797 3847 4327 4657 5227 5783 5923 6073 6151 7237 7549 8171 8501 10513 11083 11593 11969 13177 13187 13807 14593 14713 16057 16319 16529 16547 17471 17477 17881 18329 18553 19141 20261 20807 21247 23497 23873 24697 26693 26947 27947 28631 28927 29123 29167 29741 30011 31721 32719 32987 33601 33703 33937 35401 36217 37253 38047 38557 38861 39293 39419 39607 39623 40037 40961 41117 41189 41411 41479 42101 42859 44909 45013 45751 45833 45943 46051 46411 46691 47387 47903 48121 48563 49193 49261 49613 49853 50767 51683 52267 52757 52817 53279 54539 54577 54941 55049 55541 56267 57413 58451 58787 59723 60037 60637 61231 61381 62633 63347 63421 64489 64613 64621 64997 65323 65827 65929 69073 70487 71147 71909 73043 73421 73721 76207 76537 76771 77417 77543 78571 78941 79087 80039 80611 80963 81457 82567 85703 85733 87211 87931 89069 89459 89477 90073 91121 91493 92681 93103 93553 94109 94531 94907 95723 95791 96457 96497 97501 97927 98899 99241 99709 100343 100693 100769 101663 104059 104383 104527 107941 108089 110063 110629 110647 111119 111227 111301 112289 112459 112507 112859 113173 114769 115631 118409 118967 119671 119827 120041 120607 120889 120929 121169 122387 122849 123127 123923 124429 124673 124853 125311 125921 126037 126827 127297 127373 127507 128099 128971 130589 131111 131113 131449 131849 132833 134837 137447 137849 139199 139273 139303 139787 140863 141623 141803 142159 142873 143239 143249 144967 145069 145807 146239 146381 147347 148867 149341 152563 153107 155413 155593 155693 156109 157669 159167 160739 161563 162017 162553 162713 163181 163753 164089 166031 166237 166487 168449 169783 171889 172219 173267 174467 174893 175631 176557 177283 177421 177553 177743 177949 179953 180317 180907 181061 181157 183581 184211 185027 185243 185681 185767 185831 186119 187081 187091 187417 187843 187951 188369 188389 188437 190093 190121 190391 191251 191977 192833 192847 193043 193367 194861 194917 195023 195919 196739 198571 198641 198833 198967 199153 199751 200483 200731 201581 201683 202717 202973 203321 204427 204583 205157 205463 205879 206203 206413 206783 207797 208231 208891 209257 209327 209659 211097 211691 211817 212501 213193 213247 214507 215981 216211 216431 217421 220421 220447 220559 220973 221281 221461 222073 222367 222511 222601 222991 223151 223747 224209 224317 224579 226141 227693 228113 229081 229553 229939 230891 230939 230959 231293 231809 231877 234043 234343 234589 234803 234833 236449 237301 237977 238081 238151 238331 239831 240437 240491 240853 242257 243121 244121 244411 244781 245591 248401 248779 248861 251513 252163 252913 253567 253819 254147 254197 255107 255127 256301 257437 260003 260339 260441 261061 261167 262387 263827 266177 266921 266977 267199 267521 267899 268237 269023 269341 271849 272203 273311 273629 275251 275549 276847 277741 277859 277999 279431 280129 280699 280811 281357 282571 282917 283519 284111 285569 286789 288733 289889 290011 290443 292577 292711 293081 293093 293543 293803 293957 294001 294919 295259 296347 297629 298099 298777 299197 299281 299287 299653 300319 300623 301219 302903 304253 304643 305339 305563 305917 307019 307693 307873 307891 308333 308723 309011 309109 309713 310801 311033 313081 313931 313969 316153 318233 320693 321413 321553 321743 322669 323083 324131 324293 324299 326741 327419 327473 328109 328639 329419 329473 329947 330433 330587 331511 331547 331777 332729 332803 333097 333349 334429 334511 335579 336577 336823 337817 338687 339671 339841 340583 341347 341959 342077 342451 343313 343391 344807 345953 346649 347287 347707 347849 348001 348191 348433 349007 349603 349753 351797 354953 355027 355679 355697 355951 356977 357353 358223 358637 358877 360317 360589 361687 362431 363719 364337 366479 367949 368287 368609 368743 368873 369913 371233 371573 371927 372367 372971 373273 375119 375121 375359 376891 377369 377563 377711 377761 378583 378671 378941 379283 379777 380867 382961 385069 385141 386083 386921 388159 388991 389303 389663 390157 390359 391057 391301 391373 391613 392437 393241 393859 394249 395677 397099 398347 400187 400723 401627 402043 403649 403717 405677 406117 406883 407861 408533 408773 409099 409163 409879 411251 411709 411833 411967 412303 413827 414217 414347 414959 416947 417763 418087 418343 418961 419443 420149 420467 421279 421361 421973 422711 422753 422893 423389 423751 424027 424397 424537 424967 425377 426773 427379 427723 427993 428843 429467 429901 429937 431251 431803 432241 432869 433207 434831 436957 438707 438961 439511 439667 439781 439949 440179 440681 440809 441187 441697 441887 442193 442469 442763 443171 443293 444347 445031 445877 446123 446647 447449 447463 447859 447893 448367 448807 448993 452033 452087 452227 453289 454451 455491 455827 455863 456809 456821 457367 457739 458317 459467 460609 460771 460813 460871 461333 461407 463207 463513 468277 468841 470059 470279 471041 471847 471959 472837 473167 473507 473723 474787 474907 475763 475997 477461 477947 478273 479441 479797 480853 482021 482233 483323 484061 484229 485171 485819 486923 488149 488339 488959 489019 490183 490393 490643 492853 493777 493931 494083 494687 494987 495371 497117 497309 497587 497867 497977 498331 498973 502781 504139 504817 506119 506281 507049 507901 508297 510613 510907 511627 512251 512443 512929 513353 513371 514009 514081 514093 514103 515429 515579 515773 515887 516223 517091 517399 517417 518291 518467 518621 519227 519349 519647 520031 520589 522371 525739 526739 527381 527453 527929 528041 528631 529027 529181 530977 531983 532327 532531 532771 532811 533177 534403 534661 534671 535637 536273 536891 537041 537331 537343 538073 538511 538561 538777 538841 539849 540461 541531 541759 541771 541781 542093 545477 546149 547237 548323 550541 550859 550961 552047 552217 552341 552917 552983 554303 554531 554753 555697 556483 556999 557747 557987 558563 558827 562519 564149 565171 565393 567631 567841 570071 570613 571267 572281 572791 572801 573179 573763 574279

Reasoning: My polynomial function is y=x^2+s where s= s=primorial(p) as a seed.  Start checking with the next prime after p (gcm(pl,pl^2+s) is clearly > 1 when pl < p).  Where x is a composite less than p^2, y will always be composite (because it must have a factor <=p) so you don't need to check them.  It stands to reason that as p, increases y=x^2+primorial(p) will be less and less like to be prime.
I suspect that there is no upper bound on complexity.

Note: If you use y=x+s, a linear function, you can get much higher complexities.  I'm not sure if that's allowed based on the question.

***

 Records   |  Conjectures  |  Problems  |  Puzzles