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

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A178472 Number of compositions (ordered partitions) of n where the gcd of the part sizes is not 1. 21
 0, 1, 1, 2, 1, 5, 1, 8, 4, 17, 1, 38, 1, 65, 19, 128, 1, 284, 1, 518, 67, 1025, 1, 2168, 16, 4097, 256, 8198, 1, 16907, 1, 32768, 1027, 65537, 79, 133088, 1, 262145, 4099, 524408, 1, 1056731, 1, 2097158, 16636, 4194305, 1, 8421248, 64, 16777712, 65539 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,4 COMMENTS Of course, all part sizes must be greater than 1; that condition alone gives the Fibonacci numbers, which is thus an upper bound. Also the number of periodic compositions of n, where a sequence is periodic if its cyclic rotations are not all different. Also compositions with non-relatively prime run-lengths. - Gus Wiseman, Nov 10 2019 LINKS Vincenzo Librandi, Table of n, a(n) for n = 1..1000 Hunki Baek, Sejeong Bang, Dongseok Kim, Jaeun Lee, A bijection between aperiodic palindromes and connected circulant graphs, arXiv:1412.2426 [math.CO], 2014. See Table 2. FORMULA a(n) = Sum_{d|n & d, <4,2>, <2,4>, <2,2,2>, and <3,3>. From Gus Wiseman, Nov 10 2019: (Start) The a(2) = 1 through a(9) = 4 non-relatively prime compositions:   (2)  (3)  (4)    (5)  (6)      (7)  (8)        (9)             (2,2)       (2,4)         (2,6)      (3,6)                         (3,3)         (4,4)      (6,3)                         (4,2)         (6,2)      (3,3,3)                         (2,2,2)       (2,2,4)                                       (2,4,2)                                       (4,2,2)                                       (2,2,2,2) The a(2) = 1 through a(9) = 4 periodic compositions:   11  111  22    11111  33      1111111  44        333            1111         222              1313      121212                         1212             2222      212121                         2121             3131      111111111                         111111           112112                                          121121                                          211211                                          11111111 The a(2) = 1 through a(9) = 4 compositions with non-relatively prime run-lengths:   11  111  22    11111  33      1111111  44        333            1111         222              1133      111222                         1122             2222      222111                         2211             3311      111111111                         111111           111122                                          112211                                          221111                                          11111111 (End) MAPLE A178472 := n -> (2^n - add(mobius(n/d)*2^d, d in divisors(n)))/2: seq(A178472(n), n=1..51); # Peter Luschny, Jan 21 2018 MATHEMATICA Table[2^(n - 1) - DivisorSum[n, MoebiusMu[n/#]*2^(# - 1) &], {n, 51}] (* Michael De Vlieger, Jan 20 2018 *) PROG (PARI) vector(60, n, 2^(n-1)-sumdiv(n, d, 2^(d-1)*moebius(n/d))) CROSSREFS Cf. A000045, A008683, A011782, A178470. Periodic binary words are A152061. Cf. A000740, A027375, A059966, A121016, A329140, A329145. Sequence in context: A036073 A124227 A064865 * A331888 A178470 A093127 Adjacent sequences:  A178469 A178470 A178471 * A178473 A178474 A178475 KEYWORD nonn AUTHOR Franklin T. Adams-Watters, May 28 2010 EXTENSIONS Ambiguous term a(0) removed by Max Alekseyev, Jan 02 2012 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.

Last modified March 30 17:08 EDT 2020. Contains 333127 sequences. (Running on oeis4.)