A104714 Greatest common divisor of a Fibonacci number and its index.

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, 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, 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

Offset

0,6

Comments

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).

Links

Alois P. Heinz, Table of n, a(n) for n = 0..20000 (first 1001 terms from T. D. Noe)

Paolo Leonetti, Carlo Sanna, On the greatest common divisor of n and the nth Fibonacci number, arXiv:1704.00151 [math.NT], 2017.

Carlo Sanna, Emanuele Tron, The density of numbers n having a prescribed G.C.D. with the nth Fibonacci number, arXiv:1705.01805 [math.NT], 2017.

Formula

a(n) = gcd(F(n), n).

Example

The natural numbers:    0 1 2 3 4 5 6  7  8  9 10 11  12 ...
The Fibonacci numbers:  0 1 1 2 3 5 8 13 21 34 55 89 144 ...
The corresponding GCDs: 0 1 1 1 1 5 2  1  1  1  5  1  12 ...

Maple

b:= proc(n) option remember; local r, M, p; r, M, p:=
      <<1|0>, <0|1>>, <<0|1>, <1|1>>, n;
      do if irem(p, 2, 'p')=1 then r:= r.M mod n fi;
         if p=0 then break fi; M:= M.M mod n
      od; r[1, 2]
    end:
a:= n-> igcd(n, b(n)):
seq(a(n), n=0..100);  # Alois P. Heinz, Apr 05 2017

Mathematica

Table[GCD[Fibonacci[n], n], {n, 0, 97}] (* Alonso del Arte, Nov 22 2010 *)

Prog

(Haskell) let fibs@(_ : fs) = 0 : 1 : zipWith (+) fibs fs in 0 : zipWith gcd [1 ..] fs
(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

Crossrefs

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).

Cf. A074215 (a(n)==1).

Sequence in context: A126690 A338945 A263007 * A085119 A010128 A348993

Adjacent sequences: A104711 A104712 A104713 * A104715 A104716 A104717

Keyword

easy,nonn

Author

Harmel Nestra (harmel.nestra(AT)ut.ee), Apr 23 2005

Status

approved