A178472 Number of compositions (ordered partitions) of n where the gcd of the part sizes is not 1.

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

Offset: 1

Author

Franklin T. Adams-Watters, May 28 2010

Keywords

• nonn

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

Examples

			For n=6, we have 5 compositions: <6>, <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)
		

Links

• Vincenzo Librandi, Table of n, a(n) for n = 1..1000
• Hunki Baek, Sejeong Bang, Dongseok Kim, and Jaeun Lee, A bijection between aperiodic palindromes and connected circulant graphs, arXiv:1412.2426 [math.CO], 2014. See Table 2.

Crossrefs

Cf. A000045, A008683, A011782, A178470.

Periodic binary words are A152061.

Cf. A000740, A027375, A059966, A121016, A329140, A329145.

Programs

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

PARI

vector(60,n,2^(n-1)-sumdiv(n,d,2^(d-1)*moebius(n/d)))

Python

from sympy import mobius, divisors
def A178472(n): return -sum(mobius(n//d)<Chai Wah Wu, Sep 21 2024

Formula

a(n) = Sum_{d|n & d

a(n) = 2^(n-1) - A000740(n).

a(n) = A152061(n)/2. - George Beck, Jan 20 2018

a(p) = 1 for p prime. - Chai Wah Wu, Sep 21 2024

Extensions

Ambiguous term a(0) removed by Max Alekseyev, Jan 02 2012

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.