54
$\begingroup$

I had the idea to make a script that generates a pattern like this:

1
2 3
4 5 6
7 8 9 10

...

and so on. After that, I replaced every non-prime by a '-' character and every prime number by a '|'. The output begins like that:

- 
|| 
-|- 
|--- 
|-|-- 
-|-|-- 
-|----- 
|-|----- 
|---|-|-- 
-|-----|-- 
---|-|----- 
|---|-|----- 
|---|-----|-- 
-----|---|-|-- 
-|-|---|------- 
------|---|-----

...

What I realized is that, with the exception of the second and third lines (possibly because of 2), on every line until 12000, the two last numbers are never prime. Obviously, one of them is even, but the odd one isn't a prime number in any of these lines.

Is there a way to prove that this is true for any line? Is there any theorem that could help?

$\endgroup$
  • 1
    $\begingroup$ The pattern is just placing numbers in lines, in ascending order, where each line has one more number than the previous line, $\endgroup$ – Bruno Henrique Sep 24 '16 at 1:42
  • 11
    $\begingroup$ The last number is 1+2+3+....+n =n (n+1)/2 which will have at least two factors. The second to last number is n (n+1)/2 -1 which is [n (n+1)-2]/2 = n^2 + n -2/2 =(n+2)(n-1)/2 which will always have at least to factors. (Note: one of n,n+1 will be even. And one of n+2, n-1 will be even. So the /2 doesn't hinder anything.] $\endgroup$ – fleablood Sep 24 '16 at 1:58
  • 3
    $\begingroup$ FYI the numbers 1, 3, 6, 10, ... are sometimes called the triangular numbers for a reason which should be obvious from your diagram. :-) $\endgroup$ – Eric Lippert Sep 24 '16 at 14:26
  • 3
    $\begingroup$ Next time you see some sequence that is never prime, always try to factorize it, because almost always it will be possible. For an interesting example that has a non-obvious factorization, $F_{4n}-1$ is never prime for any positive integer $n$, where $F_k$ is the $k$-th Fibonacci number. See math.stackexchange.com/q/1865064 for the factorization and its proof. $\endgroup$ – user21820 Sep 24 '16 at 15:06
  • $\begingroup$ @user21820 Thank you for the input. I have seen this proof already before, but it is very suggestive of the power of factorization. $\endgroup$ – астон вілла олоф мэллбэрг Sep 25 '16 at 4:03
80
$\begingroup$

Great credit to you for having discovered this, because it is a known phenomena presented in an unknown gem.

The last element on each of the lines is the sum of the first $n$ natural numbers (for example, $1=1$, $3=1+2$, $6=1+2+3$,$10=1+2+3+4$ etc.). As it turns out,the sum of the first $n$ natural numbers has a formula, given by $\frac{n(n+1)}2$. Therefore, the last number on every line is either divisible by the line number $n$ or its successor, $n+1$, whichever one is odd (one of them is odd).

For example, $6$ is divisible by its line number $3$.

$10$ is divisible by one more than its line number, $5$.

Which is why, unless you are on the second line, the last number is never going to be prime. In fact, the formula even gives its divisors.

Similarly, the second last number on each line is $\frac{n(n+1)}{2} - 1 = \frac{n^2+n-2}{2} = \frac{(n+2)(n-1)}{2}$, hence the factors of the second last number is the odd number out of $n + 2$ and $n - 1$, where $n$ is the row number. We can check this also:

$9$ is divisible by $3$, one less than $4$.

$14$ is divisible by $7$, $2$ more than $5$.

Hence, again the second to last number is not going to be prime.


I think I should add this: After some time, the fourth from last number is never going to be prime! (Think about this yourself).

After some time, the seventh from last number is never going to be prime! (Think about this yourself).

After some time, the eleventh from last number is never going to be prime! (Think about this yourself).


It is worth wondering about the nature of those elements which are not covered under the $\frac{n(n+1)}{2} - (r-1)$ scheme below. The point is, for those numbers , we take the $r-1$ on top as usual to form the number $\frac{n(n+1) - 2r + 2}{2}$, which we know is a natural number. The question is : is this composite or not?

What we do know is that for $r = 1,2,4,7$ etc. we get factorizations of the expression $n(n+1) - 2r+2$ into two linear terms in $n$, therefore we get composite numbers.

What is true, in the case of the other $r$s, is that we definitely will get infinitely many composite numbers while going through $n(n+1) - 2r + 2$. This is because every non-constant polynomial takes infinitely many composite values. In our case, for example, taking $n = k(2r-2) + 1$ for $k \in \mathbb N$, we see that $n(n+1) - 2r+2 = (2r-2)((k(2r-2) + 1)k - 1)$ is composite for $r \geq 3$. Therefore, for every $r$, there exist infinitely many rows such that the $r$th last number of that row is composite.

As for primality, the question is still open as to whether quadratic expressions(in one variable) which are not linearly factorable take infinitely many prime values. Therefore this question will remain open for some time, whether the $r$th last number of each row will stop containing primes after some time or will have infinitely many primes.

$\endgroup$
  • 2
    $\begingroup$ That's it! I forgot about the sum of arithmetic progressions. Thank you. $\endgroup$ – Bruno Henrique Sep 24 '16 at 0:59
  • $\begingroup$ You are welcome. Do see the edit. I am very pleased to see questions like this, it leads to an outpouring from my side. $\endgroup$ – астон вілла олоф мэллбэрг Sep 24 '16 at 1:03
  • $\begingroup$ Wow, that's actually a great insight. May I ask how was your thought process to realize this? $\endgroup$ – Bruno Henrique Sep 24 '16 at 1:31
  • 3
    $\begingroup$ Well, the $r$th last number in the $n$th line is $\frac{n(n+1) - 2(r-1)}{2}$. You will find that for $r=1,2,4,7,11,16,22,29$ etc that the numerator is factorizable, which leads to factors of the number. Note that pattern on $1,2,4,7,11$ etc. as well. $\endgroup$ – астон вілла олоф мэллбэрг Sep 24 '16 at 1:34
  • $\begingroup$ Dear all, my greatest gratitude to those who have read this answer and up voted or commented on it. I would like to ask if there is anything that I need to add to this answer to make it complete? $\endgroup$ – астон вілла олоф мэллбэрг Sep 26 '16 at 2:36
16
$\begingroup$

The last number in row $n$ is $\sum_{i=1}^n i = n(n+1)/2$, and the second last number is $n(n+1)/2-1 = (n-1)(n+2)/2$. You can show that these are composite for $n \ge 4$. (Consider the cases of even and odd $n$ separately.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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