2
$\begingroup$

I have already seen a duplicate of this. But I was not able to follow along.

So I was asked this question by my maths teacher during a sequence and series lecture.

  1. Can you devise $100$ consecutive natural numbers with no primes.

  2. Additionally, Is it possible to have $1000$ consecutive natural numbers with exactly $12$ primes between them?

I have an intuition that we have to form a recurrsive relation and solve it. But I am stuck.

I also tried making a $10*10$, having $50$ multiplies of $2$, $33$ multiples of $3$ and so on trying to generalize but wasn't able to come up with a solution.

Any hints would be really helpful. Thank you.

$\endgroup$
  • $\begingroup$ For the first question you can take a number $n>0$ such that it has a comon divisor with all numbers numbers less than 100. Then $n+i$ is not prime for $i=0,1,...,99$, isn't it? $\endgroup$ – xarles Aug 6 '18 at 15:04
8
$\begingroup$
  1. $101!+2,101!+3,...,101!+101$ has no primes (because $i|101!+i$ for $2\leq i\leq 101$)
  2. Let $f(n)$ be the number of primes in $\{n,...,n+999\}$. Since $f(1)>12$ and $f(1001!+2)=0$ (for the same reason as above) and $|f(i+1)-f(i)|\leq1$, there exists $i\in (1,1001!+2)$ with $f(i)=12$.
$\endgroup$
  • $\begingroup$ You are using the $(n+1)!+2$ result right? $\endgroup$ – prog_SAHIL Aug 6 '18 at 15:04
  • $\begingroup$ right because $2|(n+1)!,3|(n+1)!$,etc $\endgroup$ – Akababa Aug 6 '18 at 15:05
  • $\begingroup$ Is it possible to get the $i$, for which we have exactly $12$ primes in this range? $\endgroup$ – tarit goswami Aug 6 '18 at 17:32
  • $\begingroup$ Probably not by hand, but you could with a computer. $\endgroup$ – Akababa Aug 6 '18 at 17:40
5
$\begingroup$

For the second, note that we were not asked to display such an interval, just to prove one exists. You can use the technique of the first to show there is a run of $1000$ numbers with no primes. Now note that there are more than $12$ primes in $[2,1001]$. Imagine stepping through the intervals $[2,1001], [3,1002], [4,1003],\ldots$ until we get to the interval with no primes. Each interval has either one more, the same number, or one less prime than the one that came before. As we started above $12$ and get to $0$ somewhere there is at least one that has exactly $12$. I have no idea where it is.

$\endgroup$
  • $\begingroup$ This really helped. Thank you. $\endgroup$ – prog_SAHIL Aug 6 '18 at 15:16
  • $\begingroup$ Also for $n\geq{2}$, can we always say that $n!+1$ is prime? $\endgroup$ – prog_SAHIL Aug 6 '18 at 15:18
  • $\begingroup$ A counter example will be $5!+1$? How do we know if $101!+1$ is prime or not? Just out of curiosity. Having $101$ consecutive numbers won't hurt right? $\endgroup$ – prog_SAHIL Aug 6 '18 at 15:20
  • $\begingroup$ No. $4!+1=25$ for example $\endgroup$ – Ross Millikan Aug 6 '18 at 15:21
  • $\begingroup$ Numbers $n$ such that $n!+1$ is prime are fairly rare. The first few are listed in oeis.org/A002981 $\endgroup$ – Ross Millikan Aug 6 '18 at 15:37
0
$\begingroup$

The $(n+1)!$ proof is very easy to understand, but it can create the impression that gaps of $100$ primeless numbers are almost impossibly rare. For example, $101!$ is on the order of $10^{160}$. In actuality, gaps of $100$ primeless numbers occur at much smaller magnitudes.

The same logic of the $(n+1)!$ proof can be applied to the lcm (least common multiple) function, which defines the smallest number divisible by a given set of numbers. For $k=$lcm $(2,3,..101)$, it is plain to see that $i\mid (k+i), 2\le i\le 101$ since by the definition of lcm, $i\mid k$. The lcm function returns a number much smaller than the corresponding factorial. If my back of the envelope estimate is correct, lcm $(2,3,..101)$ is on the order of $7\cdot 10^{42}$. Not small, but over $117$ orders of magnitude smaller than the factorial.

A slightly smaller number can be obtained by employing primorials. For $k=n\#$ it can be seen that $\gcd {i,(k+i)}>1, 2\le i\le n$ since every $i$ will have some factor in common with both $n\#$ and itself.

In the real world, primeless gaps of length $n$ tend to occur at yet lower magnitudes than these methods identify.

$\endgroup$
  • $\begingroup$ Can you explain how $k=n\#$ helping ? $\endgroup$ – tarit goswami Aug 6 '18 at 17:47
  • $\begingroup$ $n\#$ is the primorial function; it equals the product of all primes less than or equal to $n$. Every number between $2$ and $n$ is either (1) a prime less than or equal to $n$ or (2) has two or more prime factors less than $n$. In the first case, it is explicitly a factor of $n\#$. In the second case, it is not relatively prime to one or more of the factors of $n\#$. $\endgroup$ – Keith Backman Aug 6 '18 at 18:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.