|
|
A113166
|
|
Total number of white pearls remaining in the chest - see Comments.
|
|
3
|
|
|
0, 1, 1, 3, 3, 8, 8, 17, 23, 41, 55, 102, 144, 247, 387, 631, 987, 1636, 2584, 4233, 6787, 11011, 17711, 28794, 46380, 75181, 121441, 196685, 317811, 514712, 832040, 1346921, 2178429, 3525581, 5702937, 9229314, 14930352, 24160419, 39088469, 63250315, 102334155
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,4
|
|
COMMENTS
|
Define a(1) = 0. To calculate a(n):
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).
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.
3. Remove all n-pearled necklaces which are found to have (at least) two adjacent white pearls from the chest.
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.
5. Counting the total number of white pearls left in the chest gives a(n).
|
|
LINKS
|
|
|
FORMULA
|
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).
a(n) = Sum_{d|n} phi(n/d)*Fibonacci(d-1), where phi=A000010. - Maxim Karimov and Vladislav Sulima, Aug 20 2021
|
|
MAPLE
|
with(numtheory): with(combinat):
a:= n-> add(phi(d)*fibonacci(n/d-1), d=divisors(n)):
|
|
MATHEMATICA
|
a[n_] := Sum[EulerPhi[d]*Fibonacci[n/d - 1], {d, Divisors[n]}];
|
|
PROG
|
(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)) ))
(MATLAB)
function [res] = calcA113166(n)
d=divisors(n);
res=0;
for i=1:length(d)
res=res+eulerPhi(n/d(i))*fibonacci(d(i)-1);
end
end
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|