|
%I #34 Nov 14 2019 12:56:32
%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, 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
%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)))
%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
|
