|
Search: id:A067824
|
|
|
| A067824 |
|
a(1) = 1; for n > 1, a(n) = 1 + sum{a(d): 0<d<n and d divides n }. |
|
+0
5
|
|
| 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; listen)
|
|
|
OFFSET
|
1,2
|
|
|
COMMENT
|
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 (reinhard.zumkeller(AT)gmail.com), 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
|
|
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.
M. Krasner and B. Ranulak. Sur une propriete des polynomes de la division du cercle. Comptes Rendus Academie des Sciences Paris, 240:397-399, 1937.
|
|
LINKS
|
R. Zumkeller, Table = of n, a(n) for n = 1..10000
Olivier Bodini and Eric Rivals, Tiling an Interval of the Discrete Line
J. Karhumaki and Y. Lifshits, Tiling periodicity.
Eric H. RIVALS, Tiling
|
|
FORMULA
|
a(n) = 2*A074206(n), n>1. - Vladeta Jovovic (vladeta(AT)eunet.rs), Jul 03 2005
|
|
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.
|
|
CROSSREFS
|
Cf. A000005, A107067, A107748.
Cf. A107067.
Sequence in context: A083260 A046523 A071364 this_sequence A107067 A046801 A137502
Adjacent sequences: A067821 A067822 A067823 this_sequence A067825 A067826 A067827
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Reinhard Zumkeller (reinhard.zumkeller(AT)gmail.com), Feb 08 2002
|
|
EXTENSIONS
|
Entry revised by N. J. A. Sloane (njas(AT)research.att.com), Aug 27 2006
|
|
|
Search completed in 0.002 seconds
|
