If we consider intervals of the form $[1,p_k !! ]$ in which $p_k!! := 2\cdot3\cdots p_k$ we can ask about distribution of primes, near-primes, etc., on such intervals. A naive approach might be to note first that any interval of length $2n$ contains $n$ even and $n$ odd numbers. We label the evens [[2]] and the odds [[2']].

For the interval $[1,3!!] = [1, 6] $, labeling numbers divisible by 3 as [[3]] and those not as [[3']], we have that 1/6 are even and divisible by 3, 2/6 are even but not divisible by 3, 1/6 are odd and divisible by 3, 2/6 are odd and not divisible by 3. More economically:

$$D_3 = \frac{1}{3}\frac{1}{2} [[2,3]]+\frac{2}{3}\frac{1}{2}[[2,3']]+\frac{1}{3}\frac{1}{2}[[2',3]] + \frac{2}{3}\frac{1}{2}[[2',3']]$$


$$D_3 = \frac{1}{6} [[2,3]]+\frac{2}{6}[[2,3']]+\frac{1}{6}[[2',3]] + \frac{2}{6}[[2',3']] $$

If we group according to the number of primes by which a number is divided, we get

$$D_3 = \frac{1}{6}(2) + \frac{3}{6}(1) + \frac{2}{6}(0)$$

In words, there is one number on [1,6] divisible by both 2 and 3, there are three numbers divisible by either 2 or 3, and there are two numbers divisible by neither 2 nor 3 (i.e, 1,5).

Going through the same process with 5 and 7:

$$D_5 = \frac{1}{30}[[2,3,5]] + \frac{4}{30}[[2,3,5']] + \frac{2}{30}[[2,3'5]]+ \frac{8}{30}[[2,3',5']] + \frac{1}{30}[[2',3,5]] + \frac{4}{30}[[2',3,5']] + \frac{2}{30}[[2',3',5]]+ \frac{8}{30}[[2'3',5']]$$

and grouping,

$$D_5 = \frac{1}{30}(3) + \frac{7}{30}(2) + \frac{14}{30}(1) + \frac{8}{30}(0).$$

Barring typos, etc.,

$$D_7 = \frac{1}{210}(4 ) +\frac{13}{210}(3) + \frac{56}{210}(2) + \frac{92}{210}(1) + \frac{48}{210}(0) $$

There are problems built into this approximation of divisibility. A number divisible only by $2$ may have repetitions of that factor--$4$, for example. On $[1,30]$, $22$ has two factors, one of which is not in the set $\{2,3,5\}$. Likewise, on $[1,210]$, $121 = 11^2$, but with respect to $\{2,3,5,7\}$, $121$ is a "prime." So the process doesn't exactly sort according to the number of divisors with repetition.

In particular, the class of numbers in $D_{p_k} $ on $ [1, p_k!!] $ mutually prime to $\{ 2,3,\ldots,p_k\}$ is I think identical to

$ P_k = \prod_{n = 1}^k(1 - \frac{1}{p_k} )$ , a gross overestimate of the proportion of primes on these intervals.

So much for motivation. Acknowledging the question is of limited interest, can anyone suggest a closed form for the sequence (omitting denominators):

1, 1

1, 3, 2

1, 7, 14, 8

1, 13, 56, 92, 48




The $n$th line of your sequence is the sequence of cofficients of the polynomial $$f_n(x) = \prod_{j=1}^n \big( x + p_j-1 \big).$$ For example, $$ f_4(x) = (x+1)(x+2)(x+4)(x+6) = x^4+13 x^3+56 x^2+92 x+48. $$ Because the primes are irregularly distributed, I doubt there is a closed form that's any nicer.

  • $\begingroup$ This is a very nice expression. Had you seen this before? I haven't come across it in elementary number thy texts. Thanks. $\endgroup$ – daniel Mar 8 '12 at 0:38
  • $\begingroup$ I hadn't seen it before, but it basically falls out of your recursive construction of the coefficients. $\endgroup$ – Greg Martin Mar 8 '12 at 18:56
  • $\begingroup$ It would have fallen a lot slower for me! $\endgroup$ – daniel Mar 8 '12 at 21:32
  • $\begingroup$ Happy to help! I'm guessing the part you might have taken a while to see is to consider the numbers as coefficients of a polynomial to begin with (once you decide to do so, finding the formula isn't that bad). This is a (finite) example of a generating function approach, which is well worth getting acquainted with as there are lots of situations where it helps a lot. $\endgroup$ – Greg Martin Mar 9 '12 at 19:51
  • $\begingroup$ Thanks also for the suggestion. Will do. $\endgroup$ – daniel Mar 9 '12 at 21:03

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.