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,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, and 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<n} 2^(d-1) * (-mu(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

Example

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)

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)))
(Python)
from sympy import mobius, divisors
def A178472(n): return -sum(mobius(n//d)<<d-1 for d in divisors(n, generator=True) if d<n) # Chai Wah Wu, Sep 21 2024

Crossrefs

Cf. A000045, A008683, A011782, A178470.

Periodic binary words are A152061.

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

Sequence in context: A036073 A124227 A064865 * A337667 A331888 A178470

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