login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo

Please make a donation to keep the OEIS running. We are now in our 56th year. In the past year we added 10000 new sequences and reached almost 9000 citations (which often say "discovered thanks to the OEIS").
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A067824 a(1) = 1; for n > 1, a(n) = 1 + Sum_{0 < d < n, d|n} a(d). 41
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

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}.

a(p^k) = 2^k for primes p; a(n) = n iff n = A122408(k) for some k. - Reinhard Zumkeller, Sep 03 2006

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

REFERENCES

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.

G. Hajos. Sur le probleme de factorisation des groupes cycliques. Acta Math. Acad. Sci. Hung., 1:189-195, 1950.

Juhani Karhumaki, Yury Lifshits and Wojciech Rytter, Tiling Periodicity, in Combinatorial Pattern Matching, Lecture Notes in Computer Science, Volume 4580/2007, Springer-Verlag.

LINKS

R. 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.

J. Karhumaki and Y. Lifshits, Tiling periodicity.

M. Krasner and B. Ranulak, Sur une propriété des polynômes 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

FORMULA

a(n) = 2*A074206(n), n>1. - Vladeta Jovovic, Jul 03 2005

a(n) = Sum_{d|n} A002033(d - 1). - 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

EXAMPLE

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.

MATHEMATICA

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

PROG

(Haskell)

a067824 n = 1 + sum (map a067824 [d | d <- [1..n-1], mod n d == 0])

-- Reinhard Zumkeller, Oct 13 2011

(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

CROSSREFS

Cf. A000005, A001678, A003238, A107067, A107748, A167865, A316782.

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.

Sequence in context: A071364 A278237 A328707 * A107067 A331580 A320389

Adjacent sequences:  A067821 A067822 A067823 * A067825 A067826 A067827

KEYWORD

nonn

AUTHOR

Reinhard Zumkeller, Feb 08 2002

EXTENSIONS

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 2 20:22 EST 2020. Contains 338891 sequences. (Running on oeis4.)