Formulas for Sequences Removing Multiples of 2, 3, and 5

Question

First off, I am a programmer so please excuse if some of the terms I use are not the correct mathematical terms. I was working on devising a function to improve one of my prime number generation algorithms. With this in mind, I first set out to find the formulas for a sequence removing multiples of 2 and 3:

\begin{array}{c|c} x&y\\ \hline 0&5\\ \hline 1&7\\ \hline 2&11\\ \hline 3&13\\ \hline 4&17\\ \hline 5&19\\ \hline 6&23\\ \hline 7&25\\ \hline 8&29\\ \hline \vdots&\vdots \end{array}

The equations that I came up for for this sequence are as follows:

$$y = 3x + 5 - x \bmod 2$$ $$x = \left\lfloor\frac{y - 5 + [y \bmod 3 \neq 0]}{3}\right\rfloor$$

After this, I tried to do the same for a sequence removing multiples of 2, 3, and 5:

\begin{array}{c|c} x&y\\ \hline 0&7\\ \hline 1&11\\ \hline 2&13\\ \hline 3&17\\ \hline 4&19\\ \hline 5&23\\ \hline 6&29\\ \hline 7&31\\ \hline 8&37\\ \hline 9&41\\ \hline 10&43\\ \hline 11&47\\ \hline 12&49\\ \hline 13&53\\ \hline \vdots&\vdots \end{array}

While I think I found an equation to get $y$ from a value of $x$, I cannot find a way to get the value of $x$ from a given value $y$.

$$y = 4x + 7 - 2\left\lfloor\frac{1}{8}x\right\rfloor - 2\left[\{2, 3, 6\} \ \text{contains}\ (x \bmod 8)\right] - 4\left[\{4, 5, 7\} \ \text{contains}\ (x \bmod 8)\right]$$ $$x =\ ?$$

I am wondering if an equation that produces the corresponding value of $x$ for a given value of $y$ for the aforementioned sequence exists, and if indeed it does, what the equation is.

Answer 1

If this is for a programming task, you don't want a fancy formula. That will only slow you down. Instead, for the first table, just cycle through the values $6n+1,6n+5$ for $n=0,1,2,\ldots$ And for the second table, cycle through the values $30n+1,30n+7,30n+11,$ etc. (there are eight of them).

Updated to add:

Perhaps the following is more in the spirit of what the OP is looking for. This is for the case $2,3,5$. Declare a short array:

offset[8] = { 1,7,11,13,17,19,23,29 }

Then the nth number that is not divisible by $2, 3,$ or $5$ is simply

30 * (n / 8) + offset[n % 8]

where n/8 is understood to be rounded down to an integer.

Answer 2

This isn’t exactly what you’re looking for, but it’s definitely relevant, and too long for a comment. The formula $$\bigg\lfloor\frac{n}{2}\bigg\rfloor + \bigg\lfloor\frac{n}{3}\bigg\rfloor + \bigg\lfloor\frac{n}{5}\bigg\rfloor - \bigg\lfloor\frac{n}{6}\bigg\rfloor - \bigg\lfloor\frac{n}{10}\bigg\rfloor - \bigg\lfloor\frac{n}{15}\bigg\rfloor + \bigg\lfloor\frac{n}{30}\bigg\rfloor $$ is equal to the number of positive integers less than or equal to $n$ that aren’t divisible by $2,3,$ or $5$. Perhaps you can use this to find an answer to your question?

Answer 3

The first one is:

$$y=5+6\bigg\lfloor \frac{x}{2} \bigg\rfloor + 2(x\mod2)$$

Although arguably $x(0)=1$, so:

$$y=1+6\bigg\lfloor \frac{x+1}{2} \bigg\rfloor - 2(x\mod2)$$

The second, with $x(0)=1$, is:

$$y=15+30\bigg\lfloor \frac{x}{8} \bigg\rfloor +4(x\mod8-3.5)-\frac{(x\mod8-3.5)}{|x\mod8-3.5|}\cdot2(\bigg\lfloor\frac{(|x\mod8-3.5|+0.5)}{2}\bigg\rfloor\mod2)$$

Answer 4

my way is with an 8 value addition sequence 2, 6, 4, 2, 4, 2, 4, 6. and Repeat. Start @ -1

(-1) [+ 2] = 1 [+6] = 7 [+4] = 11

thus (-1) 1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 67, 71, 73, 77, 79, 83...

and so on

Repeating this addition sequence from start position of -1 [2, 6, 4, 2, 4, 2, 4, 6]{2, 6, 4, 2, 4, 2, 4, 6}[2, 6, 4, 2, 4, 2, 4, 6]

Generates a continuous sequence without any multiples of 2, 3 or 5