login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

Number of subsets of {1..n} containing no differences or quotients of pairs of distinct elements.
6

%I #21 Oct 24 2020 02:30:54

%S 1,2,3,5,7,12,18,31,46,72,102,172,259,428,607,989,1329,2142,3117,4953,

%T 6956,11032,15321,23979,33380,48699,66849,104853,144712,220758,304133,

%U 461580,636556,973843,1316513,1958828,2585433,3882843,5237093,7884277,10555739,15729293

%N Number of subsets of {1..n} containing no differences or quotients of pairs of distinct elements.

%H Fausto A. C. Cariboni, <a href="/A326490/b326490.txt">Table of n, a(n) for n = 0..90</a>

%F For n > 0, a(n) = A326495(n) + 1.

%e The a(0) = 1 through a(6) = 18 subsets:

%e {} {} {} {} {} {} {}

%e {1} {1} {1} {1} {1} {1}

%e {2} {2} {2} {2} {2}

%e {3} {3} {3} {3}

%e {2,3} {4} {4} {4}

%e {2,3} {5} {5}

%e {3,4} {2,3} {6}

%e {2,5} {2,3}

%e {3,4} {2,5}

%e {3,5} {2,6}

%e {4,5} {3,4}

%e {3,4,5} {3,5}

%e {4,5}

%e {4,6}

%e {5,6}

%e {2,5,6}

%e {3,4,5}

%e {4,5,6}

%t Table[Length[Select[Subsets[Range[n]],Intersection[#,Union[Divide@@@Reverse/@Subsets[#,{2}],Subtract@@@Reverse/@Subsets[#,{2}]]]=={}&]],{n,0,10}]

%o (PARI)

%o a(n)={

%o my(recurse(k, b)=

%o if(k > n, 1,

%o my(t = self()(k + 1, b));

%o for(i=1, k\2, if(bittest(b,i) && (bittest(b,k-i) || (!(k%i) && bittest(b,k/i))), return(t)));

%o t += self()(k + 1, b + (1<<k));

%o t);

%o );

%o if(n, recurse(2, 0)) + 1;

%o } \\ _Andrew Howroyd_, Aug 25 2019

%Y Subsets without difference are A007865.

%Y Maximal subsets without differences or quotients are A326491.

%Y Subsets without quotients are A327591.

%Y Subsets with differences and quotients are A326494.

%Y Cf. A051026, A054519, A325860, A326023, A326079, A326489.

%K nonn

%O 0,2

%A _Gus Wiseman_, Jul 09 2019

%E a(19)-a(41) from _Andrew Howroyd_, Aug 25 2019