A074215 -id:A074215 - cp's OEIS frontend

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

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

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

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

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.

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

let fibs@(_ : fs) = 0 : 1 : zipWith (+) fibs fs in 0 : zipWith gcd [1 ..] fs

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

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

a(n)=if(n,gcd(n,lift(Mod([1,1;1,0],n)^n)[1,2]),0) \\ Charles R Greathouse IV, Sep 24 2013

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

A352747 Array read by ascending antidiagonals. A(n, k) = F(k, n) mod n for n >= 1 and k >= 0, where F(n, k) = A352744(n, k) are the Fibonacci numbers, A(0, k) = 1 for k >= 0.

Original entry on oeis.org

1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 2, 0, 1, 0, 1, 3, 1, 2, 0, 0, 1, 5, 3, 0, 1, 1, 0, 1, 1, 1, 3, 3, 0, 0, 0, 1, 5, 0, 3, 3, 2, 2, 1, 0, 1, 3, 2, 6, 5, 3, 1, 1, 0, 0, 1, 4, 1, 7, 5, 1, 3, 0, 0, 1, 0, 1, 0, 9, 8, 4, 4, 3, 3, 3, 2, 0, 0, 1, 5, 1, 4, 6, 1, 3, 5, 3, 2, 1, 1, 0, 1

Offset: 0

Peter Luschny, Apr 08 2022

This array aims the study of the divisibility properties of the Fibonacci numbers A352744. The identity F(n, k) = (-1)^k*F(1 - n, -k) from A352744 shows that negative indices do not add to the divisibility properties of F(n, k).
All rows A(n, .) are pure periodic sequences. The length of the periods is given by (1, A270313). For n > 0 the length of the period of row A(n, .) is <= n.
The period length is 1 for n in (1, A023172) and n for n in (1, A074215), as observed by Robert Israel in A270313. In particular, if n is a power of 2 or a prime (A174090), then the period length is n.
The indices of the zero-free rows are in A353280. A zero-free row A(n, .) means that n will not divide F(k, n) whatever value k takes. For that it is sufficient to check that period(A(n, .)) is zero-free.
If period(A(n, .)) = [k | 0 <= k < n] we call n a 'Fibonacci friend'. In other words, in this case F(k, n) mod n = k for 0 <= k < n. A Fibonacci friend does not have to be prime (since 1 is a Fibonacci friend), but if it is  prime then it is congruent to {1, 4} mod 5 (A045468), and all such primes are Fibonacci friends.
To say that n is a Fibonacci friend is equivalent to saying that A(n, n) = 0 and that n divides F(n, n). Fibonacci friends are the indices of the zeros in A002752.
Integers n > 0 that divide Sum{k=0..n-1} (F(k, n) mod n) are congruent to {0, 1, 3, 5} mod 6 (A301729).

			Array starts (periods are indicated with () ):
[n\k] 0   1   2   3   4  5  6   7   8   9  10  11  12
----------------------------------------------------------
[ 0] (1), 1,  1,  1,  1, 1, 1,  1,  1,  1,  1,  1,  1, ...
[ 1] (0), 0,  0,  0,  0, 0, 0,  0,  0,  0,  0,  0,  0, ...
[ 2] (1,  0), 1,  0,  1, 0, 1,  0,  1,  0,  1,  0,  1, ...
[ 3] (1,  0,  2), 1,  0, 2, 1,  0,  2,  1,  0,  2,  1, ...
[ 4] (2,  1,  0,  3), 2, 1, 0,  3,  2,  1,  0,  3,  2, ...
[ 5] (3), 3,  3,  3,  3, 3, 3,  3,  3,  3,  3,  3,  3, ...
[ 6] (5,  1,  3), 5,  1, 3, 5,  1,  3,  5,  1,  3,  5, ...
[ 7] (1,  0,  6,  5,  4, 3, 2), 1,  0,  6,  5,  4,  3, ...
[ 8] (5,  2,  7,  4,  1, 6, 3,  0), 5,  2,  7,  4,  1, ...
[ 9] (3,  1,  8,  6,  4, 2, 0,  7,  5), 3,  1,  8,  6, ...
[10] (4,  9), 4,  9,  4, 9, 4,  9,  4,  9,  4,  9,  4, ...
[11] (0,  1,  2,  3,  4, 5, 6,  7,  8,  9, 10), 0,  1, ...
[12] (5), 5,  5,  5,  5, 5, 5,  5,  5,  5,  5,  5,  5, ...

Cf. A352744, A002752, A045468, A074215, A088209, A174090, A212804, A270313, A301729, A353280.

f := n -> combinat:-fibonacci(n + 1):
F := proc(n, k) option remember; (n-1)*f(k-1) + f(k) end:
A := (n, k) -> ifelse(n = 0, 1, modp(F(k, n), n)):
for n from 0 to 12 do seq(A(n, k), k = 0..10) od;

F[n_, k_] := (n - 1)*Fibonacci[k] + Fibonacci[k + 1];
A[n_, k_] := If[n == 0, 1, Mod[F[k, n], n]];
Table[A[n, k], {n, 0, 12}, {k, 0, 10}] // TableForm

def F(n, k): return (n - 1)*fibonacci(k) + fibonacci(k + 1)
def A(n,k): return mod(F(k, n), n)
for n in range(13): print([A(n,k) for k in range(13)])

A(n, 0) = A(n, n) = A002752(n).

Clearly 0 <= A(n, k) < n for all k and n > 0.

A270313 Denominator of Fibonacci(n)/n.

Original entry on oeis.org

1, 2, 3, 4, 1, 3, 7, 8, 9, 2, 11, 1, 13, 14, 3, 16, 17, 9, 19, 4, 21, 22, 23, 1, 1, 26, 27, 28, 29, 3, 31, 32, 33, 34, 7, 1, 37, 38, 39, 8, 41, 21, 43, 44, 9, 46, 47, 1, 49, 2, 51, 52, 53, 27, 11, 8, 57, 58, 59, 1, 61, 62, 63, 64, 13, 33, 67, 68, 69, 14, 71, 1, 73, 74, 3

Offset: 1

Jean-François Alcover and Paul Curtz, Mar 15 2016

a(n) = 1 for n in A023172; a(n) = n for n in A074215. - Robert Israel, Mar 16 2016

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A000045, A023172, A074215, A104714, A127787, A270312 (numerators).

seq(n/igcd(n,combinat:-fibonacci(n)), n=1..100); # Robert Israel, Mar 16 2016

Table[Fibonacci[n]/n, {n, 1, 100}] // Denominator

a(n) = denominator(fibonacci(n)/n); \\ Michel Marcus, Mar 16 2016

a(n) = n/A104714(n). - Robert Israel, Mar 16 2016

A296352 List of numbers k such that the determinant of the Unordered Lights Out matrix UBL_k is nonzero.

Original entry on oeis.org

3, 4, 7, 8, 9, 11, 13, 14, 16, 17, 19, 21, 22, 23, 26, 27, 28, 29, 31, 32, 33, 34, 37, 38, 39, 41, 43, 44, 46, 47, 49, 51, 52, 53, 56, 57, 58, 59, 61, 62, 63, 64, 67, 68, 69, 71, 73, 74, 76, 77, 79, 81, 82, 83, 86, 87, 88, 89, 91, 92, 93, 94, 97, 98, 99, 101, 103

Offset: 1

N. J. A. Sloane, Dec 14 2017

nonn

Martin Kreh, "Lights Out" and Variants, Amer. Math. Month., Vol. 124 (10), Dec. 2017, pp. 937-950.

Cf. A296350, A296351, A296353.

Presumably the similarity to A074215 is merely coincidental.

Select[Range[3, 120], Mod[#, 5] > 0 && Mod[#, 6] > 0 &] (* Amiram Eldar, May 13 2020 *)

Numbers m > 2 such that m is not divisible by 5 nor by 6. - Amiram Eldar, May 13 2020

More terms from Amiram Eldar, May 13 2020

A286308 Numbers m such that gcd(m, F(m)) = 2, where F(m) denotes the m-th Fibonacci number.

Original entry on oeis.org

6, 18, 42, 54, 66, 78, 102, 114, 126, 138, 162, 174, 186, 198, 222, 234, 246, 258, 282, 294, 318, 354, 366, 378, 402, 414, 426, 438, 462, 474, 486, 498, 522, 534, 558, 582, 594, 606, 618, 642, 654, 666, 678, 702, 714, 726, 738, 762, 774, 786, 798, 822, 834, 846, 858

Offset: 1

Michel Marcus, May 05 2017

nonn

From Amiram Eldar, Aug 07 2020: (Start)
All the terms are divisible by 6.
Sanna and Tron proved that for all k > 0 (2 in this sequence) the asymptotic density of the sequence of numbers m such that gcd(m, F(m)) = k exists and is equal to Sum_{i>=1} mu(i)/lcm(k*i, A001177(k*i)), where mu is the Möbius function (A008683) and A001177(m) is the least number j such that F(j) is divisible by m.
The numbers of terms not exceeding 10^k for k = 1, 2, ... are 1, 6, 62, 625, 6248, 62499, 624900, ... (End)

Amiram Eldar, Table of n, a(n) for n = 1..10000
Carlo Sanna and Emanuele Tron, The density of numbers n having a prescribed G.C.D. with the nth Fibonacci number Indagationes Mathematicae, Vol. 29, No. 3 (2018), pp. 972-980, preprint, arXiv:1705.01805 [math.NT], 2017.

Cf. A000045, A001177, A008683, A074215, A104714.

Select[Range[1, 1001], GCD[#, Fibonacci[#]]==2 &] (* Indranil Ghosh, May 06 2017 *)

PARI
```
isok(n) = gcd(n, fibonacci(n)) == 2;
```

from sympy import fibonacci, gcd
[n for n in range(1001) if gcd(n, fibonacci(n)) == 2] # Indranil Ghosh, May 06 2017

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

A352747 Array read by ascending antidiagonals. A(n, k) = F(k, n) mod n for n >= 1 and k >= 0, where F(n, k) = A352744(n, k) are the Fibonacci numbers, A(0, k) = 1 for k >= 0.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

SageMath

Formula

A270313 Denominator of Fibonacci(n)/n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A296352 List of numbers k such that the determinant of the Unordered Lights Out matrix UBL_k is nonzero.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A286308 Numbers m such that gcd(m, F(m)) = 2, where F(m) denotes the m-th Fibonacci number.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Python