cp's OEIS Frontend

A069106 Composite numbers k such that k divides F(k-1) where F(j) are the Fibonacci numbers.

%I A069106 #34 Aug 20 2024 01:56:06
%S A069106 442,1891,2737,4181,6601,6721,8149,13201,13981,15251,17119,17711,
%T A069106 30889,34561,40501,51841,52701,64079,64681,67861,68101,68251,78409,
%U A069106 88601,88831,90061,96049,97921,115231,118441,138601,145351,146611,150121,153781,163081,179697,186961,191351,194833
%N A069106 Composite numbers k such that k divides F(k-1) where F(j) are the Fibonacci numbers.
%C A069106 Primes p congruent to 1 or 4 (mod 5) divide F(p-1) (cf. A045468 and [Hardy and Wright]).
%D A069106 G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers (Fifth edition), Oxford Univ. Press (Clarendon), 1979, Chap. X, p. 150.
%H A069106 Giovanni Resta, <a href="/A069106/b069106.txt">Table of n, a(n) for n = 1..1000</a>
%t A069106 A069106[nn_] := Select[Complement[Range[2,nn],Prime[Range[2,PrimePi[ nn]]]],Divisible[ Fibonacci[ #-1],#]&] (* _Harvey P. Dale_, Jul 05 2011 *)
%o A069106 (C) #include <stdio.h> #include <gmp.h> #define STARTN 10 #define N_OF_MILLER_RABIN_TESTS 5 int main() { mpz_t n, f1, f2; int flag=0; /* flag? 0: f1 contains current F[n-1] 1: f2 = F[n-1] */ mpz_set_ui (n, STARTN); mpz_init (f1); mpz_init (f2); mpz_fib2_ui (f1, f2, STARTN-1); for (;;) { if (mpz_probab_prime_p (n, N_OF_MILLER_RABIN_TESTS)) goto next_iter; if (mpz_divisible_p (!flag? f1:f2, n)) { mpz_out_str (stdout, 10, n); printf (" "); fflush (stdout); } next_iter: mpz_add_ui (n, n, 1); mpz_add (!flag? f2:f1, f1, f2); flag = !flag; } }
%o A069106 (Haskell)
%o A069106 a069106 n = a069106_list !! (n-1)
%o A069106 a069106_list = [x | x <- a002808_list, a000045 (x-1) `mod` x == 0]
%o A069106 -- _Reinhard Zumkeller_, Jul 19 2013
%o A069106 (PARI) fibmod(n,m)=((Mod([1,1;1,0],m))^n)[1,2]
%o A069106 is(n)=!isprime(n) && !fibmod(n-1,n) && n>1 \\ _Charles R Greathouse IV_, Oct 06 2016
%Y A069106 Subsequence of A123976.
%Y A069106 Cf. A045468, A003631, A064739, A081264 (Fibonacci pseudoprimes).
%Y A069106 Cf. A002808, A000045.
%K A069106 easy,nice,nonn
%O A069106 1,1
%A A069106 _Benoit Cloitre_, Apr 06 2002
%E A069106 Corrected and extended (with C program) by _Ralf Stephan_, Oct 13 2002
%E A069106 a(35)-a(40) added by _Reinhard Zumkeller_, Jul 19 2013