cp's OEIS Frontend

A096202 Number of coverings of {1...n} by translation of a single set.

%I A096202 #19 Jun 09 2021 11:13:08
%S A096202 1,2,3,6,11,22,45,92,188,382,791,1632,3357,6922,14289,29542,61013,
%T A096202 126142,260664,538850,1113372,2300954,4752279,9814226,20257082,
%U A096202 41798206,86204773,177729712,366231907,754356336,1553063269,3196028942,6573883225,13515943986,27775807554
%N A096202 Number of coverings of {1...n} by translation of a single set.
%C A096202 The number of sets (up to translation) that with their translations can cover {1...n} in at least one way is given by A079500(n). For example, for n = 5 the 8 sets are {1}, {1,2}, {1,3}, {1,2,3}, {1,2,4}, {1,3,4}, {1,2,3,4}, {1,2,3,4,5}. - _Andrew Howroyd_, Nov 06 2019
%e A096202 a(5)=11 because the following are the 11 coverings of {1...5}, each one of which only uses a single set and its translations:
%e A096202    {{1},{2},{3},{4},{5}}
%e A096202    {{1,2},{3,4},{4,5}}
%e A096202    {{1,2},{2,3},{3,4},{4,5}}
%e A096202    {{1,2},{2,3},{4,5}}
%e A096202    {{1,3},{2,4},{3,5}}
%e A096202    {{1,2,3},{2,3,4},{3,4,5}}
%e A096202    {{1,2,3},{3,4,5}}
%e A096202    {{1,2,4},{2,3,5}}
%e A096202    {{1,3,4},{2,4,5}}
%e A096202    {{1,2,3,4},{2,3,4,5}}
%e A096202    {{1,2,3,4,5}}
%o A096202 (PARI)
%o A096202 covers(all, v)={
%o A096202   my(u=vector(#v+1)); for(i=1, #v, u[i+1]=bitor(u[i], v[i]));
%o A096202   my(recurse(k,b) = if(bitnegimply(b,u[k+1]), 0, if(k==0, 1, my(t=bitnegimply(b,v[k])); if(t==b, 2*self()(k-1, b), self()(k-1, b) + self()(k-1, t)) )));
%o A096202   recurse(#v, all)
%o A096202 }
%o A096202 a(n)={sum(i=2^(n-1), 2^n-1, covers(2^n-1, vector(valuation(i,2)+1, j, i>>(j-1))))} \\ _Andrew Howroyd_, Nov 06 2019
%Y A096202 Cf. A079500, A096154, A096203.
%K A096202 nonn
%O A096202 1,2
%A A096202 _Jon Wild_, Jul 27 2004
%E A096202 a(14)-a(32) from _Andrew Howroyd_, Nov 06 2019
%E A096202 a(33)-a(35) from _Jinyuan Wang_, Jun 09 2021