A059966 -id:A059966 - cp's OEIS frontend

A299151 Numerators of the positive solution to 2^(n-1) = Sum_{d|n} a(d) * a(n/d).

1, 1, 2, 7, 8, 14, 32, 121, 126, 248, 512, 1003, 2048, 4064, 8176, 130539, 32768, 65382, 131072, 261868, 524224, 1048064, 2097152, 4193131, 8388576, 16775168, 33554180, 67104688, 134217728, 268426672, 536870912, 8589802359, 2147482624, 4294934528, 8589934336, 17179801257, 34359738368, 68719345664, 137438949376, 274877643724, 549755813888

Offset: 1

Gus Wiseman, Feb 03 2018

Numerators of rational valued sequence f whose Dirichlet convolution with itself yields function g(n) = A000079(n-1) = 2^(n-1). - Antti Karttunen, Aug 10 2018

			Sequence begins: 1, 1, 2, 7/2, 8, 14, 32, 121/2, 126, 248, 512, 1003, 2048, 4064, 8176, 130539/8, 32768.

Andrew Howroyd, Table of n, a(n) for n = 1..1000

Cf. A000005, A000010, A000740, A018804, A023900, A029935, A034691, A046643, A059966, A228369, A257098, A296302, A298971, A299119, A299149, A299152.

Cf. also A317831.

nn=50;
sys=Table[2^(n-1)==Sum[a[d]*a[n/d],{d,Divisors[n]}],{n,nn}];
Numerator[Array[a,nn]/.Solve[sys,Array[a,nn]][[2]]]

