5
$\begingroup$

The sequence is defined by the following formula $d_{n + 3} = d_{n + 2} + 2d_{n + 1} - d_n$ where $d_1 = 0, d_2 = 1, d_3 = 2$, $\{0, 1, 2, 4, 7, 13, 23,42, ...\}$ if this sequence is calculated over finite field $p$ $$(d_{n + 3} = d_{n + 2} + 2d_{n + 1} - d_n)\,mod\,\text{p}$$ It follows that if $p$ is prime, then the last three terms $d_{p - 1},\; d_p$, and $d_{p + 1}$ fall within one of the following ending patterns $\;\{4, 2, 1\}$ , $\{p - 1, 0, 1\}$, or $\{p - 6, p - 3, p - 2\}$. this is true for all prime up to tested range, $60000$

my questions

  1. why only primes follow these patterns?
  2. is there any non prime(s) following this patterns?
  3. is there any published work like this and in the same pattern. To see if i can study more about it
Improve this question
$\endgroup$
2

2 Answers 2

Reset to default
4
$\begingroup$

Prime $p=7$ fails the test, but this is the only exception below $10^7$. This is likely explained by the characteristic polynomial $x^3 - x^2 - 2x + 1$ having discriminant $49=7^2$.

Also, there are nine pseudoprimes below $10^7$: $$530881,~ 597871,~ 1152271,~ 3057601,~ 3581761,~ 3698241,~ 5444489,~ 5968873,~ 6868261.$$

Improve this answer
$\endgroup$
6
  • $\begingroup$ can you please explain further... why? $\endgroup$
    – Esdras E E Dansha
    Jan 31, 2018 at 19:47
  • $\begingroup$ I have checked some of the pseudo primes. They are 1 mod 7. It may be numbers which pass the test and are not prime are required to be 1 mod 7. You might try for a pseudo prime theorem involving your condition to get necessary conditions on such pseudo primes. Gerhard "Switch From Inference To Deduction" Paseman, 2018.01.31. $\endgroup$
    – Gerhard Paseman
    Jan 31, 2018 at 20:06
  • $\begingroup$ @EsdrasEEDansha: why what? $\endgroup$
    – Max Alekseyev
    Jan 31, 2018 at 20:20
  • $\begingroup$ so all pseudo primes fall into 1mod7... right? $\endgroup$
    – Esdras E E Dansha
    Jan 31, 2018 at 20:27
  • $\begingroup$ @GerhardPaseman: There are pseudoprimes $\not\equiv 1\pmod{7}$, e.g., $28805713$. $\endgroup$
    – Max Alekseyev
    Jan 31, 2018 at 20:56
1
$\begingroup$

This should really be just a comment, but I had some technical difficulties.

Consider a number $x$ whose consecutive powers satisfy the recursive formula in the definition of your sequence, that is, $$x^3=x^2+2x-1.\qquad{(1)} $$ This equation has three different roots, all of them real. Call them $x_1,x_2,x_3$. Let $a_1,a_2,a_3\in\mathbb{R}$ be arbitrary. For $n\in\mathbb{N}$, define $$c_n=a_{1}x_{1}^n+a_{2}x_{2}^n+a_{3}x_{3}^n.\qquad{(2)} $$ Now $c_{n+3}=c_{n+2}+2c_{n+1}-c_{n}$ for all $n$. On the other hand, given any starting values for $c_1,c_2,c_3$, you can solve for $a_1,a_2,a_3$. So, in particular, there are values for the coefficients $a_1,a_2,a_3$ which give the sequence $(d_n)_{n\in\mathbb{N}}$ by the formula $(2)$.

I suggest having a look at equation $(1)$ modulo a number. I'm afraid I haven't yet developed this idea further, so please regard this as a rather long comment.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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