A178472 -id:A178472 - cp's OEIS frontend

A000740 Number of 2n-bead balanced binary necklaces of fundamental period 2n, equivalent to reversed complement; also Dirichlet convolution of b_n=2^(n-1) with mu(n); also number of components of Mandelbrot set corresponding to Julia sets with an attractive n-cycle.

1, 1, 3, 6, 15, 27, 63, 120, 252, 495, 1023, 2010, 4095, 8127, 16365, 32640, 65535, 130788, 262143, 523770, 1048509, 2096127, 4194303, 8386440, 16777200, 33550335, 67108608, 134209530, 268435455, 536854005, 1073741823, 2147450880

Offset: 1

N. J. A. Sloane

Also number of compositions of n into relatively prime parts (that is, the gcd of all the parts is 1). Also number of subsets of {1,2,..,n} containing n and consisting of relatively prime numbers. - Vladeta Jovovic, Aug 13 2003
Also number of perfect parity patterns that have exactly n columns (see A118141). - Don Knuth, May 11 2006
a(n) is odd if and only if n is squarefree (Tim Keller). - Emeric Deutsch, Apr 27 2007
a(n) is a multiple of 3 for all n>=3 (see Problem 11161 link). - Emeric Deutsch, Aug 13 2008
Row sums of triangle A143424. - Gary W. Adamson, Aug 14 2008
a(n) is the number of monic irreducible polynomials with nonzero constant coefficient in GF(2)[x] of degree n. - Michel Marcus, Oct 30 2016
a(n) is the number of aperiodic compositions of n, the number of compositions of n with relatively prime parts, and the number of compositions of n with relatively prime run-lengths. - Gus Wiseman, Dec 21 2017

			For n=4, there are 6 compositions of n into coprime parts: <3,1>, <2,1,1>, <1,3>, <1,2,1>, <1,1,2>, and <1,1,1,1>.
From _Gus Wiseman_, Dec 19 2017: (Start)
The a(6) = 27 aperiodic compositions are:
  (11112), (11121), (11211), (12111), (21111),
  (1113), (1122), (1131), (1221), (1311), (2112), (2211), (3111),
  (114), (123), (132), (141), (213), (231), (312), (321), (411),
  (15), (24), (42), (51),
  (6).
The a(6) = 27 compositions into relatively prime parts are:
  (111111),
  (11112), (11121), (11211), (12111), (21111),
  (1113), (1122), (1131), (1212), (1221), (1311), (2112), (2121), (2211), (3111),
  (114), (123), (132), (141), (213), (231), (312), (321), (411),
  (15), (51).
The a(6) = 27 compositions with relatively prime run-lengths are:
  (11112), (11121), (11211), (12111), (21111),
  (1113), (1131), (1212), (1221), (1311), (2112), (2121), (3111),
  (114), (123), (132), (141), (213), (231), (312), (321), (411),
  (15), (24), (42), (51),
  (6).
(End)

H. O. Peitgen and P. H. Richter, The Beauty of Fractals, Springer-Verlag; contribution by A. Douady, p. 165.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Seiichi Manyama, Table of n, a(n) for n = 1..3322 (terms 1..300 from T. D. Noe)
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.
Donald Knuth, Robin Chapman and Reiner Martin, Problem 11243, Perfect Parity Patterns, Am. Math. Monthly 115 (7) (2008) p 668, function c(n).
Emeric Deutsch and Lafayette College Problem Group, Problem 11161: Compositions without Common Factors, American Mathematical Monthly, vol. 114, No. 4, 2007, p. 363.
H. W. Gould, Binomial coefficients, the bracket function and compositions with relatively prime summands, Fib. Quart. 2(4) (1964), 241-260.
J. E. Iglesias, A formula for the number of closest packings of equal spheres having a given repeat period, Z. Krist. 155 (1981) 121-127, Table 2.
Wolfdieter Lang, Cantor's List of Real Algebraic Numbers of Heights 1 to 7, arXiv:2307.10645 [math.NT], 2023.
Nicolae Mihalache and Francois Vigneron, Factorization of the quadratic Misiurewicz-Thurston polynomials, arXiv:2506.17662 [math.DS], 2025. See p. 8.
Robert Munafo, Enumeration of Period-N Mu-Atoms
Jeffrey Shallit and N. J. A. Sloane, Correspondence 1974-1975
François Vigneron and Nicolae Mihalache, How to split a tera-polynomial, arXiv:2402.06083 [math.NA], 2024.
Index entries for sequences related to Lyndon words

