|
%I #74 Mar 11 2024 04:37:45
%S 0,1,1,3,3,8,8,17,23,41,55,102,144,247,387,631,987,1636,2584,4233,
%T 6787,11011,17711,28794,46380,75181,121441,196685,317811,514712,
%U 832040,1346921,2178429,3525581,5702937,9229314,14930352,24160419,39088469,63250315,102334155
%N Total number of white pearls remaining in the chest - see Comments.
%C Define a(1) = 0. To calculate a(n):
%C 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 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 3. Remove all n-pearled necklaces which are found to have (at least) two adjacent white pearls from the chest.
%C 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 5. Counting the total number of white pearls left in the chest gives a(n).
%H 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 Creighton Dement and Max Alekseyev, <a href="/A113166/a113166.txt">Notes on A113166</a>
%F 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 a(p) = Fibonacci(p-1) for all primes p. (_Creighton Dement_ and _Antti Karttunen_, proved by _Max Alekseyev_).
%F a(n) = Sum_{d|n} phi(n/d)*Fibonacci(d-1), where phi=A000010. - _Maxim Karimov_ and Vladislav Sulima, Aug 20 2021
%p with(numtheory): with(combinat):
%p a:= n-> add(phi(d)*fibonacci(n/d-1), d=divisors(n)):
%p seq(a(n), n=1..50); # _Alois P. Heinz_, Aug 21 2021
%t a[n_] := Sum[EulerPhi[d]*Fibonacci[n/d - 1], {d, Divisors[n]}];
%t Array[a, 50] (* _Jean-François Alcover_, Jan 03 2022 *)
%o (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 (MATLAB)
%o function [res] = calcA113166(n)
%o d=divisors(n);
%o res=0;
%o for i=1:length(d)
%o res=res+eulerPhi(n/d(i))*fibonacci(d(i)-1);
%o end
%o end
%o % _Maxim Karimov_, Aug 21 2021
%Y Cf. A000010, A034748, A006206, A000358, A000045, A000204, A000010.
%K nonn
%O 1,4
%A _Creighton Dement_, Jan 05 2006; Jan 08 2006; Jul 29 2006
%E More terms from _Max Alekseyev_, Jun 20 2006
|
