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

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.

• see sieve of sundaram.
– user645636
Sep 14, 2019 at 18:38

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).

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.

• I need this equation for indexing a very large array numerous times and as such it would be wildly inefficient to just cycle through them. Sep 13, 2019 at 16:36
• en.m.wikipedia.org/wiki/Hadamard_product_(matrices) invert to mod by 30... select the ones that fall into the correct remainders.
– user645636
Sep 14, 2019 at 19:08
• @RoddyMacPhee: err...what? Sep 14, 2019 at 19:41
• keep subtracting a matrix filled with 30 until elements are under 30. then select the elements that have values 1,7,11,13,17,19,23, or 29 as those are the ones that could be prime.
– user645636
Sep 14, 2019 at 19:51
• @RoddyMacPhee: That just sounds like obfuscation to me. Sep 14, 2019 at 20:24

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?

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

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