A034748 -id:A034748 - cp's OEIS frontend

A349565 Dirichlet convolution of Fibonacci numbers with A349452 (Dirichlet inverse of A011782, 2^(n-1)).

1, -1, -2, -3, -11, -16, -51, -93, -214, -419, -935, -1812, -3863, -7649, -15698, -31443, -63939, -127676, -257963, -516037, -1037298, -2076547, -4165647, -8335716, -16702015, -33421217, -66911078, -133875827, -267921227, -535987784, -1072395555, -2145208557, -4291436930, -8584038291, -17170640199, -34344407256

Offset: 1

Antti Karttunen, Nov 22 2021

sign

Dirichlet convolution of this sequence with A034738 produces A034748.

Antti Karttunen, Table of n, a(n) for n = 1..1001

Cf. A000045, A011782, A349452, A349566 (Dirichlet inverse).

Cf. also A034738, A034748, A349563, A349567, A349569.

s[1] = 1; s[n_] := s[n] = -DivisorSum[n, s[#] * 2^(n/# - 1) &, # < n &]; a[n_] := DivisorSum[n, Fibonacci[#] * s[n/#] &]; Array[a, 36] (* Amiram Eldar, Nov 22 2021 *)

A011782(n) = (2^(n-1));
memoA349452 = Map();
A349452(n) = if(1==n,1,my(v); if(mapisdefined(memoA349452,n,&v), v, v = -sumdiv(n,d,if(dA011782(n/d)*A349452(d),0)); mapput(memoA349452,n,v); (v)));
A349565(n) = sumdiv(n,d,fibonacci(d)*A349452(n/d));

a(n) = Sum_{d|n} A000045(d) * A349452(n/d).

A349566 Dirichlet convolution of A011782 (2^(n-1)) with A349451 (Dirichlet inverse of Fibonacci numbers).

Original entry on oeis.org

1, 1, 2, 4, 11, 20, 51, 100, 218, 441, 935, 1862, 3863, 7751, 15742, 31648, 63939, 128180, 257963, 516974, 1037502, 2078417, 4165647, 8339900, 16702136, 33428943, 66911942, 133891584, 267921227, 536021340, 1072395555, 2145272320, 4291440670, 8584166169, 17170641321, 34344672290, 68695318919, 137399603159, 274814652766

Offset: 1

Antti Karttunen, Nov 22 2021

nonn

Dirichlet convolution of this sequence with A034748 produces A034738.

Antti Karttunen, Table of n, a(n) for n = 1..1001

Cf. A000045, A011782, A349451, A349565 (Dirichlet inverse).

s[1] = 1; s[n_] := s[n] = -DivisorSum[n, s[#] * Fibonacci[n/#] &, # < n &]; a[n_] := DivisorSum[n, 2^(# - 1) * s[n/#] &]; Array[a, 40] (* Amiram Eldar, Nov 22 2021 *)

memoA349451 = Map();
A349451(n) = if(1==n,1,my(v); if(mapisdefined(memoA349451,n,&v), v, v = -sumdiv(n,d,if(dA349451(d),0)); mapput(memoA349451,n,v); (v)));
A349566(n) = sumdiv(n,d,(2^(d-1)) * A349451(n/d));

a(n) = Sum_{d|n} 2^(d-1) * A349451(n/d).

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

Original entry on oeis.org

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

Offset: 1

Creighton Dement, Jan 05 2006; Jan 08 2006; Jul 29 2006

nonn

Previous name was: Total number of white pearls remaining in the chest - see Comments.
Define a(1) = 0. To calculate a(n):
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).
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.
Remove all n-pearled necklaces which are found to have (at least) two adjacent white pearls from the chest.
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.
Counting the total number of white pearls left in the chest gives a(n).

Alois P. Heinz, Table of n, a(n) for n = 1..2000 (first 50 terms from Max Alekseyev)
Creighton Dement and Max Alekseyev, Notes on A113166

Cf. A000010, A034748, A006206, A000358, A000045, A000204, A000010.

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
% Maxim Karimov, Aug 21 2021

with(numtheory): with(combinat):
a:= n-> add(phi(d)*fibonacci(n/d-1), d=divisors(n)):
seq(a(n), n=1..50);  # Alois P. Heinz, Aug 21 2021

a[n_] := Sum[EulerPhi[d]*Fibonacci[n/d - 1], {d, Divisors[n]}];
Array[a, 50] (* Jean-François Alcover, Jan 03 2022 *)

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)) ))

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(p) = Fibonacci(p-1) for all primes p. (Creighton Dement and Antti Karttunen, proved by Max Alekseyev).
a(n) = Sum_{d|n} phi(n/d)*Fibonacci(d-1), where phi=A000010. - Maxim Karimov and Vladislav Sulima, Aug 20 2021

