A104714 -id:A104714 - cp's OEIS frontend

A285058 Numbers k such that k = A104714(A285057(k)).

1, 2, 5, 7, 10, 12, 13, 17, 24, 25, 26, 29, 34, 35, 36, 37, 38, 43, 47, 48, 49, 50, 53, 55, 58, 59, 60, 65, 67, 72, 73, 74, 85, 89, 91, 96, 97, 103, 106, 108, 109, 110, 113, 118, 120, 125, 127, 130, 137, 139, 144, 145, 146, 149, 156, 157, 158, 163, 168, 169, 170, 173, 175

Offset: 1

Michel Marcus, Apr 09 2017

nonn

The set of distinct values of A104714.
Leonetti & Sanna prove that this sequence is the image of A104714 for n >= 1.
Leonetti & Sanna prove that this sequence has density 0 and a(n) << n log n. - Charles R Greathouse IV, May 08 2017

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
Abhishek Jha and Carlo Sanna, On the greatest common divisor of n and the n-th Fibonacci number, II, arXiv:2207.03521 [math.NT], 2022.
Paolo Leonetti and Carlo Sanna, On the greatest common divisor of n and the nth Fibonacci number, arXiv:1704.00151 [math.NT], 2017. See Lemma 2 on page 2.

Cf. A001177, A104714, A285057.

