A378223 -id:A378223 - cp's OEIS frontend

A378224 Dirichlet inverse of A378223.

1, -1, -2, -1, -2, 0, -2, -1, 0, 0, -2, 0, -2, 0, 2, -1, -2, 0, -2, 0, 2, 0, -2, 0, 0, 0, 0, 0, -2, 0, -2, -1, 2, 0, 2, 0, -2, 0, 2, 0, -2, 0, -2, 0, 0, 0, -2, 0, 0, 0, 2, 0, -2, 0, 2, 0, 2, 0, -2, 0, -2, 0, 0, -1, 2, 0, -2, 0, 2, 0, -2, 0, -2, 0, 0, 0, 2, 0, -2, 0, 0, 0, -2, 0, 2, 0, 2, 0, -2, 0, 2, 0, 2, 0, 2, 0, -2

Offset: 1

Antti Karttunen, Nov 25 2024

sign

Möbius transform of A378218.

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

Cf. A008683, A345182, A378218, A378223.

Cf. also A378225.

memoA345182 = Map();
A345182(n) = if(n<=2, n%2, my(v); if(mapisdefined(memoA345182,n,&v), v, v = sumdiv(n,d,if(dA345182(d),0)); mapput(memoA345182,n,v); (v)));
A378223(n) = sumdiv(n,d,A345182(d));
memoA378224 = Map();
A378224(n) = if(1==n,1,my(v); if(mapisdefined(memoA378224,n,&v), v, v = -sumdiv(n,d,if(dA378223(n/d)*A378224(d),0)); mapput(memoA378224,n,v); (v)));