More terms from Max Alekseyev, Jun 20 2006

Better name using given formula from Joerg Arndt, Mar 11 2025

A347351 Triangle read by rows: T(n,k) is the number of links of length k in a set of all necklaces A000358 of length n, 1 <= k <= n.

Original entry on oeis.org

1, 2, 1, 3, 0, 1, 4, 2, 0, 1, 5, 1, 1, 0, 1, 6, 4, 2, 1, 0, 1, 7, 3, 2, 1, 1, 0, 1, 8, 8, 3, 3, 1, 1, 0, 1, 9, 8, 7, 3, 2, 1, 1, 0, 1, 10, 18, 9, 5, 4, 2, 1, 1, 0, 1, 11, 21, 13, 8, 5, 3, 2, 1, 1, 0, 1, 12, 40, 24, 16, 8, 6, 3, 2, 1, 1, 0, 1, 13, 55, 34, 21, 13, 8, 5, 3, 2, 1, 1, 0, 1

Offset: 0

Maxim Karimov and Vladislav Sulima, Aug 28 2021

Definitions:
1. A link is any 0 in any necklace from A000358 and all 1s following this 0 in this necklace to right until another 0 is encountered.
2. Length of the link is the number of elements in the link.
Sum of all elements n-row is Fibonacci(n-1)+n iff n=1 or n=p (follows from the identity for the sum of the Fibonacci numbers and the formula for the triangle T(n,k)).

			For k > 0:
   n\k |  1   2   3   4   5   6   7   8   9  10  ...
  -----+---------------------------------------
   1   |  1
   2   |  2   1
   3   |  3   0   1
   4   |  4   2   0   1
   5   |  5   1   1   0   1
   6   |  6   4   2   1   0   1
   7   |  7   3   2   1   1   0   1
   8   |  8   8   3   3   1   1   0   1
   9   |  9   8   7   3   2   1   1   0   1
  10   | 10  18   9   5   4   2   1   1   0   1
  ...
If we continue the calculation for nonpositive k, we get a table in which each row is a Fibonacci sequence, in which term(0) = A113166, term(1) = A034748.
For k <= 0:
   n\k |  0   -1   -2   -3   -4   -5   -6   -7   -8   -9 ...
  -----+------------------------------------------------
   1   |  0    1    1    2    3    5    8   13   21   34 ... A000045
   2   |  1    2    3    5    8   13   21   34   55   89 ... A000045
   3   |  1    4    5    9   14   23   37   60   97  157 ... A000285
   4   |  3    6    9   15   24   39   63  102  165  267 ... A022086
   5   |  3    9   12   21   33   54   87  141  228  369 ... A022379
   6   |  8   14   22   36   58   94  152  246  398  644 ... A022112
   7   |  8   19   27   46   73  119  192  311  503  814 ... A206420
   8   | 17   30   47   77  124  201  325  526  851 1377 ... A022132
   9   | 23   44   67  111  178  289  467  756 1223 1979 ... A294116
  10   | 41   68  109  177  286  463  749 1212 1961 3173 ... A022103
  ...

Cf. A000010, A000027, A000045, A000358, A113166, A034748.

function [res] = calcLinks(n,k)
if k==1
    res=n;
else
    d=divisors(n);
    res=0;
    for i=1:length(d)
        if d (i) >= k
            res=res+eulerPhi(n/d(i))*fiboExt(d(i)-k-1);
        end
    end
end
function [s] = fiboExt(m) % extended fibonacci function (including negative arguments)
m=sym(m); % for large fibonacci numbers
if m>=0 || mod(m,2)==1
    s=fibonacci(abs(m));
else
    s=fibonacci(abs(m))*(-1);
end

T(n, k) = if (k==1, n, sumdiv(n, d, if (d>=k, eulerphi(n/d)*fibonacci(d-k-1)))); \\ Michel Marcus, Aug 29 2021

If k=1, T(n,k)=n, otherwise T(n,k) = Sum_{d>=k, d|n} Phi(n/d)*Fibonacci(d-k-1), where Phi=A000010.

cp's OEIS Frontend

A349565 Dirichlet convolution of Fibonacci numbers with A349452 (Dirichlet inverse of A011782, 2^(n-1)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A349566 Dirichlet convolution of A011782 (2^(n-1)) with A349451 (Dirichlet inverse of Fibonacci numbers).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

MATLAB

Maple

Mathematica

PARI

Formula

Extensions

A347351 Triangle read by rows: T(n,k) is the number of links of length k in a set of all necklaces A000358 of length n, 1 <= k <= n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

MATLAB

PARI

Formula