cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

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

This page as a plain text file.
%I A276187 #29 Sep 15 2022 09:06:14
%S A276187 0,1,4,7,18,21,48,63,94,105,220,235,482,529,600,711,1438,1501,3020,
%T A276187 3211,3594,3849,7720,7975,11142,11877,14628,15459,30946,31201,62432,
%U A276187 69855,76126,80221,89820,91611,183258,192601,208600,214231,428502,431573,863188,900563
%N A276187 Number of subsets of {1,..,n} of cardinality >= 2 such that the elements of each counted subset are pairwise coprime.
%C A276187 n is prime if and only if a(n) = 2*a(n-1)+n-1. - _Robert Israel_, Aug 24 2016
%H A276187 Robert Israel, <a href="/A276187/b276187.txt">Table of n, a(n) for n = 1..340</a>
%F A276187 a(n) = A320426(n) - 1. - _Gus Wiseman_, May 08 2021
%e A276187 From _Gus Wiseman_, May 08 2021: (Start)
%e A276187 The a(2) = 1 through a(6) = 21 sets:
%e A276187   {1,2}   {1,2}    {1,2}     {1,2}      {1,2}
%e A276187           {1,3}    {1,3}     {1,3}      {1,3}
%e A276187           {2,3}    {1,4}     {1,4}      {1,4}
%e A276187          {1,2,3}   {2,3}     {1,5}      {1,5}
%e A276187                    {3,4}     {2,3}      {1,6}
%e A276187                   {1,2,3}    {2,5}      {2,3}
%e A276187                   {1,3,4}    {3,4}      {2,5}
%e A276187                              {3,5}      {3,4}
%e A276187                              {4,5}      {3,5}
%e A276187                             {1,2,3}     {4,5}
%e A276187                             {1,2,5}     {5,6}
%e A276187                             {1,3,4}    {1,2,3}
%e A276187                             {1,3,5}    {1,2,5}
%e A276187                             {1,4,5}    {1,3,4}
%e A276187                             {2,3,5}    {1,3,5}
%e A276187                             {3,4,5}    {1,4,5}
%e A276187                            {1,2,3,5}   {1,5,6}
%e A276187                            {1,3,4,5}   {2,3,5}
%e A276187                                        {3,4,5}
%e A276187                                       {1,2,3,5}
%e A276187                                       {1,3,4,5}
%e A276187 (End)
%p A276187 f:= proc(S) option remember;
%p A276187     local s, Sp;
%p A276187     if S = {} then return 1 fi;
%p A276187     s:= S[-1];
%p A276187     Sp:= S[1..-2];
%p A276187     procname(Sp) + procname(select(t -> igcd(t,s)=1, Sp))
%p A276187 end proc:
%p A276187 seq(f({$1..n}) - n - 1, n=1..50); # _Robert Israel_, Aug 24 2016
%t A276187 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&]]];
%t A276187 Table[f[Range[n]] - n - 1, {n, 1, 50}] (* _Jean-François Alcover_, Sep 15 2022, after _Robert Israel_ *)
%o A276187 (Sage)
%o A276187 from sage.combinat.subsets_pairwise import PairwiseCompatibleSubsets
%o A276187 def is_coprime(x, y): return gcd(x, y) == 1
%o A276187 max_n = 40
%o A276187 seq = []
%o A276187 for n in range(1, max_n+1):
%o A276187     P = PairwiseCompatibleSubsets(range(1,n+1), is_coprime)
%o A276187     a_n = len([1 for s in P.list() if len(s) > 1])
%o A276187     seq.append(a_n)
%o A276187 print(seq)
%o A276187 (PARI) f(n,k=1)=if(n==1, return(2)); if(gcd(k,n)==1, f(n-1,n*k)) + f(n-1,k)
%o A276187 a(n)=f(n)-n-1 \\ _Charles R Greathouse IV_, Aug 24 2016
%Y A276187 Cf. A000010, A002088, A018805.
%Y A276187 The case of pairs is A015614.
%Y A276187 The indivisible instead of coprime version is A051026(n) - n.
%Y A276187 Allowing empty sets and singletons gives A084422.
%Y A276187 The relatively prime instead of pairwise coprime version is A085945(n) - 1.
%Y A276187 Allowing all singletons gives A187106.
%Y A276187 Allowing only the singleton {1} gives A320426.
%Y A276187 Row sums of A320436, each minus one.
%Y A276187 The maximal case is counted by A343659.
%Y A276187 The version for sets of divisors is A343655(n) - 1.
%Y A276187 A000005 counts divisors.
%Y A276187 A186972 counts pairwise coprime k-sets containing n.
%Y A276187 A186974 counts pairwise coprime k-sets.
%Y A276187 A326675 ranks pairwise coprime non-singleton sets.
%Y A276187 Cf. A007360, A063647, A186971, A302696, A305713, A320423, A320430, A326077, A327516, A337485.
%K A276187 nonn
%O A276187 1,3
%A A276187 _Robert C. Lyons_, Aug 23 2016
%E A276187 Name and example edited by _Robert Israel_, Aug 24 2016