z[n_]:=Block[{k=1}, While[Mod[Fibonacci[k], n]!=0, k ++]; k]; l[n_]:=LCM[n, z[n]]; g[n_]:= GCD[n, Fibonacci[n]]; Select[Range[200], #==g[l[#]] &] (* Indranil Ghosh, Apr 09 2017 *)

z(n)=my(k = 1); while (fibonacci(k) % n, k++); k; \\ A001177
l(n) = lcm(n, z(n)); \\ A285057
g(n) = gcd(n, fibonacci(n)); \\ A104714
isok(n) = n == g(l(n));

zp(p)=my(k=p+[0,-1,1,1,-1][p%5+1],f=factor(k)); for(i=1,#f[,1], for(j=1,f[i,2], if((Mod([1,1;1,0],p)^(k/f[i,1]))[1,2], break); k/=f[i,1])); k
z(n)=if(n==1,return(1)); my(f=factor(n),v); v=vector(#f~,i, if(f[i,1]>1e14, zp(f[i,1]^f[i,2]), zp(f[i,1])*f[i,1]^(f[i,2]-1))); if(f[1,1]==2&&f[1,2]>1, v[1]=3<Charles R Greathouse IV, May 08 2017

from sympy import fibonacci, gcd, lcm
def z(n):
    k=1
    while fibonacci(k)%n: k+=1
    return k
def l(n): return lcm(n, z(n))
def g(n): return gcd(n, fibonacci(n))
print([n for n in range(1, 201) if n==g(l(n))]) # Indranil Ghosh, Apr 09 2017

A045925 a(n) = n*Fibonacci(n).

Original entry on oeis.org

0, 1, 2, 6, 12, 25, 48, 91, 168, 306, 550, 979, 1728, 3029, 5278, 9150, 15792, 27149, 46512, 79439, 135300, 229866, 389642, 659111, 1112832, 1875625, 3156218, 5303286, 8898708, 14912641, 24961200, 41734339, 69705888, 116311074, 193898158, 322961275, 537492672

Offset: 0

Jeff Burch

Number of levels in all compositions of n+1 with only 1's and 2's.
Apart from first term: row sums of the triangle in A131410. - Reinhard Zumkeller, Oct 07 2012
Number of permutations of length n>0 avoiding the partially ordered pattern (POP) {1>3} of length 4. That is, number of length n permutations having no subsequences of length 4 in which the first element is larger than the third one. - Sergey Kitaev, Dec 08 2020

Jean Paul Van Bendegem, The Heterogeneity of Mathematical Research, a chapter in Perspectives on Interrogative Models of Inquiry, Volume 8 of the series Logic, Argumentation & Reasoning pp 73-94, Springer 2015. See Section 2.1.

Reinhard Zumkeller, Table of n, a(n) for n = 0..1000
Russell Euler, Problem B-670, Elementary Problems and Solutions, The Fibonacci Quarterly, Vol. 28, No. 3 (1990), p. 277; Application of Generating Functions, Solution to Problem B-670 by Russell Jay Hendel, ibid., Vol. 29, No. 3 (1991), p. 278.
Rigoberto Flórez, Robinson Higuita and Alexander Ramírez, The resultant, the discriminant, and the derivative of generalized Fibonacci polynomials, arXiv:1808.01264 [math.NT], 2018.
Alice L. L. Gao and Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, arXiv:1903.08946 [math.CO], 2019.
Alice L. L. Gao and Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, The Electronic Journal of Combinatorics, Vol. 26, No. 3 (2019), Article P3.26.
Silvia Heubach and Toufik Mansour, Counting rises, levels and drops in compositions, arXiv:math/0310197 [math.CO], 2003.
A. G. Shannon, B. Kuloğlu, and E. Özkan, Rhaly terraced sequences their generalizations, properties and applications, Comp. Appl. Math. 44, 226 (2025). See p. 2.
Kai Ting Keshia Yap, David Wehlau and Imed Zaguia, Permutations Avoiding Certain Partially-ordered Patterns, arXiv:2101.12061 [math.CO], 2021.
Index to divisibility sequences.
Index entries for linear recurrences with constant coefficients, signature (2,1,-2,-1).

Partial sums: A014286. Cf. A000045.

Cf. A099920, A023607.

a045925 n = a045925_list !! (n-1)
a045925_list = zipWith (*) [0..] a000045_list
-- Reinhard Zumkeller, Oct 01 2012

[n*Fibonacci(n): n in [0..60]]; // Vincenzo Librandi, Apr 23 2011

a:= n-> n*(<<0|1>, <1|1>>^n)[1,2]:
seq(a(n), n=0..37);  # Alois P. Heinz, May 07 2021

Table[Fibonacci[n]*n, {n, 0, 33}] (* Zerinvary Lajos, Jul 09 2009 *)
LinearRecurrence[{2, 1, -2, -1}, {0, 1, 2, 6}, 34] (* or *)
CoefficientList[ Series[(x + x^3)/(-1 + x + x^2)^2, {x, 0, 35}], x] (* Robert G. Wilson v, Nov 14 2015 *)

Lucas(n)=fibonacci(n-1)+fibonacci(n+1)
a(n)=polcoeff(sum(m=1,n,eulerphi(m)*fibonacci(m)*x^m/(1-Lucas(m)*x^m+(-1)^m*x^(2*m)+x*O(x^n))),n) \\ Paul D. Hanna, Jan 12 2012

a(n)=n*fibonacci(n) \\ Charles R Greathouse IV, Jan 12 2012

concat(0, Vec(x*(1+x^2)/(1-x-x^2)^2 + O(x^100))) \\ Altug Alkan, Oct 28 2015

G.f.: x*(1+x^2)/(1-x-x^2)^2.
G.f.: Sum_{n>=1} phi(n)*Fibonacci(n)*x^n/(1 - Lucas(n)*x^n + (-1)^n*x^(2*n)) = Sum_{n>=1} n*Fibonacci(n)*x^n, where phi(n) = A000010(n) and Lucas(n) = A000204(n). - Paul D. Hanna, Jan 12 2012
a(n) = a(n-1) + a(n-2) + L(n-1). - Gary Detlefs, Dec 29 2012
a(n) = F(n+1) + Sum_{k=1..n-2} F(k)*L(n-k), F = A000045 and L = A000032. - Gary Detlefs, Dec 29 2012
a(n) = F(2*n)/Sum_{k=0..floor(n/2)} binomial(n-k,k)/(n-k). - Gary Detlefs, Jan 19 2013
a(n) = A014965(n) * A104714(n). - Michel Marcus, Oct 24 2013
a(n) = 3*A001629(n+1) - A001629(n+2) + A000045(n-1). - Ralf Stephan, Apr 26 2014
a(n) = 2*n*(F(n-2) + floor(F(n-3)/2)) + (n^3 mod 3*n), F = A000045. - Gary Detlefs, Jun 06 2014
E.g.f.: x*(exp(-x/phi)/phi + exp(x*phi)*phi)/sqrt(5), where phi = (1+sqrt(5))/2. - Vladimir Reshetnikov, Oct 28 2015
This is a divisibility sequence and is generated by  x^4 - 2*x^3 - x^2 + 2*x + 1. - R. K. Guy, Nov 13 2015
a(n) = L'(n, 1), the first derivative of the n-th Lucas polynomial evaluated at 1. - Andrés Ventas, Nov 12 2021
Sum_{n>=0} a(n)/2^n = 10 (Euler, 1990). - Amiram Eldar, Jan 22 2022

Incorrect formula removed by Gary Detlefs, Oct 27 2011

A074215 Numbers m such that m and F(m) are relatively prime, where F(m) denotes the m-th Fibonacci number.

Original entry on oeis.org

1, 2, 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, 57, 58, 59, 61, 62, 63, 64, 67, 68, 69, 71, 73, 74, 76, 77, 79, 81, 82, 83, 86, 87, 88, 89, 92, 93, 94, 97, 98, 99, 101

Offset: 1

Benoit Cloitre, Sep 17 2002

Sanna and Tron proved that a(n) is asymptotic to c*n, for some constant c > 0. - Carlo Sanna, May 11 2017
For k from 1 to 9, a(10^k) is equal to 14, 154, 1553, 15578, 155786, 1557934, 15579574, 155796106, 1557962159. - Giovanni Resta, May 11 2017
The asymptotic density of this sequence is Sum_{k>=1} mu(k)/lcm(k, A001177(k)), where mu is the Möbius function (A008683) (Sanna and Tron, 2018). - Amiram Eldar, Aug 07 2020

Lars Blomberg, 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, A104714.

Select[Range[200], GCD[#, Fibonacci[#]] == 1 &] (* T. D. Noe, Jun 13 2012 *)

isok(n) = gcd(n, fibonacci(n)) == 1; \\ Michel Marcus, May 05 2017

a(n) is probably asymptotic to c*n with c=1.55(8).....

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

A105285 Indices of Lucas 3-step numbers A001644 which have a nontrivial divisor in common with index.

Original entry on oeis.org

6, 15, 18, 21, 35, 39, 44, 45, 54, 55, 57, 78, 80, 84, 90, 93, 96, 117, 120, 123, 132, 133, 135, 140, 147, 154, 156, 162, 171, 174, 195, 201, 210, 213, 234, 235, 240, 245, 247, 249, 252, 259, 264, 273, 275, 279, 286, 288, 290, 291, 295, 299, 312, 318, 323, 327

Offset: 1

Jonathan Vos Post, Apr 25 2005

Extension by T. D. Noe. Wanted: closed-form formula for this as exists for Fibonacci and Lucas numbers. See also A105762 (prime Lucas 3-step numbers).

			gcd(6, A001644(6)) = gcd(6,39) = 3,
gcd(21, A001644(21)) = gcd(21,361109) = 7.

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A001644, A104714, A105762.

m=300; s = LinearRecurrence[{1, 1, 1}, {3, 1, 3}, m+1]; Select[Range[m], !CoprimeQ[#, s[[#+1]]] &] (* Amiram Eldar, Sep 05 2019 *)

gcd(a(n), A001644(a(n))) > 1.

More terms from Amiram Eldar, Sep 05 2019

A105289 Indices of Lucas 5-step numbers A074048 which have a nontrivial divisor in common with index.

Original entry on oeis.org

6, 12, 18, 20, 21, 33, 36, 48, 51, 54, 55, 60, 75, 78, 87, 99, 100, 108, 110, 112, 114, 120, 129, 132, 133, 144, 147, 153, 154, 155, 159, 162, 165, 174, 177, 180, 182, 183, 185, 195, 210, 219, 225, 228, 230, 234, 237, 245, 261, 267, 270, 275, 285, 290, 297, 310

Offset: 1

Jonathan Vos Post, Apr 25 2005

Extension by T. D. Noe. Wanted: closed-form formula for this as exists for Fibonacci and Lucas numbers. See also A105764 (indices of prime Lucas 5-step numbers).

			gcd(6, A074048(6)) = gcd(6,57) = 3,
gcd(20, A074048(20)) = gcd(20,743775) = 5.
gcd(21, A074048(21)) = gcd(21,1462223) = 7.

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A074048, A104714, A105764.

m=300; s = LinearRecurrence[{1, 1, 1, 1, 1}, {5, 1, 3, 7, 15}, m+1]; Select[Range[m], !CoprimeQ[#, s[[#+1]]] &] (* Amiram Eldar, Sep 05 2019 *)

gcd(a(n), A074048(a(n))) > 1.

More terms from Amiram Eldar, Sep 05 2019

A260222 a(n)=gcd(n,F(n-1)), where F(n) is the n-th Fibonacci number.

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 1, 1, 3, 2, 11, 1, 1, 1, 1, 2, 1, 1, 19, 1, 3, 2, 1, 1, 1, 1, 1, 2, 29, 1, 31, 1, 3, 2, 1, 1, 1, 1, 1, 2, 41, 1, 1, 1, 3, 2, 1, 1, 7, 1, 1, 2, 1, 1, 1, 1, 3, 2, 59, 1, 61, 1, 1, 2, 1, 1, 1, 1, 3, 2, 71, 1, 1, 1, 1, 2, 1, 13, 79, 1, 3, 2, 1

Offset: 1

Dmitry Kamenetsky, Jul 19 2015

nonn

This sequence seems good at generating primes, in particular, twin primes. Many primes p are generated when a(p)=p. In fact for n<=10000, a(n)=n occurs 617 times and 609 of these times n is prime. Furthermore, 275 of these times n is also a twin prime.
For n<=1000000 and a(n)=n this sequence generates 39210 primes (49.95% of primes in the range) and produces a prime 99.75% of the time. At the same time it generates 10864 twin primes, which is 66.50% of all twin primes in the range.
A260228 is a similar sequence that produces more primes.
It is well known that p|F(p-(p/5)) for every prime p. So a(p) = p for any prime p == 1,4 (mod 5). - Zhi-Wei Sun, Aug 29 2015

			a(2) = gcd(2,F(1)) = gcd(2,1) = 1.
a(11) = gcd(11,F(10)) = gcd(11,55) = 11.
a(19) = gcd(19,2584) = 19.
a(29) = gcd(29,317811) = 29.

Dmitry Kamenetsky, Table of n, a(n) for n = 1..10000
Z.-H. Sun and Z.-W. Sun, Fibonacci numbers and Fermat's last theorem, Acta Arithmetica 60(4) (1992), 371-388.

Cf. A104714, A106108, A260228.

[Gcd(n,Fibonacci(n-1)): n in [1..90]]; // Vincenzo Librandi, Jul 20 2015

Table[GCD[n, Fibonacci[n-1]], {n, 1, 80}] (* Vincenzo Librandi, Jul 20 2015 *)

a(n)=gcd(n,fibonacci(n-1))
first(m)=vector(m,n,a(n+1)) /* Anders Hellström, Jul 19 2015 */

A083019 Number of common divisors of n and F(n) where F(n) denotes the n-th Fibonacci number.

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 1, 1, 1, 2, 1, 6, 1, 1, 2, 1, 1, 2, 1, 2, 1, 1, 1, 8, 3, 1, 1, 1, 1, 4, 1, 1, 1, 1, 2, 9, 1, 1, 1, 2, 1, 2, 1, 1, 2, 1, 1, 10, 1, 3, 1, 1, 1, 2, 2, 2, 1, 1, 1, 12, 1, 1, 1, 1, 2, 2, 1, 1, 1, 2, 1, 12, 1, 1, 3, 1, 1, 2, 1, 2, 1, 1, 1, 6, 2, 1, 1, 1, 1, 4, 2, 1, 1, 1, 2, 12, 1, 1, 1, 3, 1, 2, 1

Offset: 1

Benoit Cloitre, May 31 2003

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A000005, A000045, A104714.

Table[Length[Intersection[Divisors[n],Divisors[Fibonacci[n]]]],{n,120}] (* Harvey P. Dale, Aug 24 2014 *)
a[n_] := DivisorSigma[0, GCD[n, Fibonacci[n]]]; Array[a, 100] (* Amiram Eldar, Oct 18 2019 *)

a(n) = length(setintersect(divisors(n), divisors(fibonacci(n)))); \\ Michel Marcus, Dec 04 2013

a(n) = A000005(A104714(n)). - Amiram Eldar, Jun 09 2022

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

A299144 a(n) is the least i such that gcd(Fibonacci(i), i+x) > 1 for all x=0..n.

Original entry on oeis.org

5, 10, 18, 30, 30, 30, 30, 180, 180, 180, 180, 840, 840, 1260, 1260, 1260, 1260, 24480, 24480, 63000, 63000, 63000, 63000, 63000, 63000, 63000, 63000, 63000, 63000, 356400, 356400, 356400, 356400, 356400, 356400, 356400, 356400, 5783400, 5783400, 5783400, 5783400, 5783400, 5783400

Offset: 0

Alex Ratushnyak, Feb 03 2018

nonn

			5 is the smallest integer i such that gcd(F(i), i) > 1, because F(5)=5. Therefore a(0)=5.
10 is the smallest integer i such that gcd(F(i), i) > 1 and gcd(F(i), i+1) > 1, because F(10)=55, not coprime to 10 nor 11. Therefore a(1)=10.

Cf. A000045, A104714.

Nest[Function[a, Append[a, SelectFirst[Range[10^5], Function[i, AllTrue[i + Range[0, Length@ a], ! CoprimeQ[Fibonacci@ i, #] &]]]]], {}, 29] (* Michael De Vlieger, Feb 05 2018 *)

isok(k, n) = {for (x=0, n, if (gcd(fibonacci(k), k+x) == 1, return(0));); return(1);}
a(n) = {my(k=1); while (!isok(k,n), k++); k;} \\ Michel Marcus, Feb 05 2018

p0=0
p1=1
def GCD(x,y):
    tmp = y
    y = x % y
    if y==0: return tmp
    return GCD(tmp, y)
n=0
for i in range(1,1000000):
    p0,p1 = p1, p0+p1
    for x in range(1000000):
        if GCD(p0,i+x)==1: break
    for j in range(n, x):
        print(i)
    if x>n: n=x

a(29)-a(36) from Michael De Vlieger, Feb 05 2018

a(37)-a(42) from Jon E. Schoenfield, Apr 24 2018

cp's OEIS Frontend

A285058 Numbers k such that k = A104714(A285057(k)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Python

A045925 a(n) = n*Fibonacci(n).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

PARI

Formula

Extensions

A074215 Numbers m such that m and F(m) are relatively prime, where F(m) denotes the m-th Fibonacci number.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A270313 Denominator of Fibonacci(n)/n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A105285 Indices of Lucas 3-step numbers A001644 which have a nontrivial divisor in common with index.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A105289 Indices of Lucas 5-step numbers A074048 which have a nontrivial divisor in common with index.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A260222 a(n)=gcd(n,F(n-1)), where F(n) is the n-th Fibonacci number.

Views