0
$\begingroup$

The following observation has been made:

Numbers in Sylvester's sequence,when reduced modulo 864, form an arithmetic progression.

This has been checked for the first ten members of the sequence:

$ 7\equiv 7 \pmod{864}\\ 43\equiv 43 \pmod{864}\\ 1807\equiv 79 \pmod{864}\\ 3263443\equiv 115 \pmod{864}\\ 10650056950807\equiv 151 \pmod{864}\\ 113423713055421844361000443 \equiv 187 \pmod{864}\\ 12864938683278671740537145998360961546653259485195807\equiv 223 \pmod{864} $

I have been unable to check other numbers in this sequence, due to the rapid growth of the sequence, the numbers become too large to handle.

Here is an attempted proof that ALL Sylvester numbers, when divided by $864$ ($864 = 4 \times 6^3$), leave a remainder which is either $7$ or $43$ or $79$ or $115$ or $151$ or $187$ or $\ldots$ or $799$ or $835$. There are only 24 possibilities. There are infinitely many Sylvester numbers, but when you divide them by $864$, the remainder of that division, can only be one of 24 numbers . These 24 numbers form an arithmetic progression: $7$, $43$, $79, $\ldots$, $763$, $799$, $835$. There are only 24 possibilities for the remainder of that division.

We note that all Sylvester numbers can be written as polynomials in powers of $6$. This is a direct consequence of the way the sequence has been defined, and the fact that the first two members of the sequence are $2$ and $3$. One may define the sequence by the recurrence relation:

$s_i=s_{i-1}(s_{i-1}-1)+1$

Sylvester's sequence can also be defined by the formula:

$s_{n}=1+\prod_{i=0}^{n-1}s_{i}$

We write the first few Sylvester numbers as polynomials in powers of $6$, and then divide them by $864$, and look at the remainder of that division. We shall also try to spot a pattern, and then prove that the pattern applies not just in the specific case we are looking at, but rather it is true in general.

Note that

$7 = (2\times 3) + 1 = 6 + 1\\43 = 6 \times 7 + 1 = 6 \times (6 +1) +1 = 6^2 + 6 + 1$

(Note that the last three terms of this polynomial add up to $43$).

$1807 = 42 \times 43 + 1 = ( 6^2 + 6 ) ( 6^2 + 6 +1 ) +1\\1807 = 6^4 + 2\times 6^3 + 2\times 6^2 + 6 + 1$

(Note that the last three terms of this polynomial add up to $79$. The other two terms of this polynomial, when added together, are divisible by $864$).

$3263443 = 1806\times 1807 + 1 = ( 6^4 + 2\times 6^3 + 2\times 6^2 + 6 )*( 6^4 + 2\times 6^3 + 2\times 6^2 + 6 + 1 ) + 1\\3263443 = 6^8 + 4\times 6^7 + 8\times 6^6 + 10\times 6^5 + 10\times 6^4 + 3\times 6^2 + 6 + 1$

(Note that the last three terms of this polynomial add up to 115. All the other terms of this polynomial, are each individually, divisible by 864, each term leaving a remainder of zero).

$10650056950807 = 3263442\times 3263443 + 1 = (\ldots + 8\times 6^6 + 10\times 6^5 + 10\times 6^4 + 3\times 6^2 + 6)\times (\ldots + 8\times 6^6 + 10\times 6^5 + 10\times 6^4 + 3\times 6^2 + 6 + 1 ) + 1 = \ldots + 88\times 6^6 + 30\times 6^5 + 20\times 6^4 + 4\times 6^2 + 6 + 1 = 10650056950807$

(Note that the last three terms of this polynomial add up to 151. All the other terms of this polynomial, are each individually, divisible by 864, each term leaving a remainder of zero).

We have spotted a pattern. When you write a Sylvester number as a polynomial in powers of six, all the terms of the polynomial greater than or equal to power 5 ($6^5$ or higher powers ) are divisible by $864\; (=\; 4\times 6^3)$.

In fact,

$6^5/864 = 9\\6^6 / 864 = 54\\6^7 / 864 = 324$

and all higher powers of 6 are divisible by 864. Therefore, the only terms in the polynomial which may not be divisible by 864 are the fourth and the third powers of 6, and the lower powers.

Therefore we have: $A\times 6^4 + B\times 6^3 + n\times 6^2 + 6 + 1$

Specifically, we have to show, that the integer coefficient of $6^4$, which we have called A, is always even (a multiple of 2 ). We must also prove that the integer coefficient of $6^3$, which we have called B, is always a multiple of 4 or it is zero. This will ensure that $A\times 6^4 + B\times 6^3$ will always be divisible by 864.

But what about the last 3 terms of the polynomial?

Recall that we wrote 43 as a polynomial in powers of 6.

$43= 6^2 + 6 + 1 = x^2 + x + 1$

We can also write 7 as a polynomial in powers of 6.

$7 = 0\times 6^2 + 6 + 1$

We can also write 1807 as a polynomial in powers of 6.

$1807 = 6^4 + 2\times 6^3 + 2\times 6^2 + 6 + 1$ We also wrote 3263443 as a polynomial in powers of 6. 3263443 = 6^8 + 4*6^7 + 8*6^6 + 10*6^5 + 10*6^4 + 3*6^2 + 6 + 1

We also wrote 10650056950807 as a polynomial in powers of 6.

$10650056950807 = \ldots + 88\times 6^6 + 30\times 6^5 + 20\times 6^4 + 4\times 6^2 + 6 + 1$

If we now compare the last three terms of all these polynomial expansions, we have:

$4\times 6^2 + 6 + 1 = 151\\3\times 6^2 + 6 + 1 = 115\\2\times 6^2 + 6 + 1 = 79\\1\times 6^2 + 6 + 1 = 43\\0\times 6^2 + 6 + 1 = 7$

Note that the last three terms of this polynomial expansion give the remainder of division by 864!!

We can use mathematical induction to prove that all Sylvester numbers, when expressed as a polynomial in powers of 6, their last three terms will be of the form: $n\times 6^2 + 6 + 1$, with $n= 0, 1, 2, 3, 4, 5, \ldots$

Because $24\times 36= 864$, we have: $24\times 6^2 + 6 + 1 = 864 + 6 + 1 = 871 \equiv 7 \pmod{864}$

Thus the pattern of remainders of dividing Sylvester numbers by 864 is cyclical, repeating itself over and over again, with a cycle length of 24.
Let us use mathematical induction to prove that the last three terms of the polynomial expansion will be of the form: n*6^2 + 6 + 1, {n=0,1,2,3,4,$\ldots$}

When n=3, we have: $s_n = 3263443 = 6^8 + 4\times 6^7 + 8\times 6^6 + 10\times 6^5 + 10\times 6^4 + 3\times 6^2 + 6 + 1$ and the last three terms are of the required form. Now assume that the result is true for n=k.

When n=k, we have $s_{k+3} = \ldots +A\times 6^4 +B\times 6^3 + k\times 6^2 + 6 + 1$ (A, B, k are all integers ). Use the recurrence relation for Sylvester's sequence.

$s_{k+4} = [\ldots+A\times 6^4 +B\times 6^3 + k\times 6^2 + 6 + 1 ]\times [\ldots+A\times 6^4 +B\times 6^3 + k\times 6^2 + 6 ] + 1$

Multiply out the two brackets to get: $s_{k+4} = A^2\times 6^8 + A\times B\times 6^7 + \ldots+k\times 6^2 + 6^2 + 1 * 6 + 1 = A^2\times 6^8 + A\times B\times 6^7 +\ldots+ (k+1)\times 6^2 + 6 + 1$

We see that the last three terms are of the required form and by induction we have proven the result.

The only thing left to prove now is that the integer coefficient of 6^4 in polynomial expansion, which we have called A, is always even (a multiple of 2). We must also prove that the integer coefficient of $6^3$ in polynomial expansion, which we have called B, is always a multiple of 4 or it is zero.

If anyone has any helpful suggestions please let me know. If you can fill the gaps in this proof, then by all means do so. Your help is appreciated. I am waiting for your suggestions and help.

$\endgroup$
  • $\begingroup$ Please use MathJax: math.meta.stackexchange.com/questions/5020/… $\endgroup$ – Lord Shark the Unknown Mar 11 '18 at 7:45
  • 1
    $\begingroup$ Have you tried modular arithmetic on the Sylvester numbers themselves at all? $\endgroup$ – Parcly Taxel Mar 11 '18 at 8:03
  • $\begingroup$ This is quite lomng-winded, but it seems t be that what you're trying to prove is that Sylvester numbers are $\equiv 7\pmod{36}$ (and I suppose that can be done easier), that's not enough to form an aritmetic progression, they also have to come in the right order for that. $\endgroup$ – Henrik Mar 11 '18 at 9:39
0
$\begingroup$

What exactly do you want to prove?

That the remainders repeat cyclically?

This can be proven much easier:

Step 1)

If the elements in a sequence $a_1, a_2, a_3 ...$ can be defined as $a_n=f(a_{n-1})$ and two elements in the sequence are equal ($a_n = a_{n+m}$) then the elements in the sequence will repeat cyclically (*):

$a_{n+m} = a_n \Rightarrow\\a_{n+m+1} = f(a_{n+m}) = f(a_n) = a_{n+1} \Rightarrow\\a_{n+m+2} = a_{n+2}\Rightarrow\\\vdots\\a_{n+2m} = a_{n+m} = a_n\Rightarrow\\\vdots\\\\a_{n+km+i} = a_{n+i}$

Step 2)

If $a \equiv b$ then $a^2 - a \equiv b^2 -b$.

Let $r_m(n)$ be the division reminder of the number $n$ when being divided by some other number $m$.

The $n^{th}$ Sylvester number can be defined as $s_n=s_{n-1}^2-s_{n-1}+1$ so the reminder can be calculated as:

$r_m(s_n)=r_m(s_{n-1}^2-s_{n-1}+1)=r_m(r_m(s_{n-1})^2-r_m(s_{n-1})+1)$

Or:

$r_m(s_n)=f(r_m(s_{n-1}))$ with $f(k)=k^2-k+1$

Because we know that $r_m(s_n)$ are integers in the range $0\leq r_m(s_n) < m$ we know that within the first $m+1$ elements of the sequence $r_m(s_1),r_m(s_2),r_m(s_3),\ldots$ at least one element must occur twice.

Now we can apply "Step 1" to the sequence $r_m(s_1),r_m(s_2),r_m(s_3),\ldots$ and prove that this sequence must repeat cyclically for any value of $m$.

For some values of $m$ (like $r_{864}(s_1) < r_{864}(s_2) < r_{864}(s_3) < \ldots$) the values of the elements will increase until one element "repeats" and a new "cycle" begins.

For other values of $m$ (like $r_{29}(s_1) < r_{29}(s_2) < r_{29}(s_3) < r_{29}(s_4) \not\leq r_{29}(s_5) < r_{29}(s_6) \not\leq r_{29}(s_7) \ldots$) this will not be the case (however the sequence will repeat cyclically anyway).

I doubt that there is another possibility to find out if the the values of the elements are increasing for a given value of $m$ but by calculating the first elements of the corresponding sequence until one element is "repeating".

(*) As English is not my native language I don't know if I am always using the correct terms. Sorry.

$\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.