A329140 -id:A329140 - cp's OEIS frontend

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

Franklin T. Adams-Watters, May 28 2010

nonn

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

			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)

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.

Cf. A000045, A008683, A011782, A178470.
Periodic binary words are A152061.
Cf. A000740, A027375, A059966, A121016, A329140, A329145.

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

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

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

from sympy import mobius, divisors
def A178472(n): return -sum(mobius(n//d)<Chai Wah Wu, Sep 21 2024

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

Ambiguous term a(0) removed by Max Alekseyev, Jan 02 2012

A329131 Numbers whose prime signature is a Lyndon word.

Original entry on oeis.org

2, 3, 4, 5, 7, 8, 9, 11, 13, 16, 17, 18, 19, 23, 25, 27, 29, 31, 32, 37, 41, 43, 47, 49, 50, 53, 54, 59, 61, 64, 67, 71, 73, 75, 79, 81, 83, 89, 97, 98, 101, 103, 107, 108, 109, 113, 121, 125, 127, 128, 131, 137, 139, 147, 149, 150, 151, 157, 162, 163, 167

Offset: 1

Gus Wiseman, Nov 06 2019

nonn

First differs from A133811 in having 50.
A Lyndon word is a finite sequence that is lexicographically strictly less than all of its cyclic rotations.
A number's prime signature is the sequence of positive exponents in its prime factorization.

			The prime signature of 30870 is (1,2,1,3), which is a Lyndon word, so 30870 is in the sequence.
The sequence of terms together with their prime indices begins:
    2: {1}
    3: {2}
    4: {1,1}
    5: {3}
    7: {4}
    8: {1,1,1}
    9: {2,2}
   11: {5}
   13: {6}
   16: {1,1,1,1}
   17: {7}
   18: {1,2,2}
   19: {8}
   23: {9}
   25: {3,3}
   27: {2,2,2}
   29: {10}
   31: {11}
   32: {1,1,1,1,1}

Numbers whose reversed binary expansion is Lyndon are A328596.
Numbers whose prime signature is a necklace are A329138.
Numbers whose prime signature is aperiodic are A329139.
Lyndon compositions are A059966.
Prime signature is A124010.
Cf. A000031, A000740, A000961, A001037, A025487, A027375, A097318, A112798, A118914, A304678, A318731, A329140, A329142.

lynQ[q_]:=Array[Union[{q,RotateRight[q,#]}]=={q,RotateRight[q,#]}&,Length[q]-1,1,And];
Select[Range[2,100],lynQ[Last/@FactorInteger[#]]&]

Intersection of A329138 and A329139.

A329139 Numbers whose prime signature is an aperiodic word.

Original entry on oeis.org

1, 2, 3, 4, 5, 7, 8, 9, 11, 12, 13, 16, 17, 18, 19, 20, 23, 24, 25, 27, 28, 29, 31, 32, 37, 40, 41, 43, 44, 45, 47, 48, 49, 50, 52, 53, 54, 56, 59, 60, 61, 63, 64, 67, 68, 71, 72, 73, 75, 76, 79, 80, 81, 83, 84, 88, 89, 90, 92, 96, 97, 98, 99, 101, 103, 104

Offset: 1

Gus Wiseman, Nov 09 2019

nonn

First differs from A319161 in having 1260 = 2*2 * 3^2 * 5^1 * 7^1. First differs from A325370 in having 420 = 2^2 * 3^1 * 5^1 * 7^1.
A number's prime signature (A124010) is the sequence of positive exponents in its prime factorization.
A sequence is aperiodic if its cyclic rotations are all different.

			The sequence of terms together with their prime signatures begins:
   1: ()
   2: (1)
   3: (1)
   4: (2)
   5: (1)
   7: (1)
   8: (3)
   9: (2)
  11: (1)
  12: (2,1)
  13: (1)
  16: (4)
  17: (1)
  18: (1,2)
  19: (1)
  20: (2,1)
  23: (1)
  24: (3,1)
  25: (2)
  27: (3)

Complement of A329140.
Aperiodic compositions are A000740.
Aperiodic binary words are A027375.
Numbers whose binary expansion is aperiodic are A328594.
Numbers whose prime signature is a Lyndon word are A329131.
Numbers whose prime signature is a necklace are A329138.
Cf. A025487, A097318, A112798, A124010, A178472, A181819, A304678, A329133, A329135, A329136, A329137, A329142.

aperQ[q_]:=Array[RotateRight[q,#1]&,Length[q],1,UnsameQ];
Select[Range[100],aperQ[Last/@FactorInteger[#]]&]

A329138 Numbers whose prime signature is a necklace.

Original entry on oeis.org

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 18, 19, 21, 22, 23, 25, 26, 27, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 41, 42, 43, 46, 47, 49, 50, 51, 53, 54, 55, 57, 58, 59, 61, 62, 64, 65, 66, 67, 69, 70, 71, 73, 74, 75, 77, 78, 79, 81, 82, 83

Offset: 1

Gus Wiseman, Nov 09 2019

nonn

First differs from A304678 in having 1350 = 2^1 * 3^3 * 5^2. First differs from A316529 in having 150 = 2^1 * 3^1 * 5^2.
A number's prime signature (A124010) is the sequence of positive exponents in its prime factorization.
A necklace is a finite sequence that is lexicographically minimal among all of its cyclic rotations.

			The sequence of terms together with their prime signatures begins:
   2: (1)
   3: (1)
   4: (2)
   5: (1)
   6: (1,1)
   7: (1)
   8: (3)
   9: (2)
  10: (1,1)
  11: (1)
  13: (1)
  14: (1,1)
  15: (1,1)
  16: (4)
  17: (1)
  18: (1,2)
  19: (1)
  21: (1,1)
  22: (1,1)

Complement of A329142.
Binary necklaces are A000031.
Necklace compositions are A008965.
Numbers whose reversed binary expansion is a necklace are A328595.
Numbers whose prime signature is a Lyndon word are A329131.
Numbers whose prime signature is aperiodic are A329139.
Cf. A001037, A025487, A056239, A097318, A112798, A118914, A124010, A181819, A304678, A328596, A329140.

neckQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And];
Select[Range[2,100],neckQ[Last/@FactorInteger[#]]&]

A329134 Numbers whose differences of prime indices are a periodic word.

Original entry on oeis.org

8, 16, 27, 30, 32, 64, 81, 105, 110, 125, 128, 180, 210, 238, 243, 256, 273, 343, 385, 450, 506, 512, 625, 627, 729, 806, 935, 1001, 1024, 1080, 1100, 1131, 1155, 1331, 1394, 1495, 1575, 1729, 1786, 1870, 1887, 2048, 2187, 2197, 2310, 2401, 2431, 2451, 2635

Offset: 1

Gus Wiseman, Nov 09 2019

nonn

A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798.

A sequence is periodic if its cyclic rotations are not all different.

			The sequence of terms together with their differences of prime indices begins:
     8: (0,0)
    16: (0,0,0)
    27: (0,0)
    30: (1,1)
    32: (0,0,0,0)
    64: (0,0,0,0,0)
    81: (0,0,0)
   105: (1,1)
   110: (2,2)
   125: (0,0)
   128: (0,0,0,0,0,0)
   180: (0,1,0,1)
   210: (1,1,1)
   238: (3,3)
   243: (0,0,0,0)
   256: (0,0,0,0,0,0,0)
   273: (2,2)
   343: (0,0)
   385: (1,1)
   450: (1,0,1,0)

Complement of A329135.
These are the Heinz numbers of the partitions counted by A329144.
Periodic binary words are A152061.
Periodic compositions are A178472.
Numbers whose binary expansion is periodic are A121016.
Numbers whose prime signature is periodic are A329140.
Cf. A000740, A027375, A056239, A112798, A124010, A328594, A329132, A329139.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
aperQ[q_]:=Array[RotateRight[q,#1]&,Length[q],1,UnsameQ];
Select[Range[10000],!aperQ[Differences[primeMS[#]]]&]

A329135 Numbers whose differences of prime indices are an aperiodic word.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 28, 29, 31, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 65, 66, 67, 68, 69, 70, 71, 72, 73

Offset: 1

Gus Wiseman, Nov 09 2019

nonn

A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798.

A sequence is aperiodic if its cyclic rotations are all different.

			The sequence of terms together with their differences of prime indices begins:
    1: ()
    2: ()
    3: ()
    4: (0)
    5: ()
    6: (1)
    7: ()
    9: (0)
   10: (2)
   11: ()
   12: (0,1)
   13: ()
   14: (3)
   15: (1)
   17: ()
   18: (1,0)
   19: ()
   20: (0,2)
   21: (2)
   22: (4)

Complement of A329134.
These are the Heinz numbers of the partitions counted by A329137.
Aperiodic compositions are A000740.
Aperiodic binary words are A027375.
Numbers whose binary expansion is aperiodic are A328594.
Numbers whose prime signature is aperiodic are A329139.
Cf. A056239, A112798, A124010, A152061, A329133, A329136, A329140.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
aperQ[q_]:=Array[RotateRight[q,#1]&,Length[q],1,UnsameQ];
Select[Range[100],aperQ[Differences[primeMS[#]]]&]

A329142 Numbers whose prime signature is not a necklace.

Original entry on oeis.org

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

Gus Wiseman, Nov 09 2019

nonn

After a(1) = 1, first differs from A112769 in lacking 1350.
A number's prime signature (A124010) is the sequence of positive exponents in its prime factorization.
A necklace is a finite sequence that is lexicographically minimal among all of its cyclic rotations.

			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)

Complement of A329138.
Binary necklaces are A000031.
Non-necklace compositions are A329145.
Numbers whose reversed binary expansion is a necklace are A328595.
Numbers whose prime signature is a Lyndon word are A329131.
Numbers whose prime signature is periodic are A329140.
Cf. A001037, A008965, A025487, A056239, A097318, A112798, A118914, A124010, A181819, A304678, A328596, A329139.

neckQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And];
Select[Range[100],#==1||!neckQ[Last/@FactorInteger[#]]&]

A329132 Numbers whose augmented differences of prime indices are a periodic sequence.

Original entry on oeis.org

4, 8, 15, 16, 32, 55, 64, 90, 105, 119, 128, 225, 253, 256, 403, 512, 540, 550, 697, 893, 935, 1024, 1155, 1350, 1357, 1666, 1943, 2048, 2263, 3025, 3071, 3150, 3240, 3375, 3451, 3927, 3977, 4096, 4429, 5123, 5500, 5566, 6731, 7735, 8083, 8100, 8192, 9089

Offset: 1

Gus Wiseman, Nov 06 2019

nonn

The augmented differences aug(y) of an integer partition y of length k are given by aug(y)i = y_i - y{i + 1} + 1 if i < k and aug(y)_k = y_k. For example, aug(6,5,5,3,3,3) = (2,1,3,1,1,3).
A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798.
A sequence is periodic if its cyclic rotations are not all different.

			The sequence of terms together with their augmented differences of prime indices begins:
     4: (1,1)
     8: (1,1,1)
    15: (2,2)
    16: (1,1,1,1)
    32: (1,1,1,1,1)
    55: (3,3)
    64: (1,1,1,1,1,1)
    90: (2,1,2,1)
   105: (2,2,2)
   119: (4,4)
   128: (1,1,1,1,1,1,1)
   225: (1,2,1,2)
   253: (5,5)
   256: (1,1,1,1,1,1,1,1)
   403: (6,6)
   512: (1,1,1,1,1,1,1,1,1)
   540: (2,1,1,2,1,1)
   550: (3,1,3,1)
   697: (7,7)
   893: (8,8)

Complement of A329133.
These are the Heinz numbers of the partitions counted by A329143.
Periodic binary words are A152061.
Periodic compositions are A178472.
Numbers whose binary expansion is periodic are A121016.
Numbers whose prime signature is periodic are A329140.
Numbers whose differences of prime indices are periodic are A329134.
Cf. A000961, A027375, A056239, A112798, A325356, A325389, A325394, A328594, A329135, A329136, A329139.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
aperQ[q_]:=Array[RotateRight[q,#1]&,Length[q],1,UnsameQ];
aug[y_]:=Table[If[i

A329136 Number of integer partitions of n whose augmented differences are an aperiodic word.

Original entry on oeis.org

1, 1, 1, 2, 4, 5, 10, 14, 19, 28, 40, 53, 75, 99, 131, 172, 226, 294, 380, 488, 617, 787, 996, 1250, 1565, 1953, 2425, 3003, 3705, 4559, 5589, 6836, 8329, 10132, 12292, 14871, 17950, 21629, 25988, 31169, 37306, 44569, 53139, 63247, 75133, 89111, 105515, 124737

Offset: 0

Gus Wiseman, Nov 09 2019

nonn

The augmented differences aug(y) of an integer partition y of length k are given by aug(y)i = y_i - y{i + 1} + 1 if i < k and aug(y)_k = y_k. For example, aug(6,5,5,3,3,3) = (2,1,3,1,1,3).

A sequence is aperiodic if its cyclic rotations are all different.

			The a(1) = 1 through a(7) = 14 partitions:
  (1)  (2)  (3)    (4)      (5)        (6)          (7)
            (2,1)  (2,2)    (4,1)      (3,3)        (4,3)
                   (3,1)    (2,2,1)    (4,2)        (5,2)
                   (2,1,1)  (3,1,1)    (5,1)        (6,1)
                            (2,1,1,1)  (2,2,2)      (3,2,2)
                                       (3,2,1)      (3,3,1)
                                       (4,1,1)      (4,2,1)
                                       (2,2,1,1)    (5,1,1)
                                       (3,1,1,1)    (2,2,2,1)
                                       (2,1,1,1,1)  (3,2,1,1)
                                                    (4,1,1,1)
                                                    (2,2,1,1,1)
                                                    (3,1,1,1,1)
                                                    (2,1,1,1,1,1)
With augmented differences:
  (1)  (2)  (3)    (4)      (5)        (6)          (7)
            (2,1)  (1,2)    (4,1)      (1,3)        (2,3)
                   (3,1)    (1,2,1)    (3,2)        (4,2)
                   (2,1,1)  (3,1,1)    (5,1)        (6,1)
                            (2,1,1,1)  (1,1,2)      (1,3,1)
                                       (2,2,1)      (2,1,2)
                                       (4,1,1)      (3,2,1)
                                       (1,2,1,1)    (5,1,1)
                                       (3,1,1,1)    (1,1,2,1)
                                       (2,1,1,1,1)  (2,2,1,1)
                                                    (4,1,1,1)
                                                    (1,2,1,1,1)
                                                    (3,1,1,1,1)
                                                    (2,1,1,1,1,1)

The Heinz numbers of these partitions are given by A329133.
The periodic version is A329143.
The non-augmented version is A329137.
Aperiodic binary words are A027375.
Aperiodic compositions are A000740.
Numbers whose binary expansion is aperiodic are A328594.
Numbers whose differences of prime indices are aperiodic are A329135.
Numbers whose prime signature is aperiodic are A329139.
Cf. A152061, A325351, A325356, A329132, A329134, A329139, A329140.

aperQ[q_]:=Array[RotateRight[q,#1]&,Length[q],1,UnsameQ];
aug[y_]:=Table[If[i

a(n) + A329143(n) = A000041(n).

A329133 Numbers whose augmented differences of prime indices are an aperiodic sequence.

Original entry on oeis.org

1, 2, 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 56, 57, 58, 59, 60, 61, 62, 63, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74

Offset: 1

Gus Wiseman, Nov 09 2019

nonn

The augmented differences aug(y) of an integer partition y of length k are given by aug(y)i = y_i - y{i + 1} + 1 if i < k and aug(y)_k = y_k. For example, aug(6,5,5,3,3,3) = (2,1,3,1,1,3).
A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798.
A finite sequence is aperiodic if its cyclic rotations are all different.

			The sequence of terms together with their augmented differences of prime indices begins:
    1: ()
    2: (1)
    3: (2)
    5: (3)
    6: (2,1)
    7: (4)
    9: (1,2)
   10: (3,1)
   11: (5)
   12: (2,1,1)
   13: (6)
   14: (4,1)
   17: (7)
   18: (1,2,1)
   19: (8)
   20: (3,1,1)
   21: (3,2)
   22: (5,1)
   23: (9)
   24: (2,1,1,1)

Complement of A329132.
These are the Heinz numbers of the partitions counted by A329136.
Aperiodic binary words are A027375.
Aperiodic compositions are A000740.
Numbers whose binary expansion is aperiodic are A328594.
Numbers whose prime signature is aperiodic are A329139.
Numbers whose differences of prime indices are aperiodic are A329135.
Cf. A056239, A112798, A121016, A124010, A152061, A246029, A325351, A325389, A329134, A329140.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
aperQ[q_]:=Array[RotateRight[q,#1]&,Length[q],1,UnsameQ];
aug[y_]:=Table[If[i

Showing 1-10 of 14 results. Next

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions

A329131 Numbers whose prime signature is a Lyndon word.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A329139 Numbers whose prime signature is an aperiodic word.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A329138 Numbers whose prime signature is a necklace.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A329134 Numbers whose differences of prime indices are a periodic word.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A329135 Numbers whose differences of prime indices are an aperiodic word.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A329142 Numbers whose prime signature is not a necklace.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A329132 Numbers whose augmented differences of prime indices are a periodic sequence.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica