6
$\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$
1
  • 1
    $\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, 2018 at 15:04

4 Answers 4

13
$\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$
4
  • $\begingroup$ You are using the $(n+1)!+2$ result right? $\endgroup$
    – prog_SAHIL
    Aug 6, 2018 at 15:04
  • $\begingroup$ right because $2|(n+1)!,3|(n+1)!$,etc $\endgroup$
    – Akababa
    Aug 6, 2018 at 15:05
  • $\begingroup$ Is it possible to get the $i$, for which we have exactly $12$ primes in this range? $\endgroup$ Aug 6, 2018 at 17:32
  • $\begingroup$ Probably not by hand, but you could with a computer. $\endgroup$
    – Akababa
    Aug 6, 2018 at 17:40
8
$\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$
11
  • $\begingroup$ This really helped. Thank you. $\endgroup$
    – prog_SAHIL
    Aug 6, 2018 at 15:16
  • $\begingroup$ Also for $n\geq{2}$, can we always say that $n!+1$ is prime? $\endgroup$
    – prog_SAHIL
    Aug 6, 2018 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, 2018 at 15:20
  • $\begingroup$ No. $4!+1=25$ for example $\endgroup$ Aug 6, 2018 at 15:21
  • 1
    $\begingroup$ @alu: and in some intervals there is one more. You have a sequence of numbers that starts above $12$ and steps by $0, \pm 1$ to get to $0$. It can't jump over $12$, so it must hit it at least once. $\endgroup$ Dec 21, 2022 at 5:33
2
$\begingroup$

I did the first question a different way:

  • look at any 100 consecutive numbers, they will end in the digits 01,02,...,00
  • we need to find a number n such that its ending digits per above are nonprimes and accordingly we can add this to a “base” number to get our solution. I’m not explaining very well but follow through the below
  • All numbers in this sequence ending with 2, 4, 6, 8, 0 are even and hence nonprimes
  • Similarly all numbers ending in 5 is nonprimes as long our starting number n is > 5
  • To cover off on numbers with last two digits summing up to a factor of 3, we need to ensure the starting number n is divisible by 3 and ends with a zero. If it does not, simply multiply by 30 to get this.
  • To cover off on Numbers ending with 1 just make sure the starting number ends with 0 and is a multiple of 11, 31, 41, 61, 71, 91, 101; where I have excluded 21, 51, 81 as they are divisible by 3. 91 is not a prime so we can remove it from this list

    • Do similar for 7 - numbers to multiply are 7, 17, 37, 47, 67, 97, 107
    • We also have cover off on 19, 29, 59, 79, 89, 13, 23, 43, 53, 73, 83

    • Thus the following number solves the question: 30 * 7 * 17 * 37 * 47 * 67 * 97 * 107 * 11 * 31 * 41 * 61 * 71 * 101 * 19 * 29 * 59 * 79 * 89 * 13 * 23 * 43 * 53 * 73 * 83

What was important for me here was that we were looking at a decimal representation of primes, since we wanted to find 100 sequential numbers. Hence, I decomposed the problem into solving for various decimal representations of natural numbers that are not prime

Hope it helps!

$\endgroup$
1
$\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$
2
  • 1
    $\begingroup$ Can you explain how $k=n\#$ helping ? $\endgroup$ Aug 6, 2018 at 17:47
  • 1
    $\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$ Aug 6, 2018 at 18:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .