The sequence is: $ 5, 13, 25, 41, 61, 85, 113, ... $

How do I prove that this sequence only contains primes and semiprimes. Would it be interesting if it did only contain primes and semiprimes?


closed as off-topic by Xander Henderson, Taroccoesbrocco, stressed out, user223391, Parcly Taxel Jul 16 '18 at 7:36

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Xander Henderson, Taroccoesbrocco, stressed out, Community, Parcly Taxel
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 3
    $\begingroup$ How is this sequence even defined? $\endgroup$ – Suzet Jul 14 '18 at 1:13
  • 1
    $\begingroup$ @geocalc33 "Take 5 and add 4". That gives $9$. :P $\endgroup$ – Ant Jul 14 '18 at 1:14
  • 1
    $\begingroup$ If I take $5$ and add $4$, I get $9$ $\endgroup$ – Suzet Jul 14 '18 at 1:14
  • 1
    $\begingroup$ Looks like it's $+8$, $+12$, $+16$, $+20$, etc. $\endgroup$ – Ant Jul 14 '18 at 1:15
  • 3
    $\begingroup$ @geocalc33 Algebraically, your sequence is $a_n=2n^2+2n+1$. It won't have any members divisible by $2$ or $3$, and this makes it 'look' prime very often for small $n$, but there's no reason to believe that it will be prime (or semiprime) any more often than 'average'. What you're seeing is the law of small numbers at work. $\endgroup$ – Steven Stadnicki Jul 14 '18 at 1:16

Based on discussion in the comments, an algebraic expression for your sequence is $a_n=2n^2+2n+1$. Note that this can never be divisible by $2$ (because it's of the form $2k+1$ where $k=n^2+n$), and it can never be divisible by $3$ (this is a little bit trickier, but you can evaluate by cases depending on the value of $n\bmod 3$).

Already, those two things will make it look prime very often; for instance, of the numbers less than $100$ not divisible by $2$ or $3$, $25$ out of $33$ of them are prime! Allowing for semiprimes makes this even more stark, because for instance the first number that's neither prime nor semiprime but isn't divisible by $2$ or $3$ is $5^3=125$; there are very few of these (if I count correctly, only 28) less than a thousand and so it's not surprising that your sequence would miss almost all of them.

But a lot of this is the strong law of small numbers at work, because as the numbers involved get larger, the number of primes (and semiprimes) gets sparser; while no one knows this for certain (there are several conjectures around this area but none has been proved), right now there's no reason to believe that any polynomial sequence of this sort is prime (or semiprime) 'more often' than you would expect when any divisibility constraints are taken into account.

Incidentally, here's a nice proof (adapted from an answer to this question elsewhere on math.SE) that no nonconstant polynomial can always be prime or semiprime; in fact, we can go even further and assert that there is no upper bound on the number of (non-unique) prime factors. For concreteness I'll assume a 'positive' polynomial $p(x)$, though there's nothing in this proof that specifically requires it; it just makes the arguments moderately easier.

First, note that $p(x)$ tends to infinity as $x$ does; more specifically, $(1)$ for every $N$ there's some $x_N$ such that $p(x)\gt N$ for all $x\gt x_N$. This isn't too hard to prove (just divide out $p(x)$ by its highest-order term), but showing it rigorously would take us pretty far afield.

Next, note that $(2)$ for any modulus $M$, the polynomial $p(x)$ is periodic $\bmod M$: $p(x+M)\equiv p(x) \pmod M$. You can show this easily enough: just expand out $(x+M)^d$ using the binomial theorem and note that every term but $x^d$ is divisible by $M$.

Now, we proceed by induction: Suppose that $p(x)$ takes on a value with $n$ (nondistinct) prime factors. Then it takes on some value with greater than $n$ prime factors.

Proof: Let $q$ be a value of $p(x)$ with $n$ prime factors, attained at $p(x_q)=q$. Now, by (2) we have $p(x_q)\equiv 0\bmod q$, so $p(x_q+tq)\equiv 0\bmod q$ for all $t$. Using (1), choose a value $x_M$ such that $p(x)\gt q$ for all $x\gt x_M$, and choose $t$ such that $x_q+tq\gt x_M$ (for instance, $t=x_M$ will certainly do here). Then $p(x_q+tq)\equiv 0\bmod q$ so $p(x_q+tq)=kq$ for some $k$; but since $p(x_q+tq)\gt q$, $k\gt 1$. Since $q$ has $n$ prime factors, $kq$ must have $\gt n$ prime factors (all those of $q$, plus those of $k$).

So, if $p(x)$ takes on a prime value, it takes on some value with more than one prime factor (semiprime, or more divisible); if it takes on a semiprime value, it takes on some value with more than two prime factors; etc.


An alternative approach, just for fun:

The sequence at hand is:

$$ 5,13,25,41,61,85,113,\ldots$$

from which the first difference between terms is:

$$8, 12, 16, 20, 24, 28, \ldots$$

from which the second difference between terms is:

$$4, 4, 4, 4, 4, \ldots$$

A sequence with constant second differences is generated by a unique quadratic expression.

With that knowledge/fact in mind, there are various ways to solve for the sequence; one of them is to write a generic quadratic $f(x)=ax^2 + bx + c$ and use three different values for the input to generate three different outputs, and then solve the three equations for $a$, $b$, and $c$.

An alternative approach here: Subtract $1$ from each term:

$$4, 12, 24, 40, 60, 84, 112, \ldots$$

Notice that these are all even; so divide by $2$:

$$2, 6, 12, 20, 30, 42, 56, \ldots$$

which is equal to:

$$1(2), 2(3), 3(4), 4(5), 5(6), 6(7), 7(8), \ldots$$

i.e., $n(n+1)$. Undoing the halving by doubling, we have $2n(n+1)$; undoing the subtraction of $1$, we have $2n(n+1)+1 = 2n^2 + 2n + 1$ as the quadratic expression generating these values.

As a second fact, no quadratic expression generates only primes-or-semiprimes (you can now find a proof of this fact in the other response left here, the answer from Steven Stadnicki). Putting together the facts that your sequence of natural numbers is quadratic, and no such sequence contains only primes and semiprimes, the answer to your main question is no.

  • 1
    $\begingroup$ I just found a really nice one based around the usual proof that it can't be prime always (which is why I deleted my previous comment); I'm going to see if I can fold it into my answer... $\endgroup$ – Steven Stadnicki Jul 14 '18 at 1:37
  • $\begingroup$ @StevenStadnicki Nice! I'd seen the main argument used, but hadn't thought of the Chinese Remainder Theorem as the closer. $\endgroup$ – Benjamin Dickman Jul 14 '18 at 2:17

The first thing I would have done is look it up in the OEIS. The first result I get is A001844, the centered square numbers. The formula given is $2n(n + 1) + 1$, which can easily be rewritten as $2n^2 + 2n + 1$.

Then I don't have to scan very far to find $1105 = 5 \times 13 \times 17$ and $2665 = 5 \times 13 \times 41$.

  • $\begingroup$ This answer doesn't seem to add anything: The quadratic is already identified as $2n^2 + 2n + 1$, and a smaller example is contained in the comments: $925 = 5 \cdot 5 \cdot 37$ $\endgroup$ – Benjamin Dickman Jul 15 '18 at 4:01
  • 1
    $\begingroup$ @Benjamin Can you also point to where Sloane's A1844 was already mentioned? $\endgroup$ – Robert Soupe Jul 15 '18 at 15:52

Not the answer you're looking for? Browse other questions tagged or ask your own question.