a(1) = 1, and for n > 1, a(n) = -Sum_{d|n, dA378223(n/d) * a(d).

a(n) = Sum_{d|n} A008683(n/d)*A378218(d).

A067824 a(1) = 1; for n > 1, a(n) = 1 + Sum_{0 < d < n, d|n} a(d).

Original entry on oeis.org

1, 2, 2, 4, 2, 6, 2, 8, 4, 6, 2, 16, 2, 6, 6, 16, 2, 16, 2, 16, 6, 6, 2, 40, 4, 6, 8, 16, 2, 26, 2, 32, 6, 6, 6, 52, 2, 6, 6, 40, 2, 26, 2, 16, 16, 6, 2, 96, 4, 16, 6, 16, 2, 40, 6, 40, 6, 6, 2, 88, 2, 6, 16, 64, 6, 26, 2, 16, 6, 26, 2, 152, 2, 6, 16, 16, 6, 26, 2, 96, 16, 6, 2, 88, 6, 6, 6, 40, 2, 88, 6, 16, 6, 6, 6, 224, 2, 16, 16, 52

Offset: 1

Reinhard Zumkeller, Feb 08 2002

nonn

By a result of Karhumaki and Lifshits, this is also the number of polynomials p(x) with coefficients in {0,1} that divide x^n-1 and such that (x^n-1)/ {(x-1)p(x)} has all coefficients in {0,1}.
The number of tiles of a discrete interval of length n (an interval of Z). - Eric H. Rivals (rivals(AT)lirmm.fr), Mar 13 2007
Bodini and Rivals proved this is the number of tiles of a discrete interval of length n and also is the number (A107067) of polynomials p(x) with coefficients in {0,1} that divide x^n-1 and such that (x^n-1)/ {(x-1)p(x)} has all coefficients in {0,1} (Bodini, Rivals, 2006). This structure of such tiles is also known as Krasner's factorization (Krasner and Ranulac, 1937). The proof also gives an algorithm to recognize if a set is a tile in optimal time and in this case, to compute the smallest interval it can tile (Bodini, Rivals, 2006). - Eric H. Rivals (rivals(AT)lirmm.fr), Mar 13 2007
Number of lone-child-avoiding rooted achiral (or generalized Bethe) trees with positive integer leaves summing to n, where a rooted tree is lone-child-avoiding if all terminal subtrees have at least two branches, and achiral if all branches directly under any given node are equal. For example, the a(6) = 6 trees are 6, (111111), (222), ((11)(11)(11)), (33), ((111)(111)). - Gus Wiseman, Jul 13 2018. Updated Aug 22 2020.
From Gus Wiseman, Aug 20 2020: (Start)
Also the number of strict chains of divisors starting with n. For example, the a(n) chains for n = 1, 2, 4, 6, 8, 12 are:
  1  2    4      6      8        12
     2/1  4/1    6/1    8/1      12/1
          4/2    6/2    8/2      12/2
          4/2/1  6/3    8/4      12/3
                 6/2/1  8/2/1    12/4
                 6/3/1  8/4/1    12/6
                        8/4/2    12/2/1
                        8/4/2/1  12/3/1
                                 12/4/1
                                 12/4/2
                                 12/6/1
                                 12/6/2
                                 12/6/3
                                 12/4/2/1
                                 12/6/2/1
                                 12/6/3/1
(End)
a(n) is the number of chains including n of the divisor lattice of divisors of n, which is to say, a(n) is the number of (d_1,d_2,...,d_k) such that d_1 < d_2 < ... < d_k = n and d_i divides d_{i+1} for 1 <= i <= k-1. Using this definition, the recurrence a(n) = 1 + Sum_{0 < d < n, d|n} a(d) is evident by enumerating the preceding element of n in the chains. If we count instead the chains whose LCM of members is n, then a(1) would be 2 because the empty chain is included, and we would obtain 2*A074206(n). - Jianing Song, Aug 21 2024

			a(12) = 1 + a(6) + a(4) + a(3) + a(2) + a(1)
= 1+(1+a(3)+a(2)+a(1))+(1+a(2)+a(1))+(1+a(1))+(1+a(1))+(1)
= 1+(1+(1+a(1))+(1+a(1))+1)+(1+(1+a(1))+1)+(1+1)+(1+1)+(1)
= 1+(1+(1+1)+(1+1)+1)+(1+(1+1)+1)+(1+1)+(1+1)+(1)
= 1 + 6 + 4 + 2 + 2 + 1 = 16.

Olivier Bodini and Eric Rivals. Tiling an Interval of the Discrete Line. In M. Lewenstein and G. Valiente, editors, Proc. of the 17th Annual Symposium on Combinatorial Pattern Matching (CPM), volume 4009 of Lecture Notes in Computer Science, pages 117-128. Springer Verlag, 2006.
Juhani Karhumaki, Yury Lifshits and Wojciech Rytter, Tiling Periodicity, in Combinatorial Pattern Matching, Lecture Notes in Computer Science, Volume 4580/2007, Springer-Verlag.

Reinhard Zumkeller, Table = of n, a(n) for n = 1..10000
Olivier Bodini and Eric Rivals, Tiling an Interval of the Discrete Line
Thomas Fink, Recursively divisible numbers, arXiv:1912.07979 [math.NT], 2019. See Table 1 p. 8.
T. M. A. Fink, Properties of the recursive divisor function and the number of ordered factorizations, arXiv:2307.09140 [math.NT], 2023.
Michael Greene and Robin Michaels, One Dimensional Tilings, Eureka (Cambridge) 54 (1996), 4-13.
G. Hajos, Sur le problème de factorisation des groupes cycliques, Acta Math. Acad. Sci. Hung., 1:189-195, 1950.
J. Karhumaki and Y. Lifshits, Tiling periodicity.
M. Krasner and B. Ranulac, Sur une propriété des polynomes de la division du cercle, Comptes Rendus Académie des Sciences Paris, 240:397-399, 1937.
Eric H. Rivals, Tiling
Index entries for sequences computed from exponents in factorization of n

Cf. A000005, A001678, A003238, A107067, A107748, A167865, A316782.
Cf. A122408 (fixed points).
Inverse Möbius transform of A074206.
A001055 counts factorizations.
A008480 counts maximal chains of divisors starting with n.
A074206 counts chains of divisors from n to 1.
A253249 counts nonempty chains of divisors.
A337070 counts chains of divisors starting with A006939(n).
A337071 counts chains of divisors starting with n!.
A337256 counts chains of divisors.
Cf. A001221, A001222, A002033, A124010, A337074, A337105, A378223, A378225 (Dirichlet inverse).

a067824 n = 1 + sum (map a067824 [d | d <- [1..n-1], mod n d == 0])
-- Reinhard Zumkeller, Oct 13 2011

a:= proc(n) option remember;
      1+add(a(d), d=numtheory[divisors](n) minus {n})
    end:
seq(a(n), n=1..100);  # Alois P. Heinz, Apr 17 2021

a[1]=1; a[n_] := a[n] = 1+Sum[If[Mod[n,d]==0, a[d], 0], {d, 1, n-1}]; Array[a,100] (* Jean-François Alcover, Apr 28 2011 *)

A=vector(100);A[1]=1; for(n=2,#A,A[n]=1+sumdiv(n,d,A[d])); A \\ Charles R Greathouse IV, Nov 20 2012

a(n) = 2*A074206(n), n>1. - Vladeta Jovovic, Jul 03 2005
a(p^k) = 2^k for primes p. - Reinhard Zumkeller, Sep 03 2006
a(n) = Sum_{d|n} A002033(d-1) = Sum_{d|n} A074206(d). - Gus Wiseman, Jul 13 2018
Dirichlet g.f.: zeta(s) / (2 - zeta(s)). - Álvar Ibeas, Dec 30 2018
G.f. A(x) satisfies: A(x) = x/(1 - x) + Sum_{k>=2} A(x^k). - Ilya Gutkovskiy, May 18 2019

Entry revised by N. J. A. Sloane, Aug 27 2006

A345182 a(1) = 1, a(2) = 0; a(n) = Sum_{d|n, d < n} a(d).

Original entry on oeis.org

1, 0, 1, 1, 1, 2, 1, 2, 2, 2, 1, 5, 1, 2, 3, 4, 1, 6, 1, 5, 3, 2, 1, 12, 2, 2, 4, 5, 1, 10, 1, 8, 3, 2, 3, 18, 1, 2, 3, 12, 1, 10, 1, 5, 8, 2, 1, 28, 2, 6, 3, 5, 1, 16, 3, 12, 3, 2, 1, 31, 1, 2, 8, 16, 3, 10, 1, 5, 3, 10, 1, 50, 1, 2, 8, 5, 3, 10, 1, 28, 8, 2, 1, 31, 3, 2, 3, 12, 1, 36

Offset: 1

Ilya Gutkovskiy, Jun 10 2021

nonn

From Antti Karttunen, Nov 25 2024: (Start)
a(n) is the number of strict chains of divisors from n to 1 that do not end with 2/1. For example, the a(n) such chains for n = 1, 2, 4, 6, 8, 12, 30 are:
  1 (none) 4/1    6/1     8/1     12/1      30/1
                  6/3/1   8/4/1   12/3/1    30/3/1
                                  12/4/1    30/5/1
                                  12/6/1    30/6/1
                                  12/6/3/1  30/10/1
                                            30/15/1
                                            30/6/3/1
                                            30/10/5/1
                                            30/15/3/1
                                            30/15/5/1
leaving 1, 0, 1, 2, 2, 5, 10 chains out of the 1, 1, 2, 3, 4, 8, 13 chains depicted in the illustration of A074206.
Equally, a(n) is the number of strict chains of divisors from n to 1 where n is not followed by n/2 as the second divisor in the chain, which explains nicely the formula a(n) = A074206(n) - A074206(n/2) when n is even.
(End)

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

Cf. A022825 (partial sums), A074206, A167865, A320224, A345138, A345141, A378218 (Dirichlet inverse), A378223 (inverse Möbius transform).

a[1] = 1; a[2] = 0; a[n_] := a[n] = Sum[If[d < n, a[d], 0], {d, Divisors[n]}]; Table[a[n], {n, 1, 90}]
nmax = 90; A[] = 0; Do[A[x] = x - x^2 + Sum[A[x^k], {k, 2, nmax}] + O[x]^(nmax + 1) // Normal, nmax + 1]; CoefficientList[A[x], x] // Rest

memoA345182 = Map();
A345182(n) = if(n<=2, n%2, my(v); if(mapisdefined(memoA345182,n,&v), v, v = sumdiv(n,d,if(dA345182(d),0)); mapput(memoA345182,n,v); (v))); \\ Antti Karttunen, Nov 22 2024

up_to = 20000;
A345182list(up_to_n) = { my(v=vector(up_to_n)); v[1] = 1; v[2] = 0; for(n=3,up_to_n,v[n] = sumdiv(n,d,(dA345182list(up_to);
A345182(n) = v345182[n]; \\ Antti Karttunen, Nov 25 2024

G.f. A(x) satisfies: A(x) = x - x^2 + A(x^2) + A(x^3) + A(x^4) + ...

a(n) = A074206(n) if n is odd, otherwise a(n) = A074206(n) - A074206(n/2).

cp's OEIS Frontend

A378224 Dirichlet inverse of A378223.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A067824 a(1) = 1; for n > 1, a(n) = 1 + Sum_{0 < d < n, d|n} a(d).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

Extensions

A345182 a(1) = 1, a(2) = 0; a(n) = Sum_{d|n, d < n} a(d).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

A378533 Dirichlet convolution of A323910 and A378542.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula