5
$\begingroup$

Call a sequence $(a_n)$ of positive integers easily computable if there is a constant $C$ and an algorithm which computes $a_n$ from $n$, $a_1, \dots, a_{n-1}$ and a finite number of integer constants in at most $C$ steps, i.e. additions, subtractions, multiplications, divisions / computations of remainders and making choices among finite numbers of cases.

Further call an easily computable sequence $(a_n)$ reducible if there is an easily computable sequence $(b_n)$ such that $\forall n \in \mathbb{N} \ \ b_n | a_n$ and such that at most finitely many $b_n$ are equal to $1$ or to $a_n$, and irreducible otherwise.

Question: Does there exist an irreducible easily computable sequence which contains only composite numbers? And if yes, does there exist such sequence which does not grow faster than exponentially? If the answer is still yes, does there exist such sequence which does not grow faster than polynomially?

Remarks: I strongly guess that the answer to the first question is yes -- though I'd be interested to see an explicit example, with a proof that it is indeed an example. As to the second and third question, things seem less clear -- though a negative answer would be a pretty strong result.

Examples: Easily computable sequences in our sense are e.g. $a_n := n^2+1$ (with $C = 2$), the Fibonacci sequence (with $C = 1$), $a_1 := 2, a_{n+1} := 2a_n$ (powers of two, with $C = 1$), $a_1 := 3, a_{n+1} := (a_n-1)^2+1$ (Fermat numbers, with $C = 3$), and $a_1 = a_2 = 1$, $a_n := a_{n-a_{n-1}} + a_{n-a_{n-2}}$ for $n \geq 3$ (Hofstadter's Q-sequence; $C = 5$), as well as Collatz-type sequences ($C = 5$). Reducible such sequences are e.g. $a_n := n^2-1$ (put $b_n := n-1$), $a_n := n^2+n+2$ (put $b_n := 2$), $a_n := 78557 \cdot 2^n + 1$ (put $b_n := 3$ if $n \equiv 0(2)$, $b_n := 5$ if $n \equiv 1(4)$, $b_n := 7$ if $n \equiv 7(12)$, $b_n := 13$ if $n \equiv 11(12)$, $b_n := 19$ if $n \equiv 15(36)$, $b_n := 37$ if $n \equiv 27(36)$ and $b_n := 73$ if $n \equiv 3(36)$). Irreducible ones are e.g. $a_n := n$ and $a_n := 4n+1$.

Improve this question
$\endgroup$
5
  • 3
    $\begingroup$ Interesting question. If I understand it well, Fermat sequence $2^{2^n}+1$ for $n \geq 5$ should be a good candidate for question 1, since it is easily computable, conjectured to be always composite, but that we have no idea how we could construct an easily computable sequence of divisors. But this is of course too hard to prove now, and you ask for an example that would provably works. $\endgroup$
    – Joël
    Commented May 6, 2017 at 12:09
  • $\begingroup$ @Joël: Finding out whether the Fermat sequence for $n \geq 5$ is an example would likely indeed be too hard. -- But there are so many other candidates which one could try. $\endgroup$
    – Stefan Kohl ♦
    Commented May 6, 2017 at 12:21
  • 4
    $\begingroup$ You are allowed to compute $y=2^{x-1}$ along with $x$ (in the alternating positions). So you can just put $x'_n=x_{n-1}+1$, $y'_n=2*y_{n-1}$, check the remainder $y_n'\mod x_n'$ and, if it is $1$, skip this pair and advance one more step. This way you'll get all composite integers such that the Fermat test with base $2$ refutes their primality (plus some powers of $2$ that are surely composite). Intuitively, it is obvious that the task of creating an easily computable proper divisor sequence for them is about as hopeless as for all composite integers and the latter one is impossible but... $\endgroup$
    – fedja
    Commented May 6, 2017 at 12:29
  • $\begingroup$ @fedja: Yes, this appears to be an example which answers the first two questions -- if nonexistence of an easily computable proper divisor sequence can be established, of course ... . -- Do you have any idea about the case of less-than-exponential, respectively, polynomial, growth? $\endgroup$
    – Stefan Kohl ♦
    Commented May 6, 2017 at 12:39
  • 1
    $\begingroup$ Growth is not a problem: just slow the process down introducing a linear counter from $2^{x-1}$ down over even integers and advance only when the counter reaches 4 with resetting. However, I would love to see the proof that you cannot create an easily computable sequence $x_n$ such that $x_n$ is a proper divisor of $n$ whenever $n$ is composite. $\endgroup$
    – fedja
    Commented May 6, 2017 at 13:41

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .