|
%I #27 Jul 11 2022 19:41:45
%S 0,1,1,1,1,5,2,1,1,1,5,1,12,1,1,5,1,1,2,1,5,1,1,1,24,25,1,1,1,1,10,1,
%T 1,1,1,5,36,1,1,1,5,1,2,1,1,5,1,1,48,1,25,1,1,1,2,5,7,1,1,1,60,1,1,1,
%U 1,5,2,1,1,1,5,1,72,1,1,25,1,1,2,1,5,1,1,1,12,5,1,1,1,1,10,13,1,1,1,5,96,1
%N Greatest common divisor of a Fibonacci number and its index.
%C Considering this sequence is a natural sequel to the investigation of the problem when F_n is divisible by n (the numbers occurring in A023172). This sequence has several nice properties. (1) n | m implies a(n) | a(m) for arbitrary naturals n and m. This property is a direct consequence of the analogous well-known property of Fibonacci numbers. (2) gcd (a(n), a(m)) = a(gcd(n, m)) for arbitrary naturals n and m. Also this property follows directly from the analogous (perhaps not so well-known) property of Fibonacci numbers. (3) a(n) * a(m) | a(n * m) for arbitrary naturals n and m. This property is remarkable especially in the light that the analogous proposition for Fibonacci numbers fails if n and m are not relatively prime (e.g. F_3 * F_3 does not divide F_9). (4) The set of numbers satisfying a(n) = n is closed w.r.t. multiplication. This follows easily from (3).
%H Alois P. Heinz, <a href="/A104714/b104714.txt">Table of n, a(n) for n = 0..20000</a> (first 1001 terms from T. D. Noe)
%H Paolo Leonetti, Carlo Sanna, <a href="https://arxiv.org/abs/1704.00151">On the greatest common divisor of n and the nth Fibonacci number</a>, arXiv:1704.00151 [math.NT], 2017.
%H Carlo Sanna, Emanuele Tron, <a href="https://arxiv.org/abs/1705.01805">The density of numbers n having a prescribed G.C.D. with the nth Fibonacci number</a>, arXiv:1705.01805 [math.NT], 2017.
%F a(n) = gcd(F(n), n).
%e The natural numbers: 0 1 2 3 4 5 6 7 8 9 10 11 12 ...
%e The Fibonacci numbers: 0 1 1 2 3 5 8 13 21 34 55 89 144 ...
%e The corresponding GCDs: 0 1 1 1 1 5 2 1 1 1 5 1 12 ...
%p b:= proc(n) option remember; local r, M, p; r, M, p:=
%p <<1|0>, <0|1>>, <<0|1>, <1|1>>, n;
%p do if irem(p, 2, 'p')=1 then r:= r.M mod n fi;
%p if p=0 then break fi; M:= M.M mod n
%p od; r[1, 2]
%p end:
%p a:= n-> igcd(n, b(n)):
%p seq(a(n), n=0..100); # _Alois P. Heinz_, Apr 05 2017
%t Table[GCD[Fibonacci[n],n],{n,0,97}] (* _Alonso del Arte_, Nov 22 2010 *)
%o (Haskell) let fibs@(_ : fs) = 0 : 1 : zipWith (+) fibs fs in 0 : zipWith gcd [1 ..] fs
%o (PARI) a(n)=if(n,gcd(n,lift(Mod([1,1;1,0],n)^n)[1,2]),0) \\ _Charles R Greathouse IV_, Sep 24 2013
%Y Cf. A023172, A000045, A001177, A001175, A001176. a(n) = gcd(A000045(n), A001477(n)). a(n) = n iff n occurs in A023172 iff n | A000045(n).
%Y Cf. A074215 (a(n)==1).
%K easy,nonn
%O 0,6
%A Harmel Nestra (harmel.nestra(AT)ut.ee), Apr 23 2005
|
