cp's OEIS Frontend

A113166 a(n) = Sum_{d|n} A000010(n/d) * A000045(d-1).

%I A113166 #78 Mar 11 2025 04:28:27
%S A113166 0,1,1,3,3,8,8,17,23,41,55,102,144,247,387,631,987,1636,2584,4233,
%T A113166 6787,11011,17711,28794,46380,75181,121441,196685,317811,514712,
%U A113166 832040,1346921,2178429,3525581,5702937,9229314,14930352,24160419,39088469,63250315,102334155
%N A113166 a(n) = Sum_{d|n} A000010(n/d) * A000045(d-1).
%C A113166 Previous name was: Total number of white pearls remaining in the chest - see Comments.
%C A113166 Define a(1) = 0. To calculate a(n):
%C A113166 1. Expand (A + B)^n into 2^n words of length n consisting of letters A and B (i.e., use of the distributive and associative laws of multiplication but assume A and B do not commute).
%C A113166 2. To each of the 2^n words, associate a free binary necklace consisting of n "black and white pearls". Figuratively, all 2^n necklaces can be placed inside a treasure chest.
%C A113166 3. Remove all n-pearled necklaces which are found to have (at least) two adjacent white pearls from the chest.
%C A113166 4. If two necklaces are found to be equivalent, remove one of them from the chest. Continue until no two equivalent necklaces can be found in the chest.
%C A113166 5. Counting the total number of white pearls left in the chest gives a(n).
%H A113166 Alois P. Heinz, <a href="/A113166/b113166.txt">Table of n, a(n) for n = 1..2000</a> (first 50 terms from Max Alekseyev)
%H A113166 Creighton Dement and Max Alekseyev, <a href="/A113166/a113166.txt">Notes on A113166</a>
%F A113166 a(n) = Sum_{k=1..floor(n/2)} (k/(n-k))*Sum_{j=1..gcd(n,k)} binomial((n-k)*gcd(n,k,j)/gcd(n,k), k*gcd(n,k,j)/gcd(n,k)) (Alekseyev).
%F A113166 a(p) = Fibonacci(p-1) for all primes p. (_Creighton Dement_ and _Antti Karttunen_, proved by _Max Alekseyev_).
%F A113166 a(n) = Sum_{d|n} phi(n/d)*Fibonacci(d-1), where phi=A000010. - _Maxim Karimov_ and Vladislav Sulima, Aug 20 2021
%p A113166 with(numtheory): with(combinat):
%p A113166 a:= n-> add(phi(d)*fibonacci(n/d-1), d=divisors(n)):
%p A113166 seq(a(n), n=1..50);  # _Alois P. Heinz_, Aug 21 2021
%t A113166 a[n_] := Sum[EulerPhi[d]*Fibonacci[n/d - 1], {d, Divisors[n]}];
%t A113166 Array[a, 50] (* _Jean-François Alcover_, Jan 03 2022 *)
%o A113166 (PARI) A113166(n) = sum(k=1,n\2, k/(n-k) * sum(j=1,gcd(n,k), binomial((n-k)*gcd([n,k,j])/gcd(n,k),k*gcd([n,k,j])/gcd(n,k)) ))
%o A113166 (MATLAB)
%o A113166 function [res] = calcA113166(n)
%o A113166     d=divisors(n);
%o A113166     res=0;
%o A113166     for i=1:length(d)
%o A113166         res=res+eulerPhi(n/d(i))*fibonacci(d(i)-1);
%o A113166     end
%o A113166 end
%o A113166 % _Maxim Karimov_, Aug 21 2021
%Y A113166 Cf. A000010, A034748, A006206, A000358, A000045, A000204, A000010.
%K A113166 nonn
%O A113166 1,4
%A A113166 _Creighton Dement_, Jan 05 2006; Jan 08 2006; Jul 29 2006
%E A113166 More terms from _Max Alekseyev_, Jun 20 2006
%E A113166 Better name using given formula from _Joerg Arndt_, Mar 11 2025