login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons 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. 25
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

Vincenzo Librandi, Table of n, a(n) for n = 1..1000

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

Cf. A000045, A008683, A011782, A178470.

Periodic binary words are A152061.

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

Sequence in context: A036073 A124227 A064865 * A331888 A178470 A093127

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 13 06:45 EDT 2020. Contains 335675 sequences. (Running on oeis4.)