login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
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. 41
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
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<n} 2^(d-1) * (-mu(n/d)).
a(n) = 2^(n-1) - A000740(n).
a(n) = A152061(n)/2. - George Beck, Jan 20 2018
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)))
CROSSREFS
Periodic binary words are A152061.
Sequence in context: A036073 A124227 A064865 * A337667 A331888 A178470
KEYWORD
nonn
AUTHOR
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 | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 18 22:56 EDT 2024. Contains 370952 sequences. (Running on oeis4.)