1
$\begingroup$

The following observation has been made:

Numbers in Sylvester's sequence,when reduced $modulo 864$, form an arithmetic progression, namely $$7,43,79,115,151,187,223,259,295,331,.....$$

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

$$7≡7(mod864)$$ $$43≡43(mod864)$$ $$1807≡79(mod864)$$ $$3263443≡115(mod864)$$ $$10650056950807≡151(mod864)$$ $$113423713055421844361000443≡187(mod864)$$ $$12864938683278671740537145998360961546653259485195807≡223(mod864)$$

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. However, we can use congruence relations, congruence arithmetic and arithmetic of residue classes to prove that Sylvester numbers ,when reduced $modulo 864$, form an arithmetic progression. Consider the following: One may define the sequence by the recurrence relation:

$$si=si−1(si−1−1)+1$$

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

$$sn=1+∏n−1i=0si$$

$$7≡7 (mod864)$$ $$7x6+1=43≡43 (mod864)$$ $$43x42+1=1807≡79 (mod 864)$$ $$79x78+1=6163≡115 (mod 864)$$ $$115x114+1=13111≡151 (mod 864)$$ $$151x150+1=22651≡187 (mod 864)$$ $$187x186+1=34783≡223 (mod 864)$$ $$223x222+1=49507≡259 (mod 864)$$ $$259x258+1=66823≡295 (mod 864)$$ $$295x294+1=86731≡331 (mod 864)$$ $$331x330+1=109231≡367 (mod 864)$$ $$367x366+1=134323≡403 (mod 864)$$ $$403x402+1=162007≡439 (mod 864)$$ $$439x438+1=192283≡475 (mod 864)$$ $$475x474+1=225151≡511 (mod 864)$$ $$511x510+1=260611≡547 (mod 864)$$ $$547x546+1=298663≡583 (mod 864)$$ $$583x582+1=339307≡619 (mod 864)$$ $$619x618+1=382543≡655 (mod 864)$$ $$655x654+1=428371≡691 (mod 864)$$ $$691x690+1=476791≡727 (mod 864)$$ $$727x726+1=527803≡763 (mod 864)$$ $$763x762+1=581407≡799 (mod 864)$$ $$799x798+1=637603≡835 (mod 864)$$ $$835x834+1=696391≡7 (mod 864)$$ $$7x6+1 =43≡43 (mod 864)$$ $$43x42+1 =1807≡79 (mod 864)$$ $$79x78+1=6163≡115 (mod 864)$$ etc.

Notice that after $24$ cycles , we get back to where we started. Hence Sylvester numbers , reduced $modulo 864$ form an arithmetic progression of $24$ terms which will then repeat until infinity. Therefore Sylvester sequence , reduced $mod 864$, forms an arithmetic progression of $24$ terms, which will repeat until infinity. QED

$\endgroup$
  • $\begingroup$ Please see math.meta.stackexchange.com/questions/5020 Incidentally, have you an OEIS number for this sequence? $\endgroup$ – Lord Shark the Unknown Nov 16 '18 at 21:00
  • $\begingroup$ It's easy to compute the Sylvester numbers modulo any small number, just use the recursive definition...$a_{n+1}=a_n^2-a_n+1$. $\pmod {864}$ the sequence goes $\{2,3,7,43,79,115,151,187,223,259,295,331,367,403,439,475,511,547,583,619,655,\cdots \}$ and so on. $\endgroup$ – lulu Nov 16 '18 at 21:09
  • $\begingroup$ Sylvester's sequence at OEIS: oeis.org/A000058 $\endgroup$ – nickgard Nov 16 '18 at 21:15
  • $\begingroup$ I expanded my answer to show how it arises simply via the Binomial Theorem. $\endgroup$ – Bill Dubuque Nov 18 '18 at 0:09
  • $\begingroup$ I don't see a question here. $\endgroup$ – Gerry Myerson Nov 18 '18 at 0:11
1
$\begingroup$

Hint:

If $$a_n=36n+7$$ then $$a_n^2-a_n+1=(36n+7)^2-(36n+7)+1=432n^2+468n+43=36(12n^2+13n+1)+7.$$

Now remains to study

$$(12n^2+13n+1)\bmod\frac{864}{36}.$$

(Final hint, $12n(n+1)\bmod24=0$.)

$\endgroup$
1
$\begingroup$

Below I give a simple direct proof, then I explain how it boils down to the Binomial Theorem.

Notice $\bmod 864\!:\ \ a_n = 7\! +\! 36j \ \Longrightarrow\ \color{#0a0}{a_{n+1}}\,\equiv\, \color{#0a0}{a_n}\!+\color{#c00}{36}\,\ $ by

$\underbrace{\color{#0a0}{a_{n+1}\!-\!a_n} = (a_n\!-\!1)^2}_{\Large a_{n+1}\ =\ a_n^2-a_n+1}\! = (6\!+\!36j)^2\! = 36+432\,\underbrace{j(1\!+\!3j)}_{\large \rm even}\equiv \color{#c00}{36}.\,$

Remark $ $ This is closely connected to the arithmetic progression that arises from the first two terms of the Binomial Theorem $\, (1+b)^n = \color{#0a0}{1+nb}\,\pmod{\!b^2}.\,$ To make this clearer we examine the sequence $\,b_n := a_n\! - 1,\,$ which satisfies $\,b_{k+1} = b_k + b_k^2,\,\ b_0 = 1.$

Lemma $ $ Suppose a sequence $b_k$ satisfies the recurrence $\,b_{k+1} = b_k(1+ b_k).\,$ Then $$ b := b_{\large k}\, \Rightarrow\, b_{\large k+n} \equiv b(1+b)^n\equiv b(\color{#0a0}{1+nb})\ \pmod {\!b^3}\qquad $$

Proof $ $ By induction on $n$. Clear if $n=0.\,$ Suppose for induction it is true for $n$. Then

$\qquad\ \ \begin{align} \bmod \color{#c00}{b^3}\!:\ \ \ b_{\large j+n+1}\, = &\qquad\, b_{\large j+n}\ (1+b_{\large j+n})\\ = &\,\ \color{#c00}b(1+nb)(1+b+n\color{#c00}{b^2)}\\ \equiv &\,\ b(1+nb)(1+b)\ \ \ {\rm by}\ \ \color{#c00}b\color{#c00}{b^2}\equiv 0\\ \equiv &\,\ b(1+(n\!+\!1)b)\\ \equiv &\,\ b(1+b)^{\large n+1}\qquad\qquad\quad {\bf QED} \end{align}\qquad\qquad\qquad $

When $\,b = 2\!+\!4i\equiv 2\pmod{\!4}$ we can enlarge the modulus to $\,4b^3$ since, as above

$\quad\ \ \ \ \begin{align} \bmod \color{#c00}{4b^3}\!:\ \ \ b_{j+n+1} \equiv &\,\ b(1+(n\!+\!1)b) + \color{#c00}2\,{\underbrace{n(1+nb/2}_{\color{#c00}{\rm even}})}\,\color{#c00}{b^3}\\[.2em] \end{align}\qquad\qquad\qquad $

Here $\,b_2 = 6\,$ so we get $\,b_{2+n}\equiv 6 + 36n\pmod{\!864},\,$ just as you observed.

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