login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A104714 Greatest common divisor of a Fibonacci number and its index. 8
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: A033325 A126690 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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified October 22 02:06 EDT 2017. Contains 293756 sequences.