9
$\begingroup$

Is it true that in any successive (natural) $2p_n$ numbers there are at least three numbers that are not divisible by any prime less (not equal) than $p_n$? Here, $p_n$ denotes the $n$-th prime number.

For example in any six successive numbers there are at least 3 numbers that are not divisible by 2,in any 10 successive numbers there are 3 numbers that are not divisible by 2 or 3, in any 14 successive numbers there are at least 3 that are not divisible by 2, 3, or 5.

$\endgroup$
5
  • 1
    $\begingroup$ this is not homework. this is a question that i found by myself and i think that it is interesting because i ha not found it in any text or book.if you have already see this please let me know $\endgroup$ Dec 14, 2010 at 16:41
  • $\begingroup$ A (locally) maximal interval of numbers each divisible by a prime less than $p_n$ will start and end at an even integer, so you might as well try for $2p_n+1$. $\endgroup$ Dec 15, 2010 at 1:57
  • $\begingroup$ @asterios: no justification for an interesting question needed! Upvotes are justification enough!! $\endgroup$
    – Dr Shello
    Dec 15, 2010 at 8:42
  • $\begingroup$ You don't really need the $n$ in the statement of your question. You can just ask if for all primes $p$ and all strings of $2p$ consecutive positive integers at least 3 of the integers have smallest prime factor greater than or equal to $p$. $\endgroup$
    – S. Carnahan
    Dec 15, 2010 at 8:56
  • $\begingroup$ thats true but with not equal $\endgroup$ Dec 15, 2010 at 9:14

3 Answers 3

12
$\begingroup$

Late update A better question might be; "What is the Largest number of consecutive integers such that each is divisible by a prime $\le p_n$ ? Computing a few values and checking the handy OEIS yields the link above. Matching the values with the appropriate primes shows that one can get over twice (at p=67) or even thrice the next prime with no gaps.

[2, 1], [3, 3], [5, 5], [7, 9], [11, 13], [13, 21], [17, 25], [19, 33], [23, 39], [29, 45], [31, 57], [37, 65], [41, 73], [43, 89], [47, 99], [53, 105], [59, 117], [61, 131], [67, 151], [71, 173], [73, 189], [79, 199], [83, 215], [89, 233], [97, 257], [101, 263], [103, 281], [107, 299], [109, 311], [113, 329], [127, 353], [131, 377], [137, 387], [139, 413], [149, 431], [151, 449], [157, 475], [163, 491], [167, 509], [173, 537], [179, 549], [181, 573], [191, 599], [193, 615], [197, 641], [199, 657], [211, 685], [223, 717], [227, 741]

older answer The first counter-example is for $p=17$. The interval of length $40$ starting at $87890$ only yields three integers with least prime factor greater than $17$: the primes $87911,87917$ and also $87929=23\cdot 3823$. So we can use the inteval of length $38$ starting at $87890$ or at $87891$.

I may be mistaken, but I think that there are not any examples for $p=19$ and $p=23$.

On the other hand, of the 89 consecutive integers from $43559563512434$ to $43559563512522$ inclusive, all but one have a prime factor $41$ or less. The exception is $43559563512481=9393910613\cdot 4637$

There are essentially 6 ways to get a run of length $39$ (or 3 up to reflection): One can start at $87890,177980,182342,328130,332492$ or $422582 \mod 510510$.