A299151perA299152(n) = if(1==n,n,(2^(n-1)-sumdiv(n,d,if((d>1)&&(dA299151perA299152(d)*A299151perA299152(n/d),0)))/2);
A299151(n) = numerator(A299151perA299152(n));

More terms from Antti Karttunen, Jul 29 2018

A324513 Number of aperiodic cycle necklaces with n vertices.

Original entry on oeis.org

1, 0, 0, 0, 2, 7, 51, 300, 2238, 18028, 164945, 1662067, 18423138, 222380433, 2905942904, 40864642560, 615376173176, 9880203467184, 168483518571789, 3041127459127222, 57926238289894992, 1161157775616335125, 24434798429947993043, 538583682037962702384

Offset: 1

Gus Wiseman, Mar 04 2019

nonn

We define an aperiodic cycle necklace to be an equivalence class of (labeled, undirected) Hamiltonian cycles under rotation of the vertices such that all n of these rotations are distinct.

Andrew Howroyd, Table of n, a(n) for n = 1..200
Gus Wiseman, Inequivalent representatives of the a(6) = 7 aperiodic cycle necklaces.
Gus Wiseman, Inequivalent representatives of the a(7) = 51 aperiodic cycle necklaces.

Cf. A000740, A000939, A001037 (binary Lyndon words), A008965, A059966 (Lyndon compositions), A060223 (normal Lyndon words), A061417, A064852 (if cycle is oriented), A086675, A192332, A275527, A323866 (aperiodic toroidal arrays), A323871.

Cf. A306669, A324461, A324462, A324512, A324514.

rotgra[g_,m_]:=Sort[Sort/@(g/.k_Integer:>If[k==m,1,k+1])];
Table[Length[Select[Union[Sort[Sort/@Partition[#,2,1,1]]&/@Permutations[Range[n]]],#==First[Sort[Table[Nest[rotgra[#,n]&,#,j],{j,n}]]]&&UnsameQ@@Table[Nest[rotgra[#,n]&,#,j],{j,n}]&]],{n,8}]

a(n)={if(n<3, n==0||n==1, (if(n%2, 0, -(n/2-1)!*2^(n/2-2)) + sumdiv(n, d, moebius(n/d)*eulerphi(n/d)*(n/d)^d*d!/n^2))/2)} \\ Andrew Howroyd, Aug 19 2019

a(n) = A324512(n)/n.

a(2*n+1) = A064852(2*n+1)/2 for n > 0; a(2*n) = (A064852(2*n) - A002866(n-1))/2 for n > 1. - Andrew Howroyd, Aug 16 2019

Terms a(10) and beyond from Andrew Howroyd, Aug 19 2019

A328597 Number of necklace compositions of n where every pair of adjacent parts (including the last with the first) is relatively prime.

Original entry on oeis.org

1, 1, 2, 3, 5, 8, 12, 21, 33, 57, 94, 167, 279, 491, 852, 1507, 2647, 4714, 8349, 14923, 26642, 47793, 85778, 154474, 278322, 502715, 908912, 1646205, 2984546, 5418652, 9847189, 17916000, 32625617, 59470539, 108493149, 198094482, 361965238, 661891579, 1211162270

Offset: 1

Gus Wiseman, Oct 23 2019

nonn

A necklace composition of n is a finite sequence of positive integers summing to n that is lexicographically minimal among all of its cyclic rotations.

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

Andrew Howroyd, Table of n, a(n) for n = 1..200

The non-necklace version is A328609.
The non-necklace non-circular version is A167606.
The version with singletons is A318728.
The aperiodic case is A318745.
The indivisible (instead of coprime) version is A328600.
The non-coprime (instead of coprime) version is A328602.
Necklace compositions are A008965.
Cf. A000031, A000740, A000837, A032153, A059966, A318729, A318748, A328172, A328598, A328599, A328601.

neckQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],neckQ[#]&&And@@CoprimeQ@@@Partition[#,2,1,1]&]],{n,10}]

b(n, q, pred)={my(M=matrix(n, n)); for(k=1, n, M[k, k]=pred(q, k); for(i=1, k-1, M[i, k]=sum(j=1, k-i, if(pred(j, i), M[j, k-i], 0)))); M[q,]}
seq(n)={my(v=sum(k=1, n, k*b(n, k, (i,j)->gcd(i,j)==1))); vector(n, n, sumdiv(n, d, eulerphi(d)*v[n/d])/n)} \\ Andrew Howroyd, Oct 26 2019

a(n > 1) = A318728(n) - 1.

Terms a(21) and beyond from Andrew Howroyd, Oct 26 2019

A334266 Numbers k such that the k-th composition in standard order is both a reversed Lyndon word and a co-Lyndon word.

Original entry on oeis.org

0, 1, 2, 4, 5, 8, 9, 11, 16, 17, 18, 19, 21, 23, 32, 33, 34, 35, 37, 39, 43, 47, 64, 65, 66, 67, 68, 69, 71, 73, 74, 75, 77, 79, 85, 87, 91, 95, 128, 129, 130, 131, 132, 133, 135, 137, 138, 139, 141, 143, 146, 147, 149, 151, 155, 159, 171, 173, 175, 183, 191

Offset: 1

Gus Wiseman, Apr 22 2020

nonn

A Lyndon word is a finite sequence of positive integers that is lexicographically strictly less than all of its cyclic rotations. Co-Lyndon is defined similarly, except with strictly greater instead of strictly less.

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 sequence of all reversed Lyndon co-Lyndon words begins:
    0: ()            37: (3,2,1)         91: (2,1,2,1,1)
    1: (1)           39: (3,1,1,1)       95: (2,1,1,1,1,1)
    2: (2)           43: (2,2,1,1)      128: (8)
    4: (3)           47: (2,1,1,1,1)    129: (7,1)
    5: (2,1)         64: (7)            130: (6,2)
    8: (4)           65: (6,1)          131: (6,1,1)
    9: (3,1)         66: (5,2)          132: (5,3)
   11: (2,1,1)       67: (5,1,1)        133: (5,2,1)
   16: (5)           68: (4,3)          135: (5,1,1,1)
   17: (4,1)         69: (4,2,1)        137: (4,3,1)
   18: (3,2)         71: (4,1,1,1)      138: (4,2,2)
   19: (3,1,1)       73: (3,3,1)        139: (4,2,1,1)
   21: (2,2,1)       74: (3,2,2)        141: (4,1,2,1)
   23: (2,1,1,1)     75: (3,2,1,1)      143: (4,1,1,1,1)
   32: (6)           77: (3,1,2,1)      146: (3,3,2)
   33: (5,1)         79: (3,1,1,1,1)    147: (3,3,1,1)
   34: (4,2)         85: (2,2,2,1)      149: (3,2,2,1)
   35: (4,1,1)       87: (2,2,1,1,1)    151: (3,2,1,1,1)

The version for binary expansion is A334267.
Compositions of this type are counted by A334269.
Normal sequences of this type are counted by A334270.
Necklace compositions of this type are counted by A334271.
Binary Lyndon words are counted by A001037.
Lyndon compositions are counted by A059966.
All of the following pertain to compositions in standard order (A066099):
- Length is A000120.
- Necklaces are A065609.
- Sum is A070939.
- Reverse is A228351 (triangle).
- Strict compositions are A233564.
- Constant compositions are A272919.
- Lyndon words are A275692.
- Reversed Lyndon words are A334265.
- Co-Lyndon words are A326774.
- Reversed co-Lyndon words are A328596.
- Length of Lyndon factorization is A329312.
- Length of Lyndon factorization of reverse is A334297.
- Length of co-Lyndon factorization is A334029.
- Length of co-Lyndon factorization of reverse is A329313.
- Distinct rotations are counted by A333632.
- Co-Lyndon factorizations are counted by A333765.
- Lyndon factorizations are counted by A333940.
Cf. A000740, A008965, A065609, A329324, A333764, A333943, A334272, A334297.

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
lynQ[q_]:=Length[q]==0||Array[Union[{q,RotateRight[q,#1]}]=={q,RotateRight[q,#1]}&,Length[q]-1,1,And];
colynQ[q_]:=Length[q]==0||Array[Union[{RotateRight[q,#],q}]=={RotateRight[q,#],q}&,Length[q]-1,1,And];
Select[Range[0,100],lynQ[Reverse[stc[#]]]&&colynQ[stc[#]]&]

Intersection of A334265 and A326774.

A298941 Number of permutations of the multiset of prime factors of n > 1 that are Lyndon words.

Original entry on oeis.org

1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 2, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 0, 1, 2, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 0, 1, 1, 3, 1, 1, 1, 1, 1, 3

Offset: 2

Gus Wiseman, Jan 29 2018

nonn

			The a(90) = 3 Lyndon permutations are {2,3,3,5}, {2,3,5,3}, {2,5,3,3}.

Alois P. Heinz, Table of n, a(n) for n = 2..20000

Cf. A000740, A001037, A001222, A008480, A008965, A059966, A060223, A096443, A112798, A215366, A275024, A294859, A298947.

with(combinat): with(numtheory):
g:= l-> (n-> `if`(n=0, 1, add(mobius(j)*multinomial(n/j,
        (l/j)[]), j=divisors(igcd(l[])))/n))(add(i, i=l)):
a:= n-> g(map(i-> i[2], ifactors(n)[2])):
seq(a(n), n=2..150);  # Alois P. Heinz, Feb 09 2018

primeMS[n_]:=If[n===1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
LyndonQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And]&&Array[RotateRight[q,#]&,Length[q],1,UnsameQ];
Table[Length[Select[Permutations[primeMS[n]],LyndonQ]],{n,2,60}]
(* Second program: *)
multinomial[n_, k_List] := n!/Times @@ (k!);
g[l_] := With[{n = Total[l]}, If[n == 0, 1, Sum[MoebiusMu[j] multinomial[ n/j, l/j], {j, Divisors[GCD @@ l]}]/n]];
a[n_] := g[FactorInteger[n][[All, 2]]];
a /@ Range[2, 150] (* Jean-François Alcover, Dec 15 2020, after Alois P. Heinz *)

A318745 Number of Lyndon compositions (aperiodic necklaces of positive integers) with sum n and adjacent parts (including the last with the first part) being coprime.

Original entry on oeis.org

1, 1, 2, 3, 5, 7, 12, 19, 32, 53, 94, 158, 279, 480, 847, 1487, 2647, 4676, 8349, 14865, 26630, 47700, 85778, 154290, 278318, 502437, 908880, 1645713, 2984546, 5417743, 9847189, 17914494, 32625523, 59467893, 108493134, 198089610, 361965238, 661883231, 1211161991

Offset: 1

Gus Wiseman, Sep 02 2018

nonn

			The a(7) = 12 Lyndon compositions with adjacent parts coprime:
  (7)
  (16) (25) (34)
  (115)
  (1114) (1213) (1132) (1123)
  (11113) (11212)
  (111112)

Andrew Howroyd, Table of n, a(n) for n = 1..100

Cf. A000740, A008965, A059966, A100953, A167606, A296302, A318728, A318731, A318746, A318747.

LyndonQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And]&&Array[RotateRight[q,#]&,Length[q],1,UnsameQ];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],Or[Length[#]==1,LyndonQ[#]&&And@@CoprimeQ@@@Partition[#,2,1,1]]&]],{n,20}]

b(n, q, pred)={my(M=matrix(n, n)); for(k=1, n, M[k, k]=pred(q, k); for(i=1, k-1, M[i, k]=sum(j=1, k-i, if(pred(j, i), M[j, k-i], 0)))); M[q, ]}
seq(n)={my(v=sum(k=1, n, k*b(n, k, (i, j)->gcd(i, j)==1))); vector(n, n, (n > 1) + sumdiv(n, d, moebius(d)*v[n/d])/n)} \\ Andrew Howroyd, Nov 01 2019

a(n) = A328669(n) + 1 for n > 1. - Andrew Howroyd, Nov 01 2019

Terms a(21) and beyond from Andrew Howroyd, Sep 08 2018

A320776 Inverse Euler transform of the number of prime factors (with multiplicity) function A001222.

Original entry on oeis.org

1, 0, 1, 1, 1, 0, -1, -1, 0, 1, 0, -1, -1, -1, 1, 3, 3, -2, -5, -4, 0, 7, 7, 0, -9, -10, 2, 15, 15, -3, -27, -30, 3, 46, 51, 1, -71, -91, -7, 117, 157, 23, -194, -265, -57, 318, 465, 111, -536, -821, -230, 893, 1456, 505, -1485, -2559, -1036, 2433, 4483, 2022

Offset: 0

Gus Wiseman, Oct 22 2018

sign

The Euler transform of a sequence q is the sequence of coefficients of x^n, n > 0, in the expansion of Product_{n > 0} 1/(1 - x^n)^q(n). The constant term 1 is sometimes taken to be the zeroth part of the Euler transform.

Number theoretical functions: A000005, A000010, A000203, A001055, A001221, A001222, A008683, A010054.
Euler transforms: A000081, A001970, A006171, A007294, A061255, A061256, A061257, A073576, A117209, A293548, A293549.
Inverse Euler transforms: A059966, A320767, A320777, A320778, A320779, A320780, A320781, A320782.

# The function EulerInvTransform is defined in A358451.
a := EulerInvTransform(n -> ifelse(n=0, 1, NumberTheory:-NumberOfPrimeFactors(n))):
seq(a(n), n = 0..59); # Peter Luschny, Nov 21 2022

EulerInvTransform[{}]={};EulerInvTransform[seq_]:=Module[{final={}},For[i=1,i<=Length[seq],i++,AppendTo[final,i*seq[[i]]-Sum[final[[d]]*seq[[i-d]],{d,i-1}]]];
Table[Sum[MoebiusMu[i/d]*final[[d]],{d,Divisors[i]}]/i,{i,Length[seq]}]];
EulerInvTransform[Array[PrimeOmega,100]]

A320777 Inverse Euler transform of the number of distinct prime factors (without multiplicity) function A001221.

Original entry on oeis.org

1, 0, 1, 1, 0, 0, 0, 0, -1, -1, 1, 1, 0, -1, 0, 1, -1, -2, 1, 3, 1, -2, -2, 1, 0, -4, 0, 6, 6, -4, -8, 1, 4, -4, -5, 10, 16, -4, -25, -7, 17, 5, -16, 2, 42, 12, -58, -48, 40, 59, -27, -44, 67, 86, -103, -187, 36, 236, 45, -213, -5, 284, -23, -526, -188, 663, 520

Offset: 0

Gus Wiseman, Oct 22 2018

sign

The Euler transform of a sequence q is the sequence of coefficients of x^n, n > 0, in the expansion of Product_{n > 0} 1/(1 - x^n)^q(n). The constant term 1 is sometimes taken to be the zeroth part of the Euler transform.

Number theoretical functions: A000005, A000010, A000203, A001055, A001221, A001222, A008683, A010054.
Euler transforms: A000081, A001970, A006171, A007294, A061255, A061256, A061257, A073576, A117209, A293548, A293549.
Inverse Euler transforms: A059966, A320767, A320776, A320778, A320779, A320780, A320781, A320782.

EulerInvTransform[{}]={};EulerInvTransform[seq_]:=Module[{final={}},For[i=1,i<=Length[seq],i++,AppendTo[final,i*seq[[i]]-Sum[final[[d]]*seq[[i-d]],{d,i-1}]]];
Table[Sum[MoebiusMu[i/d]*final[[d]],{d,Divisors[i]}]/i,{i,Length[seq]}]];
EulerInvTransform[Array[PrimeNu,100]]

A320782 Inverse Euler transform of the unsigned Moebius function A008966.

Original entry on oeis.org

1, 1, 0, 0, -1, 1, 0, 0, -1, 1, 0, 0, -2, 3, 0, -1, -3, 6, -3, 0, -6, 12, -6, 0, -9, 23, -17, 0, -15, 47, -40, 8, -24, 91, -101, 34, -46, 181, -230, 109, -92, 354, -534, 323, -208, 690, -1177, 883, -520, 1365, -2603, 2297, -1377, 2760, -5641, 5789, -3721, 5741

Offset: 0

Gus Wiseman, Oct 22 2018

sign

The Euler transform of a sequence q is the sequence of coefficients of x^n, n > 0, in the expansion of Product_{n > 0} 1/(1 - x^n)^q(n). The constant term 1 is sometimes taken to be the zeroth part of the Euler transform.

OEIS Wiki, Euler transform

Number theoretical functions: A000005, A000010, A000203, A001055, A001221, A001222, A008683, A010054.
Euler transforms: A000081, A001970, A006171, A007294, A061255, A061256, A061257, A073576, A117209, A293548, A293549.
Inverse Euler transforms: A059966, A320767, A320776, A320777, A320778, A320779, A320780, A320781.

EulerInvTransform[{}]={};EulerInvTransform[seq_]:=Module[{final={}},For[i=1,i<=Length[seq],i++,AppendTo[final,i*seq[[i]]-Sum[final[[d]]*seq[[i-d]],{d,i-1}]]];
Table[Sum[MoebiusMu[i/d]*final[[d]],{d,Divisors[i]}]/i,{i,Length[seq]}]];
EulerInvTransform[Table[Abs[MoebiusMu[n]],{n,30}]]

A325549 Number of necklace compositions of n with distinct circular differences.

Original entry on oeis.org

1, 1, 2, 3, 5, 4, 10, 16, 23, 34, 53, 66, 113, 164, 262, 380, 567, 821, 1217, 1778, 2702, 3919, 5760, 8520, 12375

Offset: 1

Gus Wiseman, May 10 2019

A necklace composition of n is a finite sequence of positive integers summing to n that is lexicographically minimal among all of its cyclic rotations.

The circular differences of a composition c of length k are c_{i + 1} - c_i for i < k and c_1 - c_i for i = k. For example, the circular differences of (1,2,1,3) are (1,-1,2,-2).

			The a(1) = 1 through a(8) = 16 necklace compositions:
  (1)  (2)  (3)   (4)    (5)    (6)    (7)     (8)
            (12)  (13)   (14)   (15)   (16)    (17)
                  (112)  (23)   (24)   (25)    (26)
                         (113)  (114)  (34)    (35)
                         (122)         (115)   (116)
                                       (124)   (125)
                                       (133)   (134)
                                       (142)   (143)
                                       (223)   (152)
                                       (1213)  (224)
                                               (233)
                                               (1124)
                                               (1142)
                                               (1214)
                                               (11213)
                                               (11312)

Gus Wiseman, Sequences counting and ranking integer partitions by the differences of their successive parts.

Cf. A000079, A000740, A008965, A034297, A059966, A070211, A318728, A318748, A320348, A325545, A325551, A325554, A325556.

neckQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],neckQ[#]&&UnsameQ@@Append[Differences[#],First[#]-Last[#]]&]],{n,15}]

cp's OEIS Frontend

A299151 Numerators of the positive solution to 2^(n-1) = Sum_{d|n} a(d) * a(n/d).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A324513 Number of aperiodic cycle necklaces with n vertices.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A328597 Number of necklace compositions of n where every pair of adjacent parts (including the last with the first) is relatively prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A334266 Numbers k such that the k-th composition in standard order is both a reversed Lyndon word and a co-Lyndon word.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A298941 Number of permutations of the multiset of prime factors of n > 1 that are Lyndon words.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A318745 Number of Lyndon compositions (aperiodic necklaces of positive integers) with sum n and adjacent parts (including the last with the first part) being coprime.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A320776 Inverse Euler transform of the number of prime factors (with multiplicity) function A001222.

Views

Author

Keywords

Comments

Crossrefs

Programs

Maple

Mathematica

A320777 Inverse Euler transform of the number of distinct prime factors (without multiplicity) function A001221.