A113166 - OEIS

%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