login
Self-Fibonacci numbers: numbers k that divide Fibonacci(k).
64

%I #91 Sep 08 2022 08:44:47

%S 1,5,12,24,25,36,48,60,72,96,108,120,125,144,168,180,192,216,240,288,

%T 300,324,336,360,384,432,480,504,540,552,576,600,612,625,648,660,672,

%U 684,720,768,840,864,900,960,972,1008,1080,1104,1152,1176,1200,1224,1296,1320

%N Self-Fibonacci numbers: numbers k that divide Fibonacci(k).

%C 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 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 From _Max Alekseyev_, Nov 29 2010: (Start)

%C Every term greater than 1 is a multiple of 5 or 12.

%C Proof. Let n>1 divide Fibonacci number F(n) and let p be the smallest prime divisor of n.

%C If p=2, then 3|n implying further that 4|n. Hence, 12|n.

%C If p=5, then 5|n.

%C 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 Luca & Tron give an upper bound, see links. - _Charles R Greathouse IV_, Aug 04 2021

%D S. Wolfram, "A new kind of science", p. 891

%H 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 Dov Jarden, <a href="/A001602/a001602.pdf">Recurring Sequences</a>, Riveon Lematematika, Jerusalem, 1966. [Annotated scanned copy] See p. 75.

%H Tamas Lengyel, <a href="http://employees.oxy.edu/lengyel/papers/FQp_sect112502M.pdf">Divisibility Properties by Multisection</a>, Dec 2000.

%H 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 C. 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 fmod:= proc(n,m) local M,t; uses LinearAlgebra:-Modular;

%p if m <= 1 then return 0 fi;

%p if m < 2^25 then t:= float[8] else t:= integer fi;

%p M:= Mod(m,<<1,1>|<1,0>>,t);

%p round(MatrixPower(m,M,n)[1,2])

%p end proc:

%p select(n -> fmod(n,n)=0, [$1..2000]); # _Robert Israel_, May 10 2016

%t 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 Select[Range[1350], Mod[Fibonacci[ # ], # ]==0&] (* _Harvey P. Dale_ *)

%o (Haskell)

%o import Data.List (elemIndices)

%o a023172 n = a023172_list !! (n-1)

%o a023172_list =

%o map (+ 1) $ elemIndices 0 $ zipWith mod (tail a000045_list) [1..]

%o -- _Reinhard Zumkeller_, Oct 13 2011

%o (PARI) is(n)=((Mod([1,1;1,0],n))^n)[1,2]==0 \\ _Charles R Greathouse IV_, Feb 03 2014

%o (Magma) [n: n in [1..2*10^3] | Fibonacci(n) mod n eq 0 ]; // _Vincenzo Librandi_, Sep 17 2015

%Y Cf. A000350. See A127787 for an essentially identical sequence.

%Y Cf. A000045, A069104, A123976, A159051, A263112.

%Y Cf. A128974 (12n does not divide Fibonacci(12n)). - _Zak Seidov_, Jan 10 2016

%K nonn

%O 1,2

%A _David W. Wilson_

%E Edited by _Don Reble_, Sep 07 2003