# Closed form for a sequence related to divisibility

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']]$$

or

$$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

...etc.?

Thanks.

-
You can use $\# p$ for the primorial. – Pedro Tamaroff Mar 8 '12 at 0:45

## 1 Answer

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.

-
This is a very nice expression. Had you seen this before? I haven't come across it in elementary number thy texts. Thanks. – daniel Mar 8 '12 at 0:38
I hadn't seen it before, but it basically falls out of your recursive construction of the coefficients. – Greg Martin Mar 8 '12 at 18:56
It would have fallen a lot slower for me! – daniel Mar 8 '12 at 21:32
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. – Greg Martin Mar 9 '12 at 19:51
Thanks also for the suggestion. Will do. – daniel Mar 9 '12 at 21:03