What is the number of integers divisible by either 2, 3, or 5 from the integers 1 to $n+1$?

Question

I am interested in integer sequence A254828 (https://oeis.org/A254828), but from the link it seems to have a recursive formula $a(n) = a(n-1) + a(n-30) - a(n-31)$.

As joriki said, they are the number of positive integers up to $n+1$ divisible by 2, 3 or 5. We can check them by the following code:

//A254828
#include <stdio.h>

int countDivisibleBy235(int n) {
    int count = 0;
    for (int i = 1; i <= n + 1; i++) {
        if (i % 2 == 0 || i % 3 == 0 || i % 5 == 0) {
            count++;
        }
    }
    return count;
}

int main() {
    int start, end;
    printf("Enter the range (start end): ");
    scanf("%d %d", &start, &end);

    printf("Number of positive integers divisible by 2, 3, or 5:\n");
    for (int i = start; i <= end; i++) {
        int result = countDivisibleBy235(i);
        printf("n = %d: %d\n", i, result);
    }

    return 0;
}

A specific example is when n+1 equals 300. See What is the number of integers divisible by either 2, 3, or 5 from the integers 1 to 300?

However, is there a concise closed-form expression?

---

Maybe we can give it as

$\lfloor \frac{n+1}{2} \rfloor+ \lfloor \frac{n+1}{3} \rfloor+ \lfloor\frac{n+1}{5}\rfloor -\lfloor\frac{n+1}{6}\rfloor- \lfloor\frac{n+1}{10}\rfloor-\lfloor \frac{n+1}{15}\rfloor+ \lfloor\frac{n+1}{30} \rfloor$.

Answer 1

This sequence makes little sense by itself. It’s the first of a series of sequences up to A$254834$, where the $n$-th term of the sequence A$254827+k$ is the number of $k$-tuples of positive integers up to $n+1$ with every partial sum divisible by $2$, $3$ or $5$. For $k=1$, this is simply the number of positive integers up to $n+1$ divisible by $2$, $3$ or $5$. Since there are $\phi(30)=8$ residues modulo $30$ that are coprime to $30=2\cdot3\cdot5$, this is essentially $\frac{22}{30}n=\frac{11}{15}n$ with some local deviations. The recurrence relation just expresses that the period is $30$.

As for a “concise closed-form expression”, it would be nice to be able to express this as $a(n)=\left\lfloor\frac{11}{15}n+x\right\rfloor$, but that’s not possible due to the bunching of the coprime residues in pairs. Using the fact that the coprime residues are all at either $6k+1$ or $6k+5$ and only two of the residues of that form aren’t coprime ($5$ and $25$), the sequence can be expressed as

$$ a(n-1)=n-\left\lfloor\frac{5n+5}{30}\right\rfloor-\left\lfloor\frac{5n+25}{30}\right\rfloor+\left\lfloor\frac{n+5}{30}\right\rfloor+\left\lfloor\frac{n+25}{30}\right\rfloor $$

and thus

$$ a(n)=n-\left\lfloor\frac{5n+10}{30}\right\rfloor-\left\lfloor\frac{5n}{30}\right\rfloor+\left\lfloor\frac{n+6}{30}\right\rfloor+\left\lfloor\frac{n+26}{30}\right\rfloor\;. $$