A085945 -id:A085945 - cp's OEIS frontend

A224840 Divisor sum of the arithmetic function A085945(n).

1, 3, 6, 14, 27, 61, 117, 250, 494, 1012, 2007, 4088, 8112, 16357, 32635, 65493, 130779, 262115, 523710, 1048502, 2096110, 4194124, 8386419, 16777182, 33550085, 67108507, 134209495, 268434899, 536853987, 1073741664, 2147449815, 4294966187, 8589868975, 17179866799

Offset: 1

Prapanpong Pongsriiam, Sep 18 2013

nonn

Also the number of subsets A of {1, 2, 3, ..., n} such that gcd(A) divides n.

Charles R Greathouse IV, Table of n, a(n) for n = 1..3321
P. Pongsriiam, Relatively Prime Sets, Divisor Sums, and Partial Sums, arXiv:1306.4891 and J. Int. Seq. 16 (2013) #13.9.1.
P. Pongsriiam, A remark on relative prime sets, Integers 13 (2013), A49.

Cf. A038199, A027375, Divisor sums of A085945.

A085945(n)=sum(k=1, n, moebius(k)*(2^(n\k)-1))
a(n)=sumdiv(n,d,A085945(d)) \\ Charles R Greathouse IV, Sep 19 2013

a(n)=my(v=vector(n,i,i));sum(i=1,2^n-1,n%gcd(vecextract(v,i))==0) \\ Charles R Greathouse IV, Sep 19 2013

a(n) = sum{d | n} sum_{k <= d} mu(k)*(2^floor(n/k) - 1) where mu is the Moebius function.

a(19)-a(34) from Charles R Greathouse IV, Sep 19 2013

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.

Original entry on oeis.org

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

A324736 Number of subsets of {1...n} containing all prime indices of the elements.

Original entry on oeis.org

1, 2, 3, 4, 7, 9, 15, 22, 43, 79, 127, 175, 343, 511, 851, 1571, 3141, 4397, 8765, 13147, 25243, 46843, 76795, 115171, 230299, 454939, 758203, 1516363, 2916079, 4356079, 8676079, 12132079, 24264157, 45000157, 73800253, 145685053, 291369853, 437054653, 728424421

Offset: 0

Gus Wiseman, Mar 13 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.

Also the number of subsets of {1...n} containing no prime indices of the non-elements up to n.

			The a(0) = 1 through a(6) = 15 subsets:
  {}  {}   {}     {}       {}         {}           {}
      {1}  {1}    {1}      {1}        {1}          {1}
           {1,2}  {1,2}    {1,2}      {1,2}        {1,2}
                  {1,2,3}  {1,4}      {1,4}        {1,4}
                           {1,2,3}    {1,2,3}      {1,2,3}
                           {1,2,4}    {1,2,4}      {1,2,4}
                           {1,2,3,4}  {1,2,3,4}    {1,2,6}
                                      {1,2,3,5}    {1,2,3,4}
                                      {1,2,3,4,5}  {1,2,3,5}
                                                   {1,2,3,6}
                                                   {1,2,4,6}
                                                   {1,2,3,4,5}
                                                   {1,2,3,4,6}
                                                   {1,2,3,5,6}
                                                   {1,2,3,4,5,6}
An example for n = 18 is {1,2,4,7,8,9,12,16,17,18}, whose elements have the following prime indices:
   1: {}
   2: {1}
   4: {1,1}
   7: {4}
   8: {1,1,1}
   9: {2,2}
  12: {1,1,2}
  16: {1,1,1,1}
  17: {7}
  18: {1,2,2}
All of these prime indices {1,2,4,7} belong to the subset, as required.

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

The strict integer partition version is A324748. The integer partition version is A324753. The Heinz number version is A290822. An infinite version is A324698.
Cf. A000720, A001462, A007097, A076078, A084422, A085945, A112798, A276625, A279861, A290689, A304360, A320426.
Cf. A324697, A324737, A324741, A324743.

Table[Length[Select[Subsets[Range[n]],SubsetQ[#,PrimePi/@First/@Join@@FactorInteger/@DeleteCases[#,1]]&]],{n,0,10}]

pset(n)={my(b=0, f=factor(n)[,1]); sum(i=1, #f, 1<<(primepi(f[i])))}
a(n)={my(p=vector(n,k,pset(k)), d=0); for(i=1, #p, d=bitor(d, p[i]));
((k,b)->if(k>#p, 1, my(t=self()(k+1,b)); if(!bitnegimply(p[k], b), t+=if(bittest(d,k), self()(k+1, b+(1<Andrew Howroyd, Aug 15 2019

Terms a(21) and beyond from Andrew Howroyd, Aug 15 2019

A324743 Number of maximal subsets of {1...n} containing no prime indices of the elements.

Original entry on oeis.org

1, 1, 2, 2, 3, 4, 5, 8, 8, 8, 8, 12, 12, 18, 18, 19, 19, 30, 30, 54, 54, 54, 54, 96, 96, 96, 96, 96, 96, 156, 156, 244, 244, 248, 248, 248, 248, 440, 440, 440, 440, 688, 688, 1120, 1120, 1120, 1120, 1864, 1864, 1864, 1864, 1864, 1864, 3664, 3664, 3664, 3664, 3664

Offset: 0

Gus Wiseman, Mar 15 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.

			The a(0) = 1 through a(8) = 8 maximal subsets:
  {}  {1}  {1}  {2}    {1,3}  {1,3}    {1,3}    {1,3,7}  {1,3,7}
           {2}  {1,3}  {2,4}  {1,5}    {1,5}    {1,5,7}  {1,5,7}
                       {3,4}  {3,4}    {2,4,5}  {2,4,5}  {2,4,5,8}
                              {2,4,5}  {3,4,6}  {2,5,7}  {2,5,7,8}
                                       {4,5,6}  {3,4,6}  {3,4,6,8}
                                                {3,6,7}  {3,6,7,8}
                                                {4,5,6}  {4,5,6,8}
                                                {5,6,7}  {5,6,7,8}
An example for n = 15 is {1,5,7,9,13,15}, with prime indices:
  1: {}
  5: {3}
  7: {4}
  9: {2,2}
  13: {6}
  15: {2,3}
None of these prime indices {2,3,4,6} belong to the subset, as required.

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

The non-maximal case is A324741. The case for subsets of {2...n} is A324763.
Cf. A000720, A001462, A007097, A084422, A085945, A112798, A276625, A290689, A290822, A304360, A306844, A320426, A324764.
Cf. A324695, A324736, A324742, A324744, A324751, A324756, A324758.

maxim[s_]:=Complement[s,Last/@Select[Tuples[s,2],UnsameQ@@#&&SubsetQ@@#&]];
Table[Length[maxim[Select[Subsets[Range[n]],Intersection[#,PrimePi/@First/@Join@@FactorInteger/@#]=={}&]]],{n,0,10}]

pset(n)={my(b=0, f=factor(n)[, 1]); sum(i=1, #f, 1<<(primepi(f[i])))}
a(n)={my(p=vector(n, k, pset(k)), d=0); for(i=1, #p, d=bitor(d, p[i]));
my(ismax(b)=my(e=0); forstep(k=#p, 1, -1, if(bittest(b,k), e=bitor(e,p[k]), if(!bittest(e,k) && !bitand(p[k], b), return(0)) )); 1);
((k, b)->if(k>#p, ismax(b), my(f=!bitand(p[k], b)); if(!f || bittest(d, k), self()(k+1, b)) + if(f, self()(k+1, b+(1<Andrew Howroyd, Aug 26 2019

Terms a(16) and beyond from Andrew Howroyd, Aug 26 2019

A324744 Number of maximal subsets of {1...n} containing no element whose prime indices all belong to the subset.

Original entry on oeis.org

1, 1, 2, 2, 3, 4, 4, 5, 6, 8, 8, 11, 11, 22, 22, 22, 22, 28, 28, 44, 44, 52, 52, 76, 76, 88, 88, 96, 96, 184, 184, 240, 240, 264, 264, 296, 296, 592, 592, 592, 592, 728, 728, 1456, 1456, 1456, 1456, 2912, 2912, 3168, 3168, 3168, 3168, 5568, 5568, 5568, 5568

Offset: 0

Gus Wiseman, Mar 15 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.

			The a(1) = 1 through a(8) = 6 maximal subsets:
  {1}  {1}  {2}    {1,3}  {1,3}    {1,3,6}    {3,4,6}    {1,3,6,7}
       {2}  {1,3}  {2,4}  {1,5}    {1,5,6}    {1,3,6,7}  {1,5,6,7}
                   {3,4}  {3,4}    {3,4,6}    {1,5,6,7}  {3,4,6,8}
                          {2,4,5}  {2,4,5,6}  {2,4,5,6}  {3,6,7,8}
                                              {2,5,6,7}  {2,4,5,6,8}
                                                         {2,5,6,7,8}

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

The non-maximal case is A324738. The case for subsets of {2...n} is A324762.
Cf. A000720, A001462, A007097, A076078, A084422, A085945, A112798, A276625, A290822, A304360, A306844, A320426, A324764.
Cf. A324694, A324736, A324743, A324749, A324754, A324759.

maxim[s_]:=Complement[s,Last/@Select[Tuples[s,2],UnsameQ@@#&&SubsetQ@@#&]];
Table[Length[maxim[Select[Subsets[Range[n]],!MemberQ[#,k_/;SubsetQ[#,PrimePi/@First/@FactorInteger[k]]]&]]],{n,0,10}]

pset(n)={my(b=0, f=factor(n)[, 1]); sum(i=1, #f, 1<<(primepi(f[i])))}
a(n)={my(p=vector(n, k, if(k==1, 1, pset(k))), d=0); for(i=1, #p, d=bitor(d, p[i]));
my(ismax(b)=for(k=1, #p, if(!bittest(b,k) && bitnegimply(p[k], b), my(e=bitor(b, 1<#p, ismax(b), my(f=bitnegimply(p[k], b)); if(!f || bittest(d, k), self()(k+1, b)) + if(f, self()(k+1, b+(1<Andrew Howroyd, Aug 27 2019

Terms a(16) and beyond from Andrew Howroyd, Aug 27 2019

A324738 Number of subsets of {1...n} containing no element > 1 whose prime indices all belong to the subset.

Original entry on oeis.org

1, 2, 3, 5, 8, 13, 26, 42, 72, 120, 232, 376, 752, 1128, 2256, 4512, 8256, 13632, 27264, 42048, 82944, 158976, 313344, 497664, 995328, 1700352, 3350016, 5815296, 11630592, 17491968, 34983936, 56954880, 108933120, 210788352, 418258944, 804667392, 1609334784

Offset: 0

Gus Wiseman, Mar 13 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.

			The a(0) = 1 through a(6) = 26 subsets:
  {}  {}   {}   {}     {}     {}       {}
      {1}  {1}  {1}    {1}    {1}      {1}
           {2}  {2}    {2}    {2}      {2}
                {3}    {3}    {3}      {3}
                {1,3}  {4}    {4}      {4}
                       {1,3}  {5}      {5}
                       {2,4}  {1,3}    {6}
                       {3,4}  {1,5}    {1,3}
                              {2,4}    {1,5}
                              {2,5}    {1,6}
                              {3,4}    {2,4}
                              {4,5}    {2,5}
                              {2,4,5}  {2,6}
                                       {3,4}
                                       {3,6}
                                       {4,5}
                                       {4,6}
                                       {5,6}
                                       {1,3,6}
                                       {1,5,6}
                                       {2,4,5}
                                       {2,4,6}
                                       {2,5,6}
                                       {3,4,6}
                                       {4,5,6}
                                       {2,4,5,6}

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

The maximal case is A324744. The case of subsets of {2...n} is A324739. The strict integer partition version is A324749. The integer partition version is A324754. The Heinz number version is A324759. An infinite version is A324694.
Cf. A000720, A001221, A001462, A007097, A076078, A084422, A085945, A112798, A276625, A279861, A290689, A290822, A304360, A306844.
Cf. A324695, A324736, A324741, A324750, A324755, A324760.

Table[Length[Select[Subsets[Range[n]],!MemberQ[#,k_/;SubsetQ[#,PrimePi/@First/@FactorInteger[k]]]&]],{n,0,10}]

pset(n)={my(b=0,f=factor(n)[,1]); sum(i=1, #f, 1<<(primepi(f[i])))}
a(n)={my(p=vector(n,k,if(k==1, 1, pset(k))), d=0); for(i=1, #p, d=bitor(d, p[i]));
((k,b)->if(k>#p, 1, my(t=self()(k+1,b)); if(bitnegimply(p[k], b), t+=if(bittest(d,k), self()(k+1, b+(1<Andrew Howroyd, Aug 16 2019

Terms a(21) and beyond from Andrew Howroyd, Aug 16 2019

A324742 Number of subsets of {2...n} containing no prime indices of the elements.

Original entry on oeis.org

1, 2, 3, 6, 10, 16, 24, 48, 84, 144, 228, 420, 648, 1080, 1800, 3600, 5760, 11136, 16704, 31104, 53568, 90624, 136896, 269952, 515712, 862080, 1708800, 3171840, 4832640, 9325440, 14890752, 29781504, 52245504, 88418304, 166017024, 331628544, 497645568, 829409280

Offset: 1

Gus Wiseman, Mar 15 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.

			The a(1) = 1 through a(6) = 16 subsets:
  {}  {}   {}   {}     {}       {}
      {2}  {2}  {2}    {2}      {2}
           {3}  {3}    {3}      {3}
                {4}    {4}      {4}
                {2,4}  {5}      {5}
                {3,4}  {2,4}    {6}
                       {2,5}    {2,4}
                       {3,4}    {2,5}
                       {4,5}    {3,4}
                       {2,4,5}  {3,6}
                                {4,5}
                                {4,6}
                                {5,6}
                                {2,4,5}
                                {3,4,6}
                                {4,5,6}
An example for n = 20 is {4,5,6,12,17,18,19}, with prime indices:
   4: {1,1}
   5: {3}
   6: {1,2}
  12: {1,1,2}
  17: {7}
  18: {1,2,2}
  19: {8}
None of these prime indices {1,2,3,7,8} belong to the set, as required.

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

The maximal case is A324763. The version for subsets of {1...n} is A324741. The strict integer partition version is A324752. The integer partition version is A324757. The Heinz number version is A324761. An infinite version is A304360.
Cf. A000720, A001462, A007097, A076078, A084422, A085945, A112798, A276625, A290689, A290822, A306844, A324764.
Cf. A324695, A324737, A324743, A324751, A324756, A324758.

Table[Length[Select[Subsets[Range[2,n]],Intersection[#,PrimePi/@First/@Join@@FactorInteger/@#]=={}&]],{n,10}]

pset(n)={my(b=0,f=factor(n)[,1]); sum(i=1, #f, 1<<(primepi(f[i])))}
a(n)={my(p=vector(n-1,k,pset(k+1)>>1), d=0); for(i=1, #p, d=bitor(d, p[i]));
((k,b)->if(k>#p, 1, my(t=self()(k+1,b)); if(!bitand(p[k], b), t+=if(bittest(d,k), self()(k+1, b+(1<Andrew Howroyd, Aug 16 2019

Terms a(21) and beyond from Andrew Howroyd, Aug 16 2019

A143327 Table T(n,k) by antidiagonals. T(n,k) is the number of primitive (=aperiodic) k-ary words (n,k >= 1) with length less than or equal to n which are earlier in lexicographic order than any other word derived by cyclic shifts of the alphabet.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 3, 5, 1, 1, 4, 11, 11, 1, 1, 5, 19, 35, 26, 1, 1, 6, 29, 79, 115, 53, 1, 1, 7, 41, 149, 334, 347, 116, 1, 1, 8, 55, 251, 773, 1339, 1075, 236, 1, 1, 9, 71, 391, 1546, 3869, 5434, 3235, 488, 1, 1, 10, 89, 575, 2791, 9281, 19493, 21754, 9787, 983, 1, 1, 11

Offset: 1

Alois P. Heinz, Aug 07 2008

The coefficients of the polynomial of row n are given by the n-th row of triangle A134541; for example row 4 has polynomial -1+k^2+k^3.

			T(3,3) = 11, because 11 words of length <=3 over 3-letter alphabet {a,b,c} are primitive and earlier than others derived by cyclic shifts of the alphabet: a, ab, ac, aab, aac, aba, abb, abc, aca, acb, acc.
Table begins:
  1,   1,    1,     1,     1,      1,      1,       1, ...
  1,   2,    3,     4,     5,      6,      7,       8, ...
  1,   5,   11,    19,    29,     41,     55,      71, ...
  1,  11,   35,    79,   149,    251,    391,     575, ...
  1,  26,  115,   334,   773,   1546,   2791,    4670, ...
  1,  53,  347,  1339,  3869,   9281,  19543,   37367, ...
  1, 116, 1075,  5434, 19493,  55936, 137191,  299510, ...
  1, 236, 3235, 21754, 97493, 335656, 960391, 2396150, ...

Alois P. Heinz, Antidiagonals n = 1..141, flattened
Index entries for sequences related to Lyndon words

Columns k=1-10 give: A000012, A085945, A320087, A320088, A320089, A320090, A320091, A320092, A320093, A320094.
Rows n=1-4 give: A000012, A000027, A028387, A003777.
Main diagonal gives A320095.
Cf. A143325, A143326, A134541, A008683.

with(numtheory):
f1:= proc (n) option remember; unapply(k^(n-1)
        -add(f1(d)(k), d=divisors(n) minus {n}), k)
     end:
g1:= proc(n) option remember; unapply(add(f1(j)(x), j=1..n), x) end:
T:= (n, k)-> g1(n)(k):
seq(seq(T(n, 1+d-n), n=1..d), d=1..12);

t[n_, k_] := Sum[k^(d-1)*MoebiusMu[j/d], {j, 1, n}, {d, Divisors[j]}]; Table[t[n-k+1, k], {n, 1, 12}, {k, n, 1, -1}] // Flatten (* Jean-François Alcover, Dec 13 2013 *)

T(n,k) = Sum_{j=1..n} Sum_{d|j} k^(d-1) * mu(j/d).
T(n,k) = Sum_{j=1..n} A143325(j,k).
T(n,k) = A143326(n,k) / k.

A276187 Number of subsets of {1,..,n} of cardinality >= 2 such that the elements of each counted subset are pairwise coprime.

Original entry on oeis.org

0, 1, 4, 7, 18, 21, 48, 63, 94, 105, 220, 235, 482, 529, 600, 711, 1438, 1501, 3020, 3211, 3594, 3849, 7720, 7975, 11142, 11877, 14628, 15459, 30946, 31201, 62432, 69855, 76126, 80221, 89820, 91611, 183258, 192601, 208600, 214231, 428502, 431573, 863188, 900563

Offset: 1

Robert C. Lyons, Aug 23 2016

nonn

n is prime if and only if a(n) = 2*a(n-1)+n-1. - Robert Israel, Aug 24 2016

			From _Gus Wiseman_, May 08 2021: (Start)
The a(2) = 1 through a(6) = 21 sets:
  {1,2}   {1,2}    {1,2}     {1,2}      {1,2}
          {1,3}    {1,3}     {1,3}      {1,3}
          {2,3}    {1,4}     {1,4}      {1,4}
         {1,2,3}   {2,3}     {1,5}      {1,5}
                   {3,4}     {2,3}      {1,6}
                  {1,2,3}    {2,5}      {2,3}
                  {1,3,4}    {3,4}      {2,5}
                             {3,5}      {3,4}
                             {4,5}      {3,5}
                            {1,2,3}     {4,5}
                            {1,2,5}     {5,6}
                            {1,3,4}    {1,2,3}
                            {1,3,5}    {1,2,5}
                            {1,4,5}    {1,3,4}
                            {2,3,5}    {1,3,5}
                            {3,4,5}    {1,4,5}
                           {1,2,3,5}   {1,5,6}
                           {1,3,4,5}   {2,3,5}
                                       {3,4,5}
                                      {1,2,3,5}
                                      {1,3,4,5}
(End)

Robert Israel, Table of n, a(n) for n = 1..340

Cf. A000010, A002088, A018805.
The case of pairs is A015614.
The indivisible instead of coprime version is A051026(n) - n.
Allowing empty sets and singletons gives A084422.
The relatively prime instead of pairwise coprime version is A085945(n) - 1.
Allowing all singletons gives A187106.
Allowing only the singleton {1} gives A320426.
Row sums of A320436, each minus one.
The maximal case is counted by A343659.
The version for sets of divisors is A343655(n) - 1.
A000005 counts divisors.
A186972 counts pairwise coprime k-sets containing n.
A186974 counts pairwise coprime k-sets.
A326675 ranks pairwise coprime non-singleton sets.
Cf. A007360, A063647, A186971, A302696, A305713, A320423, A320430, A326077, A327516, A337485.

f:= proc(S) option remember;
    local s, Sp;
    if S = {} then return 1 fi;
    s:= S[-1];
    Sp:= S[1..-2];
    procname(Sp) + procname(select(t -> igcd(t,s)=1, Sp))
end proc:
seq(f({$1..n}) - n - 1, n=1..50); # Robert Israel, Aug 24 2016

f[S_] := f[S] = Module[{s, Sp}, If[S == {}, Return[1]]; s = S[[-1]]; Sp = S[[1;;-2]]; f[Sp] + f[Select[Sp, GCD[#, s] == 1&]]];
Table[f[Range[n]] - n - 1, {n, 1, 50}] (* Jean-François Alcover, Sep 15 2022, after Robert Israel *)

f(n,k=1)=if(n==1, return(2)); if(gcd(k,n)==1, f(n-1,n*k)) + f(n-1,k)
a(n)=f(n)-n-1 \\ Charles R Greathouse IV, Aug 24 2016

from sage.combinat.subsets_pairwise import PairwiseCompatibleSubsets
def is_coprime(x, y): return gcd(x, y) == 1
max_n = 40
seq = []
for n in range(1, max_n+1):
    P = PairwiseCompatibleSubsets(range(1,n+1), is_coprime)
    a_n = len([1 for s in P.list() if len(s) > 1])
    seq.append(a_n)
print(seq)

a(n) = A320426(n) - 1. - Gus Wiseman, May 08 2021

Name and example edited by Robert Israel, Aug 24 2016

A324763 Number of maximal subsets of {2...n} containing no prime indices of the elements.

Original entry on oeis.org

1, 1, 2, 2, 2, 3, 6, 6, 6, 6, 10, 10, 16, 16, 16, 16, 24, 24, 48, 48, 48, 48, 84, 84, 84, 84, 84, 84, 144, 144, 228, 228, 228, 228, 228, 228, 420, 420, 420, 420, 648, 648, 1080, 1080, 1080, 1080, 1800, 1800, 1800, 1800, 1800, 1800, 3600, 3600, 3600, 3600, 3600

Offset: 1

Gus Wiseman, Mar 17 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.

			The a(1) = 1 through a(9) = 6 subsets:
  {}  {2}  {2}  {2,4}  {3,4}    {2,4,5}  {2,4,5}  {2,4,5,8}  {2,4,5,8}
           {3}  {3,4}  {2,4,5}  {3,4,6}  {2,5,7}  {2,5,7,8}  {2,5,7,8}
                                {4,5,6}  {3,4,6}  {3,4,6,8}  {3,4,6,8,9}
                                         {3,6,7}  {3,6,7,8}  {3,6,7,8,9}
                                         {4,5,6}  {4,5,6,8}  {4,5,6,8,9}
                                         {5,6,7}  {5,6,7,8}  {5,6,7,8,9}

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

The non-maximal version is A324742.
The version for subsets of {1...n} is A324741.
An infinite version is A304360.
Cf. A076078, A084422, A085945, A112798, A276625, A306844, A324764.
Cf. A324695, A324743, A324751, A324756, A324758, A324762.

maxim[s_]:=Complement[s,Last/@Select[Tuples[s,2],UnsameQ@@#&&SubsetQ@@#&]];
Table[Length[maxim[Select[Subsets[Range[2,n]],Intersection[#,PrimePi/@First/@Join@@FactorInteger/@#]=={}&]]],{n,10}]

pset(n)={my(b=0, f=factor(n)[, 1]); sum(i=1, #f, 1<<(primepi(f[i])))}
a(n)={my(p=vector(n-1, k, pset(k+1)>>1), d=0); for(i=1, #p, d=bitor(d, p[i]));
my(ismax(b)=my(e=0); forstep(k=#p, 1, -1, if(bittest(b,k), e=bitor(e,p[k]), if(!bittest(e,k) && !bitand(p[k], b), return(0)) )); 1);
((k, b)->if(k>#p, ismax(b), my(f=!bitand(p[k], b)); if(!f || bittest(d, k), self()(k+1, b)) + if(f, self()(k+1, b+(1<Andrew Howroyd, Aug 26 2019

Terms a(16) and beyond from Andrew Howroyd, Aug 26 2019

cp's OEIS Frontend

A224840 Divisor sum of the arithmetic function A085945(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

PARI

Formula

Extensions

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

A324736 Number of subsets of {1...n} containing all prime indices of the elements.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A324743 Number of maximal subsets of {1...n} containing no prime indices of the elements.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A324744 Number of maximal subsets of {1...n} containing no element whose prime indices all belong to the subset.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A324738 Number of subsets of {1...n} containing no element > 1 whose prime indices all belong to the subset.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A324742 Number of subsets of {2...n} containing no prime indices of the elements.

Views

Author