6
$\begingroup$

Given the three roots of $x^3=x^2+x+1$. Then we get the tribonacci-like sequence,

$B_n = x_1^n+x_2^n+x_3^n = 3, 1, 3, 7, 11, 21, 39, 71, 131,\dots$

where $B_n = B_{n-1}+B_{n-2}+B_{n-3}$, and the index starts with n = 0. This is A001644 of the OEIS.

I noticed that, like for the Lucas numbers, if n is prime then n divides $B_n-1$. (For example $B_7=71$ minus 1 is div by 7.) But it also has pseudoprimes, one of which is n = 182.

Question: What is the next pseudoprime?

(If I did my Mathematica session correctly, then this is the ONLY one for n < 5000, versus the Lucas numbers which has 5 pseudoprimes within that range.)

  • 0
    @StevenStadnicki: You may be interested in [this post](http://math.stackexchange.com/questions/1268311/) about tetranacci-like pseudoprimes.2015-05-05

1 Answers 1

4

I got together a quick C++ program using the matrix method mentioned in the comments (and described in detail in Fibonacci, tribonacci and other similar sequences) to search for more pseudoprimes; the next several after $182$ are $25201 (=11\cdot 29\cdot 79)$, $54289 (=233^2!)$ and $63618 (=2\cdot 3\cdot 23\cdot 461)$. There are another three between $10^5$ and $10^6$, and then five more between $10^6$ and $10^7$ (for a total of twelve $\leq 10^7$); it seems likely that the count is growing logarithmically or polylogarithmically, but the numbers involved are just too small to make a reasonable conjecture on the total number.

ADDED: while I wait for my OEIS application to go through, here's the full list less than $10^9$. This took about 3 hours for my less-than-optimal C++ code to compute, so it wouldn't be too hard to go to $10^{10}$ if someone really wanted:

$182, 25201, \color{blue}{233^2}, 63618, 194390, 750890, 804055, 1889041, 2487941, 3542533, 3761251, 6829689, 12032021, \color{blue}{233^3}, 18002881, 22586257, 28250321, 68355001, 72374401, 74458790, 79351441, 100595461, 116406374, 123872111, 191239529, 221265526, 225853633, 248947777, 338458807, 358313761, 379732501, 381427201, 509551201, 517567051, 813015901, 859481921$

  • 0
    @StevenStadnicki: I can see that you're registered: https://oeis.org/wiki/User:Steven_Stadnicki ; did you ever send the sequence itself, or were you waiting for some sort of confirmation first?2012-06-13