The OEIS is supported by the many generous donors to the OEIS Foundation.

 Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 59th year, we have over 358,000 sequences, and we’ve crossed 10,300 citations (which often say “discovered thanks to the OEIS”). Other ways to Give
 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A104714 Greatest common divisor of a Fibonacci number and its index. 11
 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 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

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

Last modified November 30 04:37 EST 2022. Contains 358431 sequences. (Running on oeis4.)