Is it possible to know if a number exists within one of these sequences?

Question

Question:

Given a number, I need to find out which of the following rows/lists it exists in. But I don't want generate them, given that there are a lot of lists and they grow bigger over time.

We are given the following patterns.

1. $a = \textbf{0}, 4, 5, 9, 10, 14, 15, 19, 20, ..., n \quad\textbf{[+4, +1]}$

2. $b = \textbf{1}, 5, 8, 12, 15, 19, 22, 26, 29, ..., n\quad\textbf{[+4, +3]}$

3. $c = \textbf{1}, 9, 12, 20, 23, 31, 34, 42, 45, ..., n\quad\textbf{[+8, +3]}$

4. $d = \textbf{2}, 10, 15, 23, 28, 36, 41, 49, 54, ..., n\quad\textbf{[+8, +5]}$

5. $e = \textbf{2}, 14, 19, 31, 36, 48, 53, 65, 70, ..., n\quad\textbf{[+12, +5]}$

6. $f = \textbf{3}, 15, 22, 34, 41, 53, 60, 72, 79, ..., n\quad\textbf{[+12, +7]}$

7. $g = \textbf{3}, 19, 26, 42, 49, 65, 72, 88, 95, ..., n\quad\textbf{[+16, +7]}$

8. $h = \textbf{4}, 20, 29, 45, 54, 70, 79, 95, 104, ..., n\quad\textbf{[+16, +9]}$

9. $i =$ Etc.

Examples:

Where is 4? -> 4 is in list 1 (1,2)

Where is 5? -> 5 is in list 1 (1,3) and/or list 2 (2,2) [one answer is enough]

Only the list is of importance, the position within not so much.

When it comes to finding a given number, the amount of testing is also of crucial importance. As the whole point of this is to try and achieve the most optimal time complexity.

---

Answer 1

Since there are multiple solutions possible, you cannot just have one function. It is possible however to check if any number is part of a particular pattern. A pattern is described by three numbers. For computational simplicity, I will choose $a_{n,0}$ the first element of series $n$, the first step $t_n$, and the sum of the steps as $s_n$. A number $x$ is in series $n$ if either $(x-a_{n,0})$ or $(x-a_{n,0}-t_n)$ is divisible by $s_n$.

So now the problem simplifies to calculating $a_{n,0}$, $s_n$, and $t_n$ as functions of $n$. The first element can be written as $$a_{n,0}=\left\lfloor\frac n2\right\rfloor$$

For $t_n$ we can see a similar pattern $$t_n=4\left\lfloor\frac {n+1}2\right\rfloor$$ Finally, the second step is $2a_{n,0}+1$, so $$s_n=4\left\lfloor\frac {n+1}2\right\rfloor+2\left\lfloor\frac n2\right\rfloor+1$$

Answer 2

This is more of an extended comment than an answer, but it might help focus on what needs to be done. (Actually, it's now more of an answer than an extended comment; see the Added later section.)

You are fundamentally asking a question about computational complexity: Given a large number $N$ (let's say $N=10{,}000$), how efficiently can we find the smallest $n$ such that $N$ appears in list $(n)$? It's obvious that $N$ is the first entry in lists $(2N)$ and $(2N+1)$; the live question is whether it appears in any earlier lists.

The entries in list $(2k-1)$ (for $k\ge1$) are the nonnegative integers congruent to $k-1$ and $5k-1$ mod $6k-1$, while the entries in list $(2k)$ are the positive integers congruent to $k$ and $5k$ mod $6k+1$. So if $N$ belongs to an earlier list, we have one (or more) of the following:

$$N=\begin{cases} k-1+(6k-1)m\\ 5k-1+(6k-1)m\\ k+(6k+1)m\\ 5k+(6k+1)m \end{cases}$$

for some $k\ge1$ and $m\ge0$.

You might compare this to the question of factorization: It's obvious that $N$ divides $N$, the question is whether any smaller integer (greater than $1$) divides $N$, i.e. does $N=(k+1)(m+1)$ have any solutions with $k,m\ge1$? (To be somewhat more precise, for factorization we'd be asking for the smallest prime factor.) Factorization is known to be in NP and suspected to be in NP\P. The problem here is similarly in NP; the question is where it stands with respect to P.

Added later: It occurs to me the connection with factorization is indeed quite strong. For example,

$$N=k+(6k+1)m\iff6N=36km+6k+6m=(6k+1)(6m+1)-1$$ and $$N=5k+(6k+1)m\iff6N=36km+30k+6m=(6k+1)(6m+5)-5$$

so testing $N$ for membership in list $(2k)$ boils down to considering possible factorizations of $6N+1$ and $6N+5$. For $N=10{,}000$, for example, $60{,}001=29\cdot2069$, neither of which is congruent to $1$ mod $6$, but $60{,}005=5\cdot11\cdot1091=55\cdot1091$, so $N=10{,}000$ appears in list $(18)$. One can do something similar for membership in list $(2k-1)$:

$$N=k-1+(6k-1)m\iff6N=36km+6k-6m-6=(6k-1)(6m+1)-5$$ and $$N=5k-1+(6k-1)m\iff6N=36km+30k-6m-6=(6k-1)(6m+5)-1$$

If, as appears to be desired, the first element of each list is to be omitted, the condition $m\ge0$ can be replaced with $m\ge1$ and the second and fourth conditions above can be modified by replacing $m$ with $m-1$. The conditions for membership in list $(2k)$ are then

$$N+1=(6k+1)(6m+1)$$ and $$N+5=(6k+1)(6m-1)$$

while the conditions for membership in list $(2k-1)$ are

$$N+5=(6k-1)(6m+1)$$ and $$N+1=(6k-1)(6m-1)$$

all with $k\ge1$ and $m\ge1$. At least one of these four conditions will be satisfied if and only if at least one of $6N+1$ and $6N+5$ is composite, that is, if $(6N+1,6N+5)$ is not a pair of cousin primes.