Finding a formula for a sequence or proving it is impossible

Question

I tried to search for a formula that produces the following sequence: 35 49 55 65 77 85 91 95 115

Etc, a larger sequence is in the following link: https://pastebin.com/HDDHe7bz

Or proving that such formula is impossible.

I have asked more people and it is possible but the complexity of the formula grows it means it takes a lot of time to calculate large numbers.

The only requirement is that the formula should not grow exponentially in complexity for larger values.

A personal computer should be able to calculate lets say the millionth number of the sequence in less than 2 seconds, and the two millionth in less than 3 secs for example.

Answer 1

Hint By Lagrange interpolation you can find a 8th degree polynomial such that $$P(1)=35; P(2)=49; P(3)= 55; P(4)= 65; P(5)= 77; P(6)= 85; P(7)= 91; P(8)= 95; P(9)= 115$$

You can even find infinitely many polynomials of higher degree satisfying these requirement: $$P(x)+h(x)(X-1)(X-2)(X-3)(X-4)(X-5)(X-6)(X-7)(X-8)(X-9)$$ where $h$ is any polynomial. You can even replace $h$ by an arbitrary function.

Answer 2

The Online Encyclopedia of Integer Sequences

Pseudoprimes

So, we can say that 25, 35, 49, 55, 65, 77, 85, 91, … are pseudoprimes with respect to the property of being of the form $\{\displaystyle 6n-1\ \} \times \{\displaystyle 6n-1\ \}$ or $\{\displaystyle 6n+1\ \} \{\displaystyle 6n+1\ \}$

Pseudoprimes

Other methods

A038509 Composite numbers congruent to +-1 mod 6.

A067793 Nonprimes n such that phi(n) > 2n/3.

A287918 Union of nonprime 1 <= t <= m for m in A036913, with gcd(t,m) = 1.