cp's OEIS Frontend

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

%I A067824 #99 Nov 25 2024 16:34:47
%S A067824 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,
%T A067824 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,
%U A067824 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
%N A067824 a(1) = 1; for n > 1, a(n) = 1 + Sum_{0 < d < n, d|n} a(d).
%C A067824 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}.
%C A067824 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
%C A067824 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
%C A067824 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.
%C A067824 From _Gus Wiseman_, Aug 20 2020: (Start)
%C A067824 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:
%C A067824   1  2    4      6      8        12
%C A067824      2/1  4/1    6/1    8/1      12/1
%C A067824           4/2    6/2    8/2      12/2
%C A067824           4/2/1  6/3    8/4      12/3
%C A067824                  6/2/1  8/2/1    12/4
%C A067824                  6/3/1  8/4/1    12/6
%C A067824                         8/4/2    12/2/1
%C A067824                         8/4/2/1  12/3/1
%C A067824                                  12/4/1
%C A067824                                  12/4/2
%C A067824                                  12/6/1
%C A067824                                  12/6/2
%C A067824                                  12/6/3
%C A067824                                  12/4/2/1
%C A067824                                  12/6/2/1
%C A067824                                  12/6/3/1
%C A067824 (End)
%C A067824 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
%D A067824 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.
%D A067824 Juhani Karhumaki, Yury Lifshits and Wojciech Rytter, Tiling Periodicity, in Combinatorial Pattern Matching, Lecture Notes in Computer Science, Volume 4580/2007, Springer-Verlag.
%H A067824 Reinhard Zumkeller, <a href="/A067824/b067824.txt">Table = of n, a(n) for n = 1..10000</a>
%H A067824 Olivier Bodini and Eric Rivals, <a href="https://web.archive.org/web/20170810212217/http://www.lirmm.fr/~rivals/PUBLI/FILES/OB-ER-CPM06.pdf">Tiling an Interval of the Discrete Line</a>
%H A067824 Thomas Fink, <a href="https://arxiv.org/abs/1912.07979">Recursively divisible numbers</a>, arXiv:1912.07979 [math.NT], 2019. See Table 1 p. 8.
%H A067824 T. M. A. Fink, <a href="https://arxiv.org/abs/2307.09140">Properties of the recursive divisor function and the number of ordered factorizations</a>, arXiv:2307.09140 [math.NT], 2023.
%H A067824 Michael Greene and Robin Michaels, <a href="https://www.archim.org.uk/eureka/archive/Eureka-54.pdf">One Dimensional Tilings</a>, Eureka (Cambridge) 54 (1996), 4-13.
%H A067824 G. Hajos, <a href="https://doi.org/10.1007/bf02021311">Sur le problème de factorisation des groupes cycliques</a>, Acta Math. Acad. Sci. Hung., 1:189-195, 1950.
%H A067824 J. Karhumaki and Y. Lifshits, <a href="http://logic.pdmi.ras.ru/~yura/en/tiling.pdf">Tiling periodicity</a>.
%H A067824 M. Krasner and B. Ranulac, <a href="https://gallica.bnf.fr/ark:/12148/bpt6k31562/f397.item">Sur une propriété des polynomes de la division du cercle</a>, Comptes Rendus Académie des Sciences Paris, 240:397-399, 1937.
%H A067824 Eric H. Rivals, <a href="http://www.lirmm.fr/~rivals/RESEARCH/TILING/">Tiling</a>
%H A067824 <a href="/index/Eu#epf">Index entries for sequences computed from exponents in factorization of n</a>
%F A067824 a(n) = 2*A074206(n), n>1. - _Vladeta Jovovic_, Jul 03 2005
%F A067824 a(p^k) = 2^k for primes p. - _Reinhard Zumkeller_, Sep 03 2006
%F A067824 a(n) = Sum_{d|n} A002033(d-1) = Sum_{d|n} A074206(d). - _Gus Wiseman_, Jul 13 2018
%F A067824 Dirichlet g.f.: zeta(s) / (2 - zeta(s)). - _Álvar Ibeas_, Dec 30 2018
%F A067824 G.f. A(x) satisfies: A(x) = x/(1 - x) + Sum_{k>=2} A(x^k). - _Ilya Gutkovskiy_, May 18 2019
%e A067824 a(12) = 1 + a(6) + a(4) + a(3) + a(2) + a(1)
%e A067824 = 1+(1+a(3)+a(2)+a(1))+(1+a(2)+a(1))+(1+a(1))+(1+a(1))+(1)
%e A067824 = 1+(1+(1+a(1))+(1+a(1))+1)+(1+(1+a(1))+1)+(1+1)+(1+1)+(1)
%e A067824 = 1+(1+(1+1)+(1+1)+1)+(1+(1+1)+1)+(1+1)+(1+1)+(1)
%e A067824 = 1 + 6 + 4 + 2 + 2 + 1 = 16.
%p A067824 a:= proc(n) option remember;
%p A067824       1+add(a(d), d=numtheory[divisors](n) minus {n})
%p A067824     end:
%p A067824 seq(a(n), n=1..100);  # _Alois P. Heinz_, Apr 17 2021
%t A067824 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 *)
%o A067824 (Haskell)
%o A067824 a067824 n = 1 + sum (map a067824 [d | d <- [1..n-1], mod n d == 0])
%o A067824 -- _Reinhard Zumkeller_, Oct 13 2011
%o A067824 (PARI) 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
%Y A067824 Cf. A000005, A001678, A003238, A107067, A107748, A167865, A316782.
%Y A067824 Cf. A122408 (fixed points).
%Y A067824 Inverse Möbius transform of A074206.
%Y A067824 A001055 counts factorizations.
%Y A067824 A008480 counts maximal chains of divisors starting with n.
%Y A067824 A074206 counts chains of divisors from n to 1.
%Y A067824 A253249 counts nonempty chains of divisors.
%Y A067824 A337070 counts chains of divisors starting with A006939(n).
%Y A067824 A337071 counts chains of divisors starting with n!.
%Y A067824 A337256 counts chains of divisors.
%Y A067824 Cf. A001221, A001222, A002033, A124010, A337074, A337105, A378223, A378225 (Dirichlet inverse).
%K A067824 nonn
%O A067824 1,2
%A A067824 _Reinhard Zumkeller_, Feb 08 2002
%E A067824 Entry revised by _N. J. A. Sloane_, Aug 27 2006