login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A051026 Number of primitive subsequences of {1, 2, ..., n}. 30
1, 2, 3, 5, 7, 13, 17, 33, 45, 73, 103, 205, 253, 505, 733, 1133, 1529, 3057, 3897, 7793, 10241, 16513, 24593, 49185, 59265, 109297, 163369, 262489, 355729, 711457, 879937, 1759873, 2360641, 3908545, 5858113, 10534337, 12701537, 25403073, 38090337, 63299265, 81044097, 162088193, 205482593, 410965185, 570487233, 855676353 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

a(n) counts all subsequences of {1, ..., n} in which no term divides any other.  If n is a prime a(n) = 2*a(n-1)-1 because for each subsequence s counted by a(n-1) two different subsequences are counted by a(n): s and s,n.  There is only one exception: 1,n is not a primitive subsequence because 1 divides n.  For all n>1: a(n) < 2*a(n-1). - Alois P. Heinz, Mar 07 2011

Maximal primitive subsets are counted by A326077. - Gus Wiseman, Jun 07 2019

REFERENCES

Blanchet-Sadri, Francine. Algorithmic combinatorics on partial words. Chapman & Hall/CRC, Boca Raton, FL, 2008. ii+385 pp. ISBN: 978-1-4200-6092-8; 1-4200-6092-9 MR2384993 (2009f:68142). See p. 320. - N. J. A. Sloane, Apr 06 2012

LINKS

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

N. McNew, Counting primitive subsets and other statistics of the divisor graph of {1,2,..,n}, arXiv:1808.04923 (2018)

Eric Weisstein's World of Mathematics, Primitive Sequence

EXAMPLE

a(4) = 7, the primitive subsequences (including the empty sequence) are: (), (1), (2), (3), (4), (2,3), (3,4).

a(5) = 13 = 2*7-1, the primitive subsequences are: (), (5), (1), (2), (2,5), (3), (3,5), (4), (4,5), (2,3), (2,3,5), (3,4), (3,4,5).

From Gus Wiseman, Jun 07 2019: (Start)

The a(0) = 1 through a(5) = 13 primitive (pairwise indivisible) subsets:

  {}  {}   {}   {}     {}     {}

      {1}  {1}  {1}    {1}    {1}

           {2}  {2}    {2}    {2}

                {3}    {3}    {3}

                {2,3}  {4}    {4}

                       {2,3}  {5}

                       {3,4}  {2,3}

                              {2,5}

                              {3,4}

                              {3,5}

                              {4,5}

                              {2,3,5}

                              {3,4,5}

a(n) is also the number of subsets of {1..n} containing all of their pairwise products <= n as well as any quotients of divisible elements. For example, the a(0) = 1 through a(5) = 13 subsets are:

  {}  {}   {}     {}       {}         {}

      {1}  {1}    {1}      {1}        {1}

           {1,2}  {1,2}    {1,3}      {1,3}

                  {1,3}    {1,4}      {1,4}

                  {1,2,3}  {1,2,4}    {1,5}

                           {1,3,4}    {1,2,4}

                           {1,2,3,4}  {1,3,4}

                                      {1,3,5}

                                      {1,4,5}

                                      {1,2,3,4}

                                      {1,2,4,5}

                                      {1,3,4,5}

                                      {1,2,3,4,5}

Also the number of subsets of {1..n} containing all of their multiples <= n. For example, the a(0) = 1 through a(5) = 13 subsets are:

  {}  {}   {}     {}       {}         {}

      {1}  {2}    {2}      {3}        {3}

           {1,2}  {3}      {4}        {4}

                  {2,3}    {2,4}      {5}

                  {1,2,3}  {3,4}      {2,4}

                           {2,3,4}    {3,4}

                           {1,2,3,4}  {3,5}

                                      {4,5}

                                      {2,3,4}

                                      {2,4,5}

                                      {3,4,5}

                                      {2,3,4,5}

                                      {1,2,3,4,5}

(End)

MAPLE

with(numtheory):

b:= proc(s) option remember; local n;

      n:= max(s[]);

      `if`(n<0, 1, b(s minus {n}) + b(s minus divisors(n)))

    end:

bb:= n-> b({$2..n} minus divisors(n)):

sb:= proc(n) option remember; `if`(n<2, 0, bb(n) + sb(n-1)) end:

a:= n-> `if`(n=0, 1, `if`(isprime(n), 2*a(n-1)-1, 2+sb(n))):

seq(a(n), n=0..40);  # Alois P. Heinz, Mar 07 2011

MATHEMATICA

b[s_] := b[s] = With[{n=Max[s]}, If[n < 0, 1, b[Complement[s, {n}]] + b[Complement[s, Divisors[n]]]]];

bb[n_] := b[Complement[Range[2, n], Divisors[n]]];

sb[n_] := sb[n] = If[n < 2, 0, bb[n] + sb[n-1]];

a[n_] := If[n == 0, 1, If[PrimeQ[n], 2a[n-1] - 1, 2 + sb[n]]]; Table[a[n], {n, 0, 37}]

(* Jean-Fran├žois Alcover, Jul 27 2011, converted from Maple *)

Table[Length[Select[Subsets[Range[n]], SubsetQ[#, Select[Union@@Table[#*i, {i, n}], #<=n&]]&]], {n, 10}] (* Gus Wiseman, Jun 07 2019 *)

CROSSREFS

Cf. A007865, A054519, A096827, A103580, A303362, A305148.

Cf. A326023, A326076, A326077, A326081, A326082, A326083, A326117.

Sequence in context: A317688 A046703 A118722 * A028865 A053435 A096478

Adjacent sequences:  A051023 A051024 A051025 * A051027 A051028 A051029

KEYWORD

nonn,nice

AUTHOR

Eric W. Weisstein

EXTENSIONS

More terms from David Wasserman, May 02 2002

a(32)-a(37) from Donovan Johnson, Aug 11 2010

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 21 19:19 EDT 2019. Contains 328308 sequences. (Running on oeis4.)