5

Is there at least one prime between the number $n \times 100$ and $(n \times 100) + 100$ for any $n \in \mathbb{N}$ that can be $0$ ?

Question originally formulated by one of my friends.

  • http://math.stackexchange.com/questions/376942/intervals-that-are-free-of-primes/377133#377133 – gukoff Sep 13 '13 at 13:49

5 Answers5

32

Not necessarily. For example none of the numbers between $200!+100$ and $200!+200$ can be prime, because $200!+k$ is divisible by $k$ when $2\le k\le 200$.

So a concrete counterexample would be $n=\frac{200!}{100}+1$.

For a smaller counterexample one could let $100n$ be the product of all primes up to 109, times 3, plus 10. That gives an $n$ with "only" $43$ digits.

Heuristically, based on the prime number theorem, one would expect counterexamples to start showing up as early as for $n$ in the mid-thousands. The "probability" that a random $n$ works is roughly $(1-\frac{1}{\ln(100n)})^{100}$, and at $n=4000$ this is more than $1/4000$.

An exhaustive search, however, shows that the smallest counterexample is n=16,718. That's not too far from the above heuristic estimate, considering how crude it is.

hmakholm left over Monica
  • 286,031
9

No.

Consider $n=99!$. $100n = 100!$ is composite, and $100!+1$ is divisible by $101$ (Wilson's theorem) and so is composite. $100n+i$ is divisible by $i$ for $2\leq i \leq 100$.

user7530
  • 49,280
  • See also Henning's answer for a larger, but more elementary counterexample that does not require Wilson's theorem. – user7530 Sep 12 '13 at 21:21
  • So this depends on the lucky shot that $101$ is prime. So if you want interval sizes that always contain a prime, look for (at minimum) something which isn't one less than a prime. – Jack M Sep 12 '13 at 22:14
2
     4652400 = 2^4 * 3 * 5^2 * 3877
     4652401 = 13^2 * 27529
     4652402 = 2 * 401 * 5801
     4652403 = 3 * 7^2 * 31649
     4652404 = 2^2 * 619 * 1879
     4652405 = 5 * 930481
     4652406 = 2 * 3^2 * 11 * 23497
     4652407 = 17 * 103 * 2657
     4652408 = 2^3 * 581551
     4652409 = 3 * 61 * 25423
     4652410 = 2 * 5 * 7 * 66463
     4652411 = 97 * 47963
     4652412 = 2^2 * 3 * 29^2 * 461
     4652413 = 67 * 69439
     4652414 = 2 * 13 * 178939
     4652415 = 3^2 * 5 * 103387
     4652416 = 2^7 * 19 * 1913
     4652417 = 7 * 11 * 23 * 37 * 71
     4652418 = 2 * 3 * 31 * 25013
     4652419 = 823 * 5653
     4652420 = 2^2 * 5 * 232621
     4652421 = 3 * 199 * 7793
     4652422 = 2 * 2326211
     4652423 = 1567 * 2969
     4652424 = 2^3 * 3^3 * 7 * 17 * 181
     4652425 = 5^2 * 186097
     4652426 = 2 * 2326213
     4652427 = 3 * 13 * 119293
     4652428 = 2^2 * 11 * 43 * 2459
     4652429 = 373 * 12473
     4652430 = 2 * 3 * 5 * 155081
     4652431 = 7 * 664633
     4652432 = 2^4 * 313 * 929
     4652433 = 3^2 * 599 * 863
     4652434 = 2 * 41 * 56737
     4652435 = 5 * 19 * 48973
     4652436 = 2^2 * 3 * 47 * 73 * 113
     4652437 = 1583 * 2939
     4652438 = 2 * 7 * 332317
     4652439 = 3 * 11 * 140983
     4652440 = 2^3 * 5 * 13 * 23 * 389
     4652441 = 17 * 29 * 9437
     4652442 = 2 * 3^2 * 258469
     4652443 = 397 * 11719
     4652444 = 2^2 * 1163111
     4652445 = 3 * 5 * 7 * 59 * 751
     4652446 = 2 * 53 * 43891
     4652447 = 109 * 42683
     4652448 = 2^5 * 3 * 48463
     4652449 = 31 * 223 * 673
     4652450 = 2 * 5^2 * 11^2 * 769
     4652451 = 3^3 * 172313
     4652452 = 2^2 * 7^3 * 3391
     4652453 = 13 * 167 * 2143
     4652454 = 2 * 3 * 19 * 37 * 1103
     4652455 = 5 * 930491
     4652456 = 2^3 * 581557
     4652457 = 3 * 1550819
     4652458 = 2 * 17 * 193 * 709
     4652459 = 7 * 367 * 1811
     4652460 = 2^2 * 3^2 * 5 * 25847
     4652461 = 11 * 151 * 2801
     4652462 = 2 * 1327 * 1753
     4652463 = 3 * 23 * 67427
     4652464 = 2^4 * 101 * 2879
     4652465 = 5 * 131 * 7103
     4652466 = 2 * 3 * 7 * 13 * 8521
     4652467 = 107 * 43481
     4652468 = 2^2 * 79 * 14723
     4652469 = 3^2 * 139 * 3719
     4652470 = 2 * 5 * 29 * 61 * 263
     4652471 = 43 * 257 * 421
     4652472 = 2^3 * 3 * 11 * 17623
     4652473 = 7 * 19 * 34981
     4652474 = 2 * 977 * 2381
     4652475 = 3 * 5^2 * 17 * 41 * 89
     4652476 = 2^2 * 1163119
     4652477 = 911 * 5107
     4652478 = 2 * 3^6 * 3191
     4652479 = 13 * 357883
     4652480 = 2^6 * 5 * 7 * 31 * 67
     4652481 = 3 * 1550827
     4652482 = 2 * 83 * 28027
     4652483 = 11 * 47 * 8999
     4652484 = 2^2 * 3 * 387707
     4652485 = 5 * 877 * 1061
     4652486 = 2 * 23 * 101141
     4652487 = 3^2 * 7 * 73849
     4652488 = 2^3 * 71 * 8191
     4652489 = 173 * 26893
     4652490 = 2 * 3 * 5 * 155083
     4652491 = 37 * 125743
     4652492 = 2^2 * 13 * 17 * 19 * 277
     4652493 = 3 * 1550831
     4652494 = 2 * 7 * 11 * 30211
     4652495 = 5 * 930499
     4652496 = 2^4 * 3^2 * 32309
     4652497 = 2029 * 2293
     4652498 = 2 * 2326249
     4652499 = 3 * 29 * 53 * 1009
     4652500 = 2^2 * 5^4 * 1861
jagy@phobeusjunior:~$
Will Jagy
  • 139,541
  • Awesome as usual. – Pedro Sep 13 '13 at 03:02
  • You use Linux! Awesome! –  Sep 13 '13 at 15:44
  • 1
    @Adobe, yes, C++ with STL, and, for Pell equations, GMP, as some kinds of numbers stay small (the "digits" or "quotients") but the values of $x,y$ in $x^2 - n y^2 = m$ can become huge. Meanwhile, see the table with the first 75 maximal prime gaps in http://en.wikipedia.org/wiki/Prime_gap#Numerical_results which is how I knew 4652400 would work, after which I did an exhaustive search and repeated Henning's find of the first failure. In any case, read about prime gaps. – Will Jagy Sep 13 '13 at 19:00
  • Thank you so much @WillJagy –  Sep 13 '13 at 19:41
  • b.t.w: I have a question, is there a generalization of this? for let's say n1000 and n1000+1000, n10.000 and n10.000 + 10.000 ... and so on? –  Sep 13 '13 at 19:42
  • 1
    @Adobe, a relatively early counterexample for your 1000 problem begins with 80873624627235000 and has all composite numbers up to 80873624627236000. There will always be counterexamples for these, finding the earliest counterexample for one of them becomes arduous. Compare this information from the Prime Gaps table, gap = 1220, beginning prime = 80873624627234849. That is, the next prime is 80873624627236069. – Will Jagy Sep 13 '13 at 20:07
2

Earliest failure:

 1671800 = 2^3 * 5^2 * 13 * 643
 1671801 = 3 * 23 * 24229
 1671802 = 2 * 11 * 75991
 1671803 = 7 * 238829
 1671804 = 2^2 * 3^2 * 46439
 1671805 = 5 * 239 * 1399
 1671806 = 2 * 769 * 1087
 1671807 = 3 * 557269
 1671808 = 2^7 * 37 * 353
 1671809 = 599 * 2791
 1671810 = 2 * 3 * 5 * 7 * 19 * 419
 1671811 = 137 * 12203
 1671812 = 2^2 * 417953
 1671813 = 3^3 * 11 * 13 * 433
 1671814 = 2 * 17 * 49171
 1671815 = 5 * 334363
 1671816 = 2^3 * 3 * 41 * 1699
 1671817 = 7 * 241 * 991
 1671818 = 2 * 835909
 1671819 = 3 * 557273
 1671820 = 2^2 * 5 * 83591
 1671821 = 29 * 57649
 1671822 = 2 * 3^2 * 131 * 709
 1671823 = 191 * 8753
 1671824 = 2^4 * 7 * 11 * 23 * 59
 1671825 = 3 * 5^2 * 22291
 1671826 = 2 * 13 * 64301
 1671827 = 61 * 27407
 1671828 = 2^2 * 3 * 127 * 1097
 1671829 = 19 * 87991
 1671830 = 2 * 5 * 31 * 5393
 1671831 = 3^2 * 7^2 * 17 * 223
 1671832 = 2^3 * 53 * 3943
 1671833 = 1289 * 1297
 1671834 = 2 * 3 * 278639
 1671835 = 5 * 11 * 113 * 269
 1671836 = 2^2 * 417959
 1671837 = 3 * 47 * 71 * 167
 1671838 = 2 * 7 * 119417
 1671839 = 13 * 128603
 1671840 = 2^5 * 3^5 * 5 * 43
 1671841 = 1223 * 1367
 1671842 = 2 * 109 * 7669
 1671843 = 3 * 557281
 1671844 = 2^2 * 417961
 1671845 = 5 * 7 * 37 * 1291
 1671846 = 2 * 3 * 11 * 73 * 347
 1671847 = 23 * 72689
 1671848 = 2^3 * 17 * 19 * 647
 1671849 = 3^2 * 431^2
 1671850 = 2 * 5^2 * 29 * 1153
 1671851 = 67 * 24953
 1671852 = 2^2 * 3 * 7 * 13 * 1531
 1671853 = 101 * 16553
 1671854 = 2 * 835927
 1671855 = 3 * 5 * 227 * 491
 1671856 = 2^4 * 104491
 1671857 = 11^2 * 41 * 337
 1671858 = 2 * 3^2 * 293 * 317
 1671859 = 7 * 238837
 1671860 = 2^2 * 5 * 179 * 467
 1671861 = 3 * 31 * 17977
 1671862 = 2 * 835931
 1671863 = 359 * 4657
 1671864 = 2^3 * 3 * 69661
 1671865 = 5 * 13 * 17^2 * 89
 1671866 = 2 * 7 * 119419
 1671867 = 3^3 * 19 * 3259
 1671868 = 2^2 * 11 * 37997
 1671869 = 83 * 20143
 1671870 = 2 * 3 * 5 * 23 * 2423
 1671871 = 487 * 3433
 1671872 = 2^6 * 151 * 173
 1671873 = 3 * 7 * 79613
 1671874 = 2 * 835937
 1671875 = 5^6 * 107
 1671876 = 2^2 * 3^2 * 46441
 1671877 = 79 * 21163
 1671878 = 2 * 13 * 64303
 1671879 = 3 * 11 * 29 * 1747
 1671880 = 2^3 * 5 * 7^2 * 853
 1671881 = 331 * 5051
 1671882 = 2 * 3 * 17 * 37 * 443
 1671883 = 43 * 59 * 659
 1671884 = 2^2 * 47 * 8893
 1671885 = 3^2 * 5 * 53 * 701
 1671886 = 2 * 19 * 43997
 1671887 = 7 * 238841
 1671888 = 2^4 * 3 * 61 * 571
 1671889 = 521 * 3209
 1671890 = 2 * 5 * 11 * 15199
 1671891 = 3 * 13 * 163 * 263
 1671892 = 2^2 * 31 * 97 * 139
 1671893 = 23 * 157 * 463
 1671894 = 2 * 3^3 * 7 * 4423
 1671895 = 5 * 334379
 1671896 = 2^3 * 103 * 2029
 1671897 = 3 * 181 * 3079
 1671898 = 2 * 41 * 20389
 1671899 = 17 * 98347
 1671900 = 2^2 * 3 * 5^2 * 5573
Will Jagy
  • 139,541
1

As a generalization of some of the other answers, there are arbitrarily long sequences of composites: Namely, consider the numbers $N! + 2, N! + 3, N! + 4, ..., N!+N$ which has length $N - 1$.