Generalized Fibonacci sequences

Any linear recurrence relation yields sequences with many properties in common with the Fibonacci numbers—though with GoldenRatio replaced by other algebraic numbers. The Perrin sequence f[n_] := f[n - 2] + f[n - 3]; f[0] = 3; f[1] = 0; f[2] = 2 has the peculiar property that Mod[f[n], n] 0 mostly but not always only for n prime. (For more on recurrence relations see page 128.)