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
Keywords
Examples
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)
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.
Crossrefs
Programs
-
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 *) -
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)<
Chai Wah Wu, Sep 21 2024
Formula
a(n) = Sum_{d|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
Extensions
Ambiguous term a(0) removed by Max Alekseyev, Jan 02 2012
A329142 Numbers whose prime signature is not a necklace.
1, 12, 20, 24, 28, 40, 44, 45, 48, 52, 56, 60, 63, 68, 72, 76, 80, 84, 88, 90, 92, 96, 99, 104, 112, 116, 117, 120, 124, 126, 132, 135, 136, 140, 144, 148, 152, 153, 156, 160, 164, 168, 171, 172, 175, 176, 180, 184, 188, 189, 192, 198, 200, 204, 207, 208, 212
Offset: 1
Keywords
Comments
Examples
The sequence of terms together with their prime signatures begins: 1: () 12: (2,1) 20: (2,1) 24: (3,1) 28: (2,1) 40: (3,1) 44: (2,1) 45: (2,1) 48: (4,1) 52: (2,1) 56: (3,1) 60: (2,1,1) 63: (2,1) 68: (2,1) 72: (3,2) 76: (2,1) 80: (4,1) 84: (2,1,1) 88: (3,1) 90: (1,2,1) 92: (2,1)
Crossrefs
Programs
-
Mathematica
neckQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And]; Select[Range[100],#==1||!neckQ[Last/@FactorInteger[#]]&]
A329141 Number of Lyndon compositions of n that are not weakly increasing.
0, 0, 0, 0, 0, 1, 4, 11, 28, 60, 131, 263, 530, 1029, 2009, 3853, 7414, 14152, 27105, 51755, 99069, 189558, 363468, 697302, 1340220, 2578362, 4968001, 9582682, 18508226, 35784670, 69266825, 134207336, 260290846, 505274108, 981691926
Offset: 1
Keywords
Comments
A Lyndon composition of n is a finite sequence of positive integers summing to n that is lexicographically strictly less than all of its cyclic rotations.
Examples
The a(6) = 1 through a(8) = 11 compositions:
(132) (142) (143)
(1132) (152)
(1213) (1142)
(11212) (1214)
(1232)
(1322)
(11132)
(11213)
(11312)
(12122)
(111212)
Crossrefs
Programs
-
Mathematica
neckQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And]; aperQ[q_]:=Array[RotateRight[q,#1]&,Length[q],1,UnsameQ]; Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],!OrderedQ[#]&&neckQ[#]&&aperQ[#]&]],{n,10}]
Comments