A034748 - OEIS

%I #37 Sep 08 2022 08:44:52

%S 1,2,4,6,9,14,19,30,44,68,99,168,245,402,636,1026,1613,2650,4199,6854,

%T 10996,17820,28679,46596,75065,121650,196516,318250,514257,832826,

%U 1346299,2179374,3524796,5704516,9227571,14933352,24157853,39092386

%N Dirichlet convolution of Fibonacci numbers with phi(n).

%H Vincenzo Librandi, <a href="/A034748/b034748.txt">Table of n, a(n) for n = 1..2000</a> (first 300 terms from Paolo P. Lava)

%F From definition a(n) = Sum_{d|n} F(d)*phi(n/d); also a(n) = Sum_{k=1..n} gcd(F(k), F(k+n)) where F(k) denotes the k-th Fibonacci number. - _Benoit Cloitre_, May 25 2003

%F G.f.: Sum_{k>=1} phi(k) * x^k/(1 - x^k - x^(2*k)). - _Ilya Gutkovskiy_, Jul 23 2019

%F a(n) ~ phi^n / sqrt(5), where phi = A001622 = (1+sqrt(5))/2 is the golden ratio. - _Vaclav Kotesovec_, Jul 23 2019

%F From _Richard L. Ollerton_, May 06 2021: (Start)

%F a(n) = Sum_{k=1..n} F(gcd(n,k)).

%F a(n) = Sum_{k=1..n} F(n/gcd(n,k))*phi(gcd(n,k))/phi(n/gcd(n,k)). (End)

%t Table[Sum[Fibonacci[d] EulerPhi[n/d], {d, Divisors[n]}], {n, 1, 50}] (* _Vincenzo Librandi_, Aug 19 2018 *)

%o (PARI) a(n)=sumdiv(n,d,fibonacci(d)*eulerphi(n/d))

%o (Magma) [&+[Fibonacci(d)*EulerPhi(n div d): d in Divisors(n)]: n in [1..50]]; // _Vincenzo Librandi_, Aug 19 2018

%Y Cf. A000010, A000045, A001622.

%K nonn

%O 1,2

%A _Erich Friedman_