login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A104714 Greatest common divisor of a Fibonacci number and its index. 10
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 (list; graph; refs; listen; history; text; internal format)
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 A180133

Adjacent sequences:  A104711 A104712 A104713 * A104715 A104716 A104717

KEYWORD

easy,nonn

AUTHOR

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 16 17:26 EST 2021. Contains 340206 sequences. (Running on oeis4.)