cp's OEIS Frontend

A078881 Size of the largest subset S of {1,2,3,...,n} with the property that if i and j are distinct elements of S then i XOR j is not in S, where XOR is the bitwise exclusive-OR operator.

%I A078881 #22 Oct 01 2022 00:21:34
%S A078881 1,2,2,3,4,4,4,5,6,7,8,8,8,8,8,9,10,11,12,13,14,15,16,16,16,16,16,16,
%T A078881 16,16,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,32,32,32,32,
%U A078881 32,32,32,32,32,32,32,32,32,32,32,32,33,34,35,36,37,38,39,40,41,42,43,44
%N A078881 Size of the largest subset S of {1,2,3,...,n} with the property that if i and j are distinct elements of S then i XOR j is not in S, where XOR is the bitwise exclusive-OR operator.
%C A078881 Is this sequence the same as A006165?
%C A078881 The answer is yes, as shown by Hsien-Kuei Hwang, S Janson, TH Tsai (2016). More precisely, a(n) = A006165(n+1) for all n >= 1. - _N. J. A. Sloane_, Nov 26 2017
%C A078881 Can be formulated as an integer linear program: maximize sum {i = 1 to n} x[i] subject to x[i] + x[j] + x[i XOR j] <= 2 for all i < j, x[i] in {0,1} for all i. - _Rob Pratt_, Feb 09 2010
%C A078881 a(n) = A006165(n+1) checked for n <= 1023. - _Rob Pratt_, Dec 04 2014
%D A078881 Hsien-Kuei Hwang, S Janson, TH Tsai, Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications, Preprint, 2016; http://140.109.74.92/hk/wp-content/files/2016/12/aat-hhrr-1.pdf. Also Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585
%F A078881 a(n) = A006165(n+1) for all n >= 1. - _N. J. A. Sloane_, Nov 26 2017
%Y A078881 Cf. A078882.
%Y A078881 Same (apart from offset) as A006165.
%K A078881 nonn
%O A078881 1,2
%A A078881 _John W. Layman_, Dec 11 2002
%E A078881 More terms from _Rob Pratt_, Feb 09 2010