cp's OEIS Frontend

A023172 Self-Fibonacci numbers: numbers k that divide Fibonacci(k).

%I A023172 #97 Jun 28 2025 09:40:42
%S A023172 1,5,12,24,25,36,48,60,72,96,108,120,125,144,168,180,192,216,240,288,
%T A023172 300,324,336,360,384,432,480,504,540,552,576,600,612,625,648,660,672,
%U A023172 684,720,768,840,864,900,960,972,1008,1080,1104,1152,1176,1200,1224,1296,1320
%N A023172 Self-Fibonacci numbers: numbers k that divide Fibonacci(k).
%C A023172 Sequence contains all powers of 5, infinitely many multiples of 12 and other numbers (including some factors of Fibonacci(5^j), e.g., 75025).
%C A023172 If m is in this sequence then 5*m is (since 5*m divides 5*F(m) which in turn divides F(5*m)). Also, if m is in this sequence then F(m) is in this sequence (since if gcd(F(m),m)=m then gcd(F(F(m)),F(m)) = F(gcd(F(m),m)) = F(m)). - _Max Alekseyev_, Sep 20 2009
%C A023172 From _Max Alekseyev_, Nov 29 2010: (Start)
%C A023172 Every term greater than 1 is a multiple of 5 or 12.
%C A023172 Proof. Let n>1 divide Fibonacci number F(n) and let p be the smallest prime divisor of n.
%C A023172 If p=2, then 3|n implying further that 4|n. Hence, 12|n.
%C A023172 If p=5, then 5|n.
%C A023172 If p is different from 2 and 5, then p divides either F(p+1) or F(p-1) and thus p divides either F(gcd(n,p+1)) or F(gcd(n,p-1)). Minimality of p implies that gcd(n,p-1)=1 and gcd(n,p+1)=1 (notice that p+1 being prime implies p=2 which is not the case). Therefore, p divides F(1)=1, a contradiction to the existence of such p. (End)
%C A023172 Luca & Tron give an upper bound, see links. - _Charles R Greathouse IV_, Aug 04 2021
%D A023172 S. Wolfram, "A new kind of science", p. 891
%H A023172 Seiichi Manyama, <a href="/A023172/b023172.txt">Table of n, a(n) for n = 1..10000</a> (first 500 terms from T. D. Noe, next 4600 terms from Lars Blomberg)
%H A023172 Oisín Flynn-Connolly, <a href="https://arxiv.org/abs/2504.09938">On the divisibility of sums of Fibonacci numbers</a>, arXiv:2504.09938 [math.NT], 2025. See p. 1.
%H A023172 Dov Jarden, <a href="/A001602/a001602.pdf">Recurring Sequences</a>, Riveon Lematematika, Jerusalem, 1966. [Annotated scanned copy] See p. 75.
%H A023172 Tamas Lengyel, <a href="http://employees.oxy.edu/lengyel/papers/FQp_sect112502M.pdf">Divisibility Properties by Multisection</a>, Dec 2000. <a href="https://www.fq.math.ca/41-1.html"> Fib Q. 41 (1) 72</a>
%H A023172 Florian Luca and Emanuele Tron, <a href="http://arxiv.org/abs/1410.2489">The Distribution of Self-Fibonacci Divisors</a>, Proceedings of the Thirteenth Conference of the Canadian Number Theory Association (CNTA XIII), Ayşe Alaca, Şaban Alaca, and Kenneth Williams, ed. (2015), pp. 149-158. arXiv:1410.2489 [math.NT], 2014.
%H A023172 Chris Smyth, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL13/Smyth/smyth2.html">The terms in Lucas Sequences divisible by their indices</a>, JIS 13 (2010) #10.2.4.
%p A023172 fmod:= proc(n,m) local M,t; uses LinearAlgebra:-Modular;
%p A023172     if m <= 1 then return 0 fi;
%p A023172     if m < 2^25 then t:= float[8] else t:= integer fi;
%p A023172     M:= Mod(m,<<1,1>|<1,0>>,t);
%p A023172     round(MatrixPower(m,M,n)[1,2])
%p A023172 end proc:
%p A023172 select(n -> fmod(n,n)=0, [$1..2000]); # _Robert Israel_, May 10 2016
%t A023172 a=0; b=1; c=1; Do[a=b; b=c; c=a+b; If[Mod[c, n]==0, Print[n]], {n, 3, 1500}]
%t A023172 Select[Range[1350], Mod[Fibonacci[ # ], # ]==0&] (* _Harvey P. Dale_ *)
%o A023172 (Haskell)
%o A023172 import Data.List (elemIndices)
%o A023172 a023172 n = a023172_list !! (n-1)
%o A023172 a023172_list =
%o A023172    map (+ 1) $ elemIndices 0 $ zipWith mod (tail a000045_list) [1..]
%o A023172 -- _Reinhard Zumkeller_, Oct 13 2011
%o A023172 (PARI) is(n)=((Mod([1,1;1,0],n))^n)[1,2]==0 \\ _Charles R Greathouse IV_, Feb 03 2014
%o A023172 (Magma) [n: n in [1..2*10^3] | Fibonacci(n) mod n eq 0 ]; // _Vincenzo Librandi_, Sep 17 2015
%Y A023172 Cf. A000350. See A127787 for an essentially identical sequence.
%Y A023172 Cf. A000045, A069104, A123976, A159051, A263112.
%Y A023172 Cf. A128974 (12n does not divide Fibonacci(12n)). - _Zak Seidov_, Jan 10 2016
%K A023172 nonn
%O A023172 1,2
%A A023172 _David W. Wilson_
%E A023172 Edited by _Don Reble_, Sep 07 2003