Cf. A000837, A003239, A008683, A008965, A022553, A034738, A035928, A038199, A051168, A054525, A056267, A059966, A143424, A167606, A178472, A216954, A228369, A294859, A296302.
Equals A027375/2.
See A056278 for a variant.
First differences of A085945.
Column k=2 of A143325.
Row sums of A101391.

with(numtheory): a[1]:=1: a[2]:=1: for n from 3 to 32 do div:=divisors(n): a[n]:=2^(n-1)-sum(a[n/div[j]],j=2..tau(n)) od: seq(a[n],n=1..32); # Emeric Deutsch, Apr 27 2007
with(numtheory); A000740:=n-> add(mobius(n/d)*2^(d-1), d in divisors(n)); # N. J. A. Sloane, Oct 18 2012

a[n_] := Sum[ MoebiusMu[n/d]*2^(d - 1), {d, Divisors[n]}]; Table[a[n], {n, 1, 32}] (* Jean-François Alcover, Feb 03 2012, after PARI *)

a(n) = sumdiv(n,d,moebius(n/d)*2^(d-1))

from sympy import mobius, divisors
def a(n): return sum([mobius(n // d) * 2**(d - 1) for d in divisors(n)])
[a(n) for n in range(1, 101)]  # Indranil Ghosh, Jun 28 2017

a(n) = Sum_{d|n} mu(n/d)*2^(d-1), Mobius transform of A011782. Furthermore, Sum_{d|n} a(d) = 2^(n-1).
a(n) = A027375(n)/2 = A038199(n)/2.
a(n) = Sum_{k=0..n} A051168(n,k)*k. - Max Alekseyev, Apr 09 2013
Recurrence relation: a(n) = 2^(n-1) - Sum_{d|n,d>1} a(n/d). (Lafayette College Problem Group; see the Maple program and Iglesias eq (6)). - Emeric Deutsch, Apr 27 2007
G.f.: Sum_{k>=1} mu(k)*x^k/(1 - 2*x^k). - Ilya Gutkovskiy, Oct 24 2018
G.f. satisfies Sum_{n>=1} A( (x/(1 + 2*x))^n ) = x. - Paul D. Hanna, Apr 02 2025

Connection with Mandelbrot set discovered by Warren D. Smith and proved by Robert Munafo, Feb 06 2000

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

A101268 Number of compositions of n into pairwise relatively prime parts.

Original entry on oeis.org

1, 1, 2, 4, 7, 13, 22, 38, 63, 101, 160, 254, 403, 635, 984, 1492, 2225, 3281, 4814, 7044, 10271, 14889, 21416, 30586, 43401, 61205, 85748, 119296, 164835, 226423, 309664, 422302, 574827, 781237, 1060182, 1436368, 1942589, 2622079, 3531152, 4742316, 6348411

Offset: 0

Vladeta Jovovic, Dec 18 2004

nonn

Here a singleton is always considered pairwise relatively prime. Compare to A337462. - Gus Wiseman, Oct 18 2020

			From _Gus Wiseman_, Oct 18 2020: (Start)
The a(1) = 1 through a(5) = 13 compositions:
  (1)  (2)   (3)    (4)     (5)
       (11)  (12)   (13)    (14)
             (21)   (31)    (23)
             (111)  (112)   (32)
                    (121)   (41)
                    (211)   (113)
                    (1111)  (131)
                            (311)
                            (1112)
                            (1121)
                            (1211)
                            (2111)
                            (11111)
(End)

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..500 (terms 0..400 from Alois P. Heinz)
Temba Shonhiwa, Compositions with pairwise relatively prime summands within a restricted setting, Fibonacci Quart. 44 (2006), no. 4, 316-323.

Row sums of A282748.
A051424 is the unordered version, with strict case A007360.
A335235 ranks these compositions.
A337461 counts these compositions of length 3, with unordered version A307719 and unordered strict version A220377.
A337462 does not consider a singleton to be coprime unless it is (1), with strict version A337561.
A337562 is the strict case.
A337664 looks only at distinct parts, with non-constant version A337665.
A000740 counts relatively prime compositions, with strict case A332004.
A178472 counts compositions with a common factor.
Cf. A087087, A302569, A305713, A326675, A327516, A328673, A333227, A333228.

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],Length[#]<=1||CoprimeQ@@#&]],{n,0,10}] (* Gus Wiseman, Oct 18 2020 *)

It seems that no formula is known.

a(0)=1 prepended by Alois P. Heinz, Jun 14 2017

A337561 Number of pairwise coprime strict compositions of n, where a singleton is not considered coprime unless it is (1).

Original entry on oeis.org

1, 1, 0, 2, 2, 4, 8, 6, 16, 12, 22, 40, 40, 66, 48, 74, 74, 154, 210, 228, 242, 240, 286, 394, 806, 536, 840, 654, 1146, 1618, 2036, 2550, 2212, 2006, 2662, 4578, 4170, 7122, 4842, 6012, 6214, 11638, 13560, 16488, 14738, 15444, 16528, 25006, 41002, 32802

Offset: 0

Gus Wiseman, Sep 18 2020

nonn

			The a(1) = 1 through a(9) = 12 compositions (empty column shown as dot):
   (1)  .  (1,2)  (1,3)  (1,4)  (1,5)    (1,6)  (1,7)    (1,8)
           (2,1)  (3,1)  (2,3)  (5,1)    (2,5)  (3,5)    (2,7)
                         (3,2)  (1,2,3)  (3,4)  (5,3)    (4,5)
                         (4,1)  (1,3,2)  (4,3)  (7,1)    (5,4)
                                (2,1,3)  (5,2)  (1,2,5)  (7,2)
                                (2,3,1)  (6,1)  (1,3,4)  (8,1)
                                (3,1,2)         (1,4,3)  (1,3,5)
                                (3,2,1)         (1,5,2)  (1,5,3)
                                                (2,1,5)  (3,1,5)
                                                (2,5,1)  (3,5,1)
                                                (3,1,4)  (5,1,3)
                                                (3,4,1)  (5,3,1)
                                                (4,1,3)
                                                (4,3,1)
                                                (5,1,2)
                                                (5,2,1)

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..600

A072706 counts unimodal strict compositions.
A220377*6 counts these compositions of length 3.
A305713 is the unordered version.
A337462 is the not necessarily strict version.
A000740 counts relatively prime compositions, with strict case A332004.
A051424 counts pairwise coprime or singleton partitions.
A101268 considers all singletons to be coprime, with strict case A337562.
A178472 counts compositions with a common factor > 1.
A327516 counts pairwise coprime partitions, with strict case A305713.
A328673 counts pairwise non-coprime partitions.
A333228 ranks compositions whose distinct parts are pairwise coprime.
Cf. A007359, A007360, A087087, A216652, A220377, A302569, A307719, A326675, A333227, A337461.

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],#=={}||UnsameQ@@#&&CoprimeQ@@#&]],{n,0,10}]

a(n) = A337562(n) - 1 for n > 1.

A178470 Number of compositions (ordered partitions) of n where no pair of adjacent part sizes is relatively prime.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 5, 1, 8, 4, 17, 3, 38, 5, 67, 25, 132, 27, 290, 54, 547, 163, 1086, 255, 2277, 530, 4416, 1267, 8850, 2314, 18151, 4737, 35799, 10499, 71776, 20501, 145471, 41934, 289695, 89030, 581117, 178424, 1171545, 365619, 2342563, 761051, 4699711

Offset: 0

Franklin T. Adams-Watters, May 28 2010

nonn

A178472(n) is a lower bound for a(n). This bound is exact for n = 2..10 and 12, but falls behind thereafter.

a(0) = 1 vacuously for the empty composition. One could take a(1) = 0, on the theory that each composition is followed by infinitely many 0's, and thus the 1 is not relatively prime to its neighbor; but this definition seems simpler.

			The three compositions for 11 are <11>, <2,6,3> and <3,6,2>.
From _Gus Wiseman_, Nov 19 2019: (Start)
The a(1) = 1 through a(11) = 3 compositions (A = 10, B = 11):
  1  2  3  4   5  6    7  8     9    A      B
           22     24      26    36   28     263
                  33      44    63   46     362
                  42      62    333  55
                  222     224        64
                          242        82
                          422        226
                          2222       244
                                     262
                                     424
                                     442
                                     622
                                     2224
                                     2242
                                     2422
                                     4222
                                     22222
(End)

Alois P. Heinz, Table of n, a(n) for n = 0..1000

The case of partitions is A328187, with Heinz numbers A328336.
Partitions with all pairs of consecutive parts relatively prime are A328172.
Compositions without consecutive divisible parts are A328460 (one way) or A328508 (both ways).
Cf. A000837, A003242, A018783, A167606, A178471, A178472, A328171, A328188, A328220.

b:= proc(n, h) option remember; `if`(n=0, 1,
      add(`if`(h=1 or igcd(j, h)>1, b(n-j, j), 0), j=2..n))
    end:
a:= n-> `if`(n=1, 1, b(n, 1)):
seq(a(n), n=0..60);  # Alois P. Heinz, Oct 23 2011

b[n_, h_] := b[n, h] = If[n == 0, 1, Sum [If[h == 1 || GCD[j, h] > 1, b[n - j, j], 0], {j, 2, n}]]; a[n_] := If[n == 1, 1, b[n, 1]]; Table[a[n], {n, 0, 60}] (* Jean-François Alcover, Oct 29 2015, after Alois P. Heinz *)
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],!MatchQ[#,{_,x_,y_,_}/;GCD[x,y]==1]&]],{n,0,20}] (* Gus Wiseman, Nov 19 2019 *)

am(n)=local(r);r=matrix(n,n,i,j,i==j);for(i=2,n,for(j=1,i-1,for(k=1,j,if(gcd(i-j,k)>1,r[i,i-j]+=r[j,k]))));r
al(n)=local(m);m=am(n);vector(n,i,sum(j=1,i,m[i,j]))

A337462 Number of pairwise coprime compositions of n, where a singleton is not considered coprime unless it is (1).

Original entry on oeis.org

1, 1, 1, 3, 6, 12, 21, 37, 62, 100, 159, 253, 402, 634, 983, 1491, 2224, 3280, 4813, 7043, 10270, 14888, 21415, 30585, 43400, 61204, 85747, 119295, 164834, 226422, 309663, 422301, 574826, 781236, 1060181, 1436367, 1942588, 2622078, 3531151, 4742315, 6348410

Offset: 0

Gus Wiseman, Sep 18 2020

nonn

A composition of n is a finite sequence of positive integers summing to n.

			The a(1) = 1 through a(5) = 12 compositions:
  (1)  (1,1)  (1,2)    (1,3)      (1,4)
              (2,1)    (3,1)      (2,3)
              (1,1,1)  (1,1,2)    (3,2)
                       (1,2,1)    (4,1)
                       (2,1,1)    (1,1,3)
                       (1,1,1,1)  (1,3,1)
                                  (3,1,1)
                                  (1,1,1,2)
                                  (1,1,2,1)
                                  (1,2,1,1)
                                  (2,1,1,1)
                                  (1,1,1,1,1)

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..500

A000740 counts the relatively prime instead of pairwise coprime version.
A101268 considers all singletons to be coprime, with strict case A337562.
A327516 is the unordered version.
A333227 ranks these compositions, with complement A335239.
A337461 counts these compositions of length 3.
A337561 is the strict case.
A051424 counts pairwise coprime or singleton partitions.
A101268 counts pairwise coprime or singleton compositions.
A178472 counts compositions with a common factor.
A305713 counts strict pairwise coprime partitions.
A328673 counts pairwise non-coprime partitions.
A333228 ranks compositions whose distinct parts are pairwise coprime.
A337667 counts pairwise non-coprime compositions.
Cf. A001523, A007360, A087087, A220377, A302569, A307719, A326675, A335235, A335238, A337664.

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],#=={}||CoprimeQ@@#&]],{n,0,10}]

For n > 1, a(n) = A101268(n) - 1.

A337605 Number of unordered triples of distinct positive integers summing to n, any two of which have a common divisor > 1.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 2, 0, 4, 0, 4, 1, 5, 0, 9, 0, 8, 3, 10, 0, 17, 1, 14, 5, 16, 1, 25, 1, 21, 8, 26, 2, 37, 1, 30, 15, 33, 2, 49, 2, 44, 16, 44, 2, 64, 6, 54, 21, 56, 3, 87, 5, 65, 30, 70, 9, 101, 5, 80, 34, 98, 6, 121, 6, 96, 52

Offset: 0

Gus Wiseman, Sep 20 2020

nonn

			The a(n) triples for n = 12, 16, 18, 22, 27, 55:
  (6,4,2)  (8,6,2)   (8,6,4)   (10,8,4)  (12,9,6)  (28,21,6)
           (10,4,2)  (9,6,3)   (12,6,4)  (15,9,3)  (30,20,5)
                     (10,6,2)  (12,8,2)  (18,6,3)  (35,15,5)
                     (12,4,2)  (14,6,2)            (40,10,5)
                               (16,4,2)            (25,20,10)
                                                   (30,15,10)

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..10000

A014612 intersected with A318719 ranks these partitions.
A220377 is the coprime instead of non-coprime version.
A318717 counts these partitions of any length, ranked by A318719.
A337599 is the non-strict version.
A337604 is the ordered non-strict version.
A337605*6 is the ordered version.
A023023 counts relatively prime 3-part partitions
A051424 counts pairwise coprime or singleton partitions.
A200976 and A328673 count pairwise non-coprime partitions.
A307719 counts pairwise coprime 3-part partitions.
A327516 counts pairwise coprime partitions, with strict case A305713.
Cf. A000217, A001399, A014612, A082024, A178472, A220377, A284825, A337461, A337561, A337667.

stabQ[u_,Q_]:=Array[#1==#2||!Q[u[[#1]],u[[#2]]]&,{Length[u],Length[u]},1,And];
Table[Length[Select[IntegerPartitions[n,{3}],UnsameQ@@#&&stabQ[#,CoprimeQ]&]],{n,0,100}]

A333632 Rotational period of the k-th composition in standard order; a(0) = 0.

Original entry on oeis.org

0, 1, 1, 1, 1, 2, 2, 1, 1, 2, 1, 3, 2, 3, 3, 1, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 1, 1, 2, 2, 3, 1, 3, 3, 4, 2, 3, 1, 4, 3, 2, 4, 5, 2, 3, 3, 4, 3, 4, 2, 5, 3, 4, 4, 5, 4, 5, 5, 1, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4

Offset: 0

Gus Wiseman, Apr 12 2020

nonn

A composition of n is a finite sequence of positive integers summing to n. The k-th composition in standard order (graded reverse-lexicographic, A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.

			The a(299) = 5 rotations:
  (1,1,3,2,2)
  (1,3,2,2,1)
  (3,2,2,1,1)
  (2,2,1,1,3)
  (2,1,1,3,2)
The a(9933) = 4 rotations:
  (1,2,1,3,1,2,1,3)
  (1,3,1,2,1,3,1,2)
  (2,1,3,1,2,1,3,1)
  (3,1,2,1,3,1,2,1)

Aperiodic compositions are counted by A000740.
Aperiodic binary words are counted by A027375.
The orderless period of prime indices is A052409.
Numbers whose binary expansion is periodic are A121016.
Periodic compositions are counted by A178472.
The version for binary expansion is A302291.
Numbers whose prime signature is aperiodic are A329139.
Compositions by number of distinct rotations are A333941.
All of the following pertain to compositions in standard order (A066099):
- Length is A000120.
- Necklaces are A065609.
- Sum is A070939.
- Equal runs are counted by A124767.
- Rotational symmetries are counted by A138904.
- Strict compositions are A233564.
- Constant compositions are A272919.
- Lyndon compositions are A275692.
- Co-Lyndon compositions are A326774.
- Aperiodic compositions are A328594.
- Rotational period is A333632 (this sequence).
- Co-necklaces are A333764.
- Reversed necklaces are A333943.
Cf. A000031, A001037, A008965, A019536, A211100, A328595, A328596, A329312, A329313, A329326.

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
Table[Length[Union[Array[RotateRight[stc[n],#]&,DigitCount[n,2,1]]]],{n,0,100}]

a(n) = A000120(n)/A138904(n) = A302291(n) - A023416(n)/A138904(n).

A337604 Number of ordered triples of positive integers summing to n, any two of which have a common divisor > 1.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 1, 0, 3, 1, 6, 0, 13, 0, 15, 7, 21, 0, 37, 0, 39, 16, 45, 0, 73, 6, 66, 28, 81, 0, 130, 6, 105, 46, 120, 21, 181, 6, 153, 67, 189, 12, 262, 6, 213, 118, 231, 12, 337, 21, 306, 121, 303, 12, 433, 57, 369, 154, 378, 18, 583, 30, 435, 217, 465

Offset: 0

Gus Wiseman, Sep 20 2020

nonn

The first relatively prime triple (15,10,6) is counted under a(31).

			The a(6) = 1 through a(15) = 7 triples (empty columns indicated by dots, A = 10):
  222  .  224  333  226  .  228  .  22A  339
          242       244     246     248  366
          422       262     264     266  393
                    424     282     284  555
                    442     336     2A2  636
                    622     363     428  663
                            426     446  933
                            444     464
                            462     482
                            624     626
                            633     644
                            642     662
                            822     824
                                    842
                                    A22

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..10000

A014311 intersected with A337666 ranks these compositions.
A337667 counts these compositions of any length.
A335402 lists the positions of zeros.
A337461 is the coprime instead of non-coprime version.
A337599 is the unordered version, with strict case A337605.
A337605*6 is the strict version.
A000741 counts relatively prime 3-part compositions.
A101268 counts pairwise coprime or singleton compositions.
A200976 and A328673 count pairwise non-relatively prime partitions.
A307719 counts pairwise coprime 3-part partitions.
A318717 counts pairwise non-coprime strict partitions.
A333227 ranks pairwise coprime compositions.
Cf. A000217, A001399, A014612, A051424, A082024, A178472, A220377, A284825, A305713, A327516, A333228, A337561.

stabQ[u_,Q_]:=Array[#1==#2||!Q[u[[#1]],u[[#2]]]&,{Length[u],Length[u]},1,And];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n,{3}],stabQ[#,CoprimeQ]&]],{n,0,100}]

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[#]]&]

A138904 Number of rotational symmetries in the binary expansion of a number.

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 1, 3, 1, 1, 2, 1, 1, 1, 1, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 3, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1

Offset: 0

Max Sills, Apr 03 2008, Apr 04 2008

Mersenne numbers of form (2^n - 1) have n rotational symmetries.
For prime length binary expansions these are the only nontrivial symmetries.
For composite length expansions it seems that when the number of symmetries is nontrivial it is equal to a factor of the length. We're working on an explicit formula.
Discovered in the context of random circulant matrices, examining if there's a correlation between degrees of freedom and number of symmetries in the first row.
When combined with A138954, these two sequences should give a full account of the number of redundant rows in a circulant square matrix with at most two distinct values, where a(n) is the encoding of the first row of the matrix into binary such that value a = 1 and value b = 0.
Discovered on the night of Apr 02, 2008 by Maxwell Sills and Gary Doran.
Conjecture: For binary expansions of length n, there are d(n) distinct values that will show up as symmetries, where d is the divisor function. The symmetry values will be precisely the divisors of n.
Example: for binary expansions of length 12, one sees that d(12) = 6 distinct values show up as symmetries (1, 2, 3, 4, 6, 12).
Conjecture: For numbers whose binary expansion has length n which has proper divisors which are all coprime: There will be only one number of length n with n symmetries. That number is 2^n - 1. For each proper divisor d (excluding 1), you can generate all numbers of length n that have n/d symmetries like so: (2^0 + 2^d + 2^2d ... 2^(n-d)) * a, where 2^(d-1) <= a < (2^d) - 1. The rest of the expansions of length n will have only the trivial symmetry.
Also the number of rotational symmetries of the n-th composition in standard order (graded reverse-lexicographic). This composition (row n of A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of n, prepending 0, taking first differences, and reversing again. - Gus Wiseman, Apr 19 2020
From Gus Wiseman, Apr 19 2020: (Start)
Aperiodic compositions are counted by A000740.
Aperiodic binary words are counted by A027375.
The orderless period of prime indices is A052409.
Numbers whose binary expansion is periodic are A121016.
Periodic compositions are counted by A178472.
Period of binary expansion is A302291.
Compositions by sum and number of distinct rotations are A333941.
All of the following pertain to compositions in standard order (A066099):
- Length is A000120.
- Necklaces are A065609.
- Sum is A070939.
- Runs are counted by A124767.
- Strict compositions are A233564.
- Constant compositions are A272919.
- Lyndon compositions are A275692.
- Co-Lyndon compositions are A326774.
- Aperiodic compositions are A328594.
- Reversed co-necklaces are A328595.
- Rotational period is A333632.
- Co-necklaces are A333764.
- Reversed necklaces are A333943.
Cf. A000031, A001037, A008965, A019536, A211100, A328595, A328596, A329312, A329313, A329326.
(End).

			a(10) = 2 because the binary expansion of 10 is 1010 and it has two rotational symmetries (including identity).

Maxwell Sills and Gary Doran, Table of n, a(n) for n = 0..99

Cf. A136441, A138954.

Table[IntegerLength[n,2]/Length[Union[Array[RotateRight[IntegerDigits[n,2],#]&,IntegerLength[n,2]]]],{n,100}] (* Gus Wiseman, Apr 19 2020 *)

a(n) = A070939(n)/A302291(n) = A000120(n)/A333632(n). - Gus Wiseman, Apr 19 2020

cp's OEIS Frontend

A000740 Number of 2n-bead balanced binary necklaces of fundamental period 2n, equivalent to reversed complement; also Dirichlet convolution of b_n=2^(n-1) with mu(n); also number of components of Mandelbrot set corresponding to Julia sets with an attractive n-cycle.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions

A101268 Number of compositions of n into pairwise relatively prime parts.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A337561 Number of pairwise coprime strict compositions of n, where a singleton is not considered coprime unless it is (1).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A178470 Number of compositions (ordered partitions) of n where no pair of adjacent part sizes is relatively prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A337462 Number of pairwise coprime compositions of n, where a singleton is not considered coprime unless it is (1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A337605 Number of unordered triples of distinct positive integers summing to n, any two of which have a common divisor > 1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

A333632 Rotational period of the k-th composition in standard order; a(0) = 0.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica