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

%I #40 Sep 22 2024 02:38:48

%S 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,

%T 4097,256,8198,1,16907,1,32768,1027,65537,79,133088,1,262145,4099,

%U 524408,1,1056731,1,2097158,16636,4194305,1,8421248,64,16777712,65539

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

%C Of course, all part sizes must be greater than 1; that condition alone gives the Fibonacci numbers, which is thus an upper bound.

%C 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

%H Vincenzo Librandi, <a href="/A178472/b178472.txt">Table of n, a(n) for n = 1..1000</a>

%H Hunki Baek, Sejeong Bang, Dongseok Kim, and Jaeun Lee, <a href="http://arxiv.org/abs/1412.2426">A bijection between aperiodic palindromes and connected circulant graphs</a>, arXiv:1412.2426 [math.CO], 2014. See Table 2.

%F a(n) = Sum_{d|n & d<n} 2^(d-1) * (-mu(n/d)).

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

%F a(n) = A152061(n)/2. - _George Beck_, Jan 20 2018

%F a(p) = 1 for p prime. - _Chai Wah Wu_, Sep 21 2024

%e For n=6, we have 5 compositions: <6>, <4,2>, <2,4>, <2,2,2>, and <3,3>.

%e From _Gus Wiseman_, Nov 10 2019: (Start)

%e The a(2) = 1 through a(9) = 4 non-relatively prime compositions:

%e (2) (3) (4) (5) (6) (7) (8) (9)

%e (2,2) (2,4) (2,6) (3,6)

%e (3,3) (4,4) (6,3)

%e (4,2) (6,2) (3,3,3)

%e (2,2,2) (2,2,4)

%e (2,4,2)

%e (4,2,2)

%e (2,2,2,2)

%e The a(2) = 1 through a(9) = 4 periodic compositions:

%e 11 111 22 11111 33 1111111 44 333

%e 1111 222 1313 121212

%e 1212 2222 212121

%e 2121 3131 111111111

%e 111111 112112

%e 121121

%e 211211

%e 11111111

%e The a(2) = 1 through a(9) = 4 compositions with non-relatively prime run-lengths:

%e 11 111 22 11111 33 1111111 44 333

%e 1111 222 1133 111222

%e 1122 2222 222111

%e 2211 3311 111111111

%e 111111 111122

%e 112211

%e 221111

%e 11111111

%e (End)

%p A178472 := n -> (2^n - add(mobius(n/d)*2^d, d in divisors(n)))/2:

%p seq(A178472(n), n=1..51); # _Peter Luschny_, Jan 21 2018

%t Table[2^(n - 1) - DivisorSum[n, MoebiusMu[n/#]*2^(# - 1) &], {n, 51}] (* _Michael De Vlieger_, Jan 20 2018 *)

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

%o (Python)

%o from sympy import mobius, divisors

%o 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

%Y Cf. A000045, A008683, A011782, A178470.

%Y Periodic binary words are A152061.

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

%K nonn

%O 1,4

%A _Franklin T. Adams-Watters_, May 28 2010

%E Ambiguous term a(0) removed by _Max Alekseyev_, Jan 02 2012