What is the formula for the nth number in this series. $1,3,7,9,11,13,17,19,21\dots$
Basically all the numbers that end in the digits $1,3,7,9$
I am working on a formula for approximating how many factors I have to test to find if a large number is prime. So for example to test the number $229,597$. How many possible factors will I have to check?
So the convention is to take the square root of $229,597$ which is approx $479$. Then I take $(\frac{479}{10}) \times (4) - 1$. I do this because out of every ten numbers there are 4 numbers that end in $1,3,7,9$. I subtract the 1 because prime numbers also have 1 as a factor.
So   $(\frac{479}{10}) \times (4) - 1  = 190$ factors to check to see if $229,597$ is prime.
Then I look at the series $1,3,7,9,11,13,17\dots$ to start checking for possible factors. But how do I find the nth number in this series?
 A: One possible formula is $$f(n) = \frac{1}{4}\left(5(2n-1) + (-1)^{n+1} + 2 \cos \frac{n \pi}{2} - 2 \sin \frac{n \pi}{2}\right), \quad n = 1, 2, \ldots.$$  This corresponds to the recurrence relation
$$\begin{align}
f(n) &= f(n-1) + f(n-4) - f(n-5), \\
f(1) &= 1, \\
f(2) &= 3, \\
f(3) &= 7, \\
f(4) &= 9, \\
f(5) &= 11.
\end{align}$$
I don't know why you would need it, though.
A: You can look at OEIS A000040 or any other list of primes. This does not include $1,9,15,25,27\ldots$ from your list because those are not primes.
You can generate the list of primes yourself using the sieve of Erastothenes.  For a long list of primes this will be faster than downloading it from the internet.  This is much faster than using all the numbers equivalent to $1,3,7,9 \pmod {10}$ because there are many fewer primes.  Roughly speaking, the number of primes below $n$ is $\frac n{\log n}$, which becomes less than $0.4n$ for $n \gt 13$
Added:  to answer the question as asked, if you start counting from $0$ the $n^{th}$ term in the series is $$10\cdot \left\lfloor \frac n4 \right\rfloor+\begin{cases} 1&n\equiv 0 \pmod 4\\3&n\equiv 1 \pmod 4\\7&n \equiv 2 \pmod 4\\9&n \equiv 3 \pmod 4 \end {cases}$$
A: This is another possible formula :: Numbers that are odd but not divisible by 5.
here is small python code can be used to generate nth number. Yu can run and see the output https://www.ideone.com/dm9SPj
def getNthTerm(n):
    return n*2 + 2 * ((n-3)//4) + 1
def main():
    n=input()
    print getNthTerm(n)
main()