Discussion (Since somebody asked) For a prime $p$ call an integer $p$-good if it has a prime factor $p$ or less and $p$-bad otherwise. Let $M(p,b)$ be the longest possible run of consecutive integers which are all $p$-good except for $b$ exceptions (called holes). Note that $M(p,b)$ is odd. To find the values of $M(p,b)$ and all intervals attaining it, it suffices to look for runs in the integers from $0$ to $p\sharp-1$ where $p\sharp$ is the product of the primes up to $p$. That is true if we look cyclically or go a reasonable distance past $p\sharp$. I wondered at the particular question asked by the OP (" Is it the case that $M(p_{n-1},2)<2p_n$ for all $n$?" But now I realize that must be inspired by the fact that the $M(p_{n-1},2)\ge 2p_n-1$ is witnessed by the run from $p_{n-1}\sharp-p_n+1$ to $p_{n-1}\sharp+p_n-1$ (with the two bad numbers being $p_{n-1}\sharp \pm 1$).

For my computations I generated a list of the $p-bad$ numbers up to $p\sharp$. This can be done iteratively. I did this up to $p=23$ using a fairly uninspired Maple program on a unimpressive computer. $p=19$ took 9 seconds and $p=23$ took 250. The lists are centrally symmetric but I did not exploit that. A faster language, better program, faster machine, and storage in a file might allow one to go somewhat further. I then made the list of jumps from one $p$-bad number to the next. The jumps for $p=17$ with their multiplicities were

$[[2, 22274], [4, 22275], [6, 26630], [8, 6812], [10, 7734], [12, 4096]$

$[14, 1406], [16, 432], [18, 376], [20, 24], [22, 78], [24, 20], [26, 2]]$.

I then had Maple look for 3 successive gaps adding to at least $40$. There were 3 up to the middle.

I did not care to try $p=29$ by the same method! I looked for $M(23,3)$ using the same list of gaps in hopes of finding something good enough that I could get a good bound for $M(29,2)$ use the Chinese remainder theorem to shift everything preserving the 23-good members and plug a hole by making a 23-bad member 29-good. I didn't find anything by eyeballing. Similarly for $M(23,4)$ using $p=29,31$ and $M(23,5)$ using $p=29,31,37$. I did not think to look if there was something attaining $M(23,5)$ so that two of the holes were separated by 58 so that they could be plugged using up just one prime. But something with 2 of 6 holes separated by 62 did get noticed.

Note: I might have overlooked things. I did not really look at the two largish gaps around $p\sharp$. Also, The two holes with one prime trick might make a good example out of a run which is 2 or 4 less than $M(23,b)$.

$\endgroup$
15
  • 1
    $\begingroup$ 87911 is also prime. Gerhard "Ask Me About System Design" Paseman, 2010.12.14 $\endgroup$ Dec 15, 2010 at 6:34
  • $\begingroup$ True enough. Actually 87931 is outside the range I mentioned so the claim is correct, just not the transcription. Thanks! $\endgroup$ Dec 15, 2010 at 7:12
  • $\begingroup$ if you have a counterexample for 17 you must give me a length of 38 numbers that you have only 2 "holes" according to the question so how is 87890 a counter example ? $\endgroup$ Dec 15, 2010 at 7:47
  • 2
    $\begingroup$ 87890 to 878928 inclusive is 39 numbers. The two holes are 87911 and 87917. Here are the smallest divisors of each number: $$[2, 3, 2, 13, 2, 5, 2, 3, 2, 7, 2, 11, 2, 3, 2, 5, 2, 17, 2, 3, 2, 87911, 2, 7, 2, 3, 2, 87917, 2, 13, 2, 3, 2, 11, 2, 5, 2, 3, 2]$$ $\endgroup$ Dec 15, 2010 at 8:56
  • $\begingroup$ Aaron: How is this not a counterexample for $p=19$? $\endgroup$
    – S. Carnahan
    Dec 15, 2010 at 8:59
4
$\begingroup$

I believe the answer is no. In 1931 Erik Westzynthius showed that there are arbitrarily large gaps in the sequence S(n) of numbers which are relatively prime to the the first n primes. He not only showed that there were gaps of size 2*(p_{n-1}), which would give rise to your conjecture, he also showed that for large n ( greater than something like e^(e^e) ) that the gaps got larger than p_n*f(n) where f(n) is an increasing function involving log(n) and log(log(log(n))), which says that there are long runs of numbers each of which has one of the primes below and including p_n as a factor, and thus gives a negative answer to your question.

It is not known for what n this first occurs (a sequence of length 2*p_n consecutive numbers all of which have a factor among the first n primes). I am working on an upper bound for f(n) currently. For more information, see the related question Erik Westzynthius's cool upper bound argument: update? . I hope to post some information there soon.

Gerhard "Ask Me About System Design" Paseman, 2010.12.14

$\endgroup$
14
  • $\begingroup$ i want to know about when a sequence of length 2*p_n consecutive numbers all of which have a factor among the first n-1 primes $\endgroup$ Dec 14, 2010 at 18:12
  • $\begingroup$ I do too. If you have computing power (and a lot of memory) available to you, here are two programs you can build and run: the first computes S(n) or the largest gap in S(n), which is easy for small n; the second starts with the largest untried n from the first program and searches through the table of smallest factors of natural numbers for long runs of small factors. A good place to look for such runs are intervals centered on (P_n)/2, with P_n being the nth primorial. Gerhard "Ask Me About System Design" Paseman, 2010.12.14 $\endgroup$ Dec 14, 2010 at 18:25
  • $\begingroup$ do you have any other information about this kind of questions or Westzynthius proof? $\endgroup$ Dec 14, 2010 at 18:44
  • $\begingroup$ Yes. In addition to my own research (still under development but you can be added to the list of reviewers), there is research on prime gaps by Erdos, Rankin, and others. Hans Riesel has a book "Prime numbers and computer methods for factorization" which has a readable account of this as well as admissible constellations, which is related to your question. Marek Wolf and others have also done related work. A search for "prime gaps" will get you started. Gerhard "Ask Me About System Design" Paseman, 2010.12.14 $\endgroup$ Dec 14, 2010 at 18:54
  • $\begingroup$ i would like to read carefully your research $\endgroup$ Dec 14, 2010 at 19:07
2
$\begingroup$

EDIT: The following is false. The problem is that we only get an asymptotic for the number of such integers in the interval $[0,N]$, and to examine an interval of size $2p_n$ we need to examine the difference between this and $[0,N+2p_n]$. I was using the lower bound for this latter quantity as an upper bound, hence the erroneous result below. In reality, the answer could well be zero infinitely often, as Gerhard Paseman indicates.

For sufficiently large intervals, this is true; it follows from Buchstab's theorem (see Montgomery and Vaughan chapter 7.2) that, for sufficiently large $N$, there are approximately

$$ e^{-\gamma}\frac{2p_n}{\log p_n} $$

numbers in the interval $[N,N+2p_n]$ with all prime divisors at least $p_n$. For all primes at least 7, this is larger than 3. The cases 2,3 and 5 can be checked directly, as you mention in your question.

I imagine that if you were interested, it should be fairly easy to work out a specific (albeit large) lower bound for something like the above to hold, and then run a computer search on all smaller intervals.

Of course, there may well be a simple elementary way anyway, which I can't see right now.

$\endgroup$
7
  • $\begingroup$ I interpret the question as "all such intervals", not "exist infinitely many such intervals". Perhaps the original poster will clarify. Gerhard "Ask Me About System Design" Paseman, 2010.12.14 $\endgroup$ Dec 14, 2010 at 17:27
  • $\begingroup$ This seems to show the result for all sufficiently large intervals; this still contradicts your answer, however. I'll think about it overnight. $\endgroup$ Dec 14, 2010 at 17:39
  • $\begingroup$ Also, I am finding online theorem 7.11 credited to Buchstab, and I am not seeing how you derive your statement from that. Are you using equation 7.42 which has phi(x,y) defined as the number of numbers at most x which have only prime factors > y ? Gerhard "Ask Me About System Design" Paseman, 2010.12.14 $\endgroup$ Dec 14, 2010 at 17:45
  • $\begingroup$ Yes; or rather, the asymptotic formula that is a corollary of Theorem 7.11 (and letting $y=p_n$) -- clearly, for sufficiently large x, we can guarantee that $\Phi(x,y)\geq 0.1\frac{2x}{\log p_n}$ (say), and just take $N$, $N'$ greater than x with a difference of $2p_n$. $\endgroup$ Dec 14, 2010 at 20:33
  • $\begingroup$ Sorry, that should be $x$ rather than $2x$. $\endgroup$ Dec 14, 2010 at 20:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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