# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/

Search: id:a323192
Showing 1-1 of 1

%I A323192 #36 Sep 22 2024 17:48:16
%S A323192 181,362,724,1448,741455,11863283,99516432383215,1592262918131443,
%T A323192 12738103345051545,101904826760412361,203809653520824722,
%U A323192 407619307041649444,3260954456333195553,6521908912666391106,417402170410649030795,1709679290002018430137083,3419358580004036860274166
%N A323192 Numbers x such that the binary complement of x is larger than the binary complement of x^2: A035327(x) > A035327(x^2).
%C A323192 Up to a(13) all the terms are of the form floor(sqrt(2^k-1)) for some k. - _Giovanni Resta_, Jan 07 2019
%C A323192 From _Chai Wah Wu_, Jan 10 2019: (Start)
%C A323192 The terms are numbers of the form floor(sqrt(2^(2k-1))) that are larger than 1/2 + sqrt(1/4 + 2^(2k-1) - 2^k) for some k > 0.
%C A323192 Theorem: if x is a term, then it is of the form floor(sqrt(2^(2k-1))) for some k > 0. In addition, floor(sqrt(2^(2k-1))) is a term if and only if it is larger than 1/2 + sqrt(1/4 + 2^(2k-1) - 2^k).
%C A323192 Proof: suppose x has k bits in its binary representation, i.e., 2^(k-1) <= x < 2^k. Then x^2 has either 2k-1 or 2k bits.
%C A323192 First we show that if x is a term of the sequence, then x^2 has 2k-1 bits. Suppose x^2 has 2k bits, i.e., x^2 >= 2^(2k-1). Then 2^2k - 1 - x^2 < 2^k - 1 - x. This is rearranged as x^2 - x + 2^k - 2^2k > 0. Solving this quadratic inequality leads to x > 2^k which contradicts the fact that x has k bits.
%C A323192 Thus x^2 < 2^(2k-1) and 2^(2k-1) - 1 - x^2 < 2^k - 1 - x. Solving this inequality and combining it with x < sqrt(2^(2k-1)) shows that x must satisfy sqrt(2^(2k-1)) > x > 1/2 + sqrt(1/4 + 2^(2k-1) - 2^k).
%C A323192 To complete the proof, we need to show that for each k, there is at most one integer satisfying this inequality. This is easily verified for k = 1. Assume that k > 1. Let a = sqrt(2^(2k-1)) and b = 1/2 + sqrt(1/4 + 2^(2k-1) - 2^k).
%C A323192 Using the identity sqrt(x) - sqrt(y) = (x-y)/(sqrt(x)+sqrt(y)) it follows that a-b = -1/2 + (2^k - 1/4)/(sqrt(2^(2k-1))+sqrt(1/4 + 2^(2k-1) - 2^k) < -1/2 + 2^k/(sqrt(2^(2k-1)) + sqrt(2^(2k-1)-2^k)).
%C A323192 Since k >= 2, sqrt(2^(2k-1)-2^k) = sqrt(2^(2k-1)(1-2^(1-k))) >= sqrt(1/2)*sqrt(2^(2k-1)). This implies that a-b < -1/2 + 2^k/((1+sqrt(1/2))*(sqrt(2^(2k-1)))) = 2*sqrt(2)/(sqrt(2)+1) - 1/2 < 0.672. This implies that there is at most one integer between b and a.
%C A323192 The above discussion also provides another characterization of the sequence. floor(sqrt(2^(2k-1))) is a term if and only if sqrt(2^(2k-1))-floor(sqrt(2^(2k-1))) < a-b where a-b is as defined above.
%C A323192 The criterion can be simplified as:
%C A323192 floor(sqrt(2^(2k-1))) is a term if and only if it is larger than 1/2 + sqrt(1/4 + 2^(2k-1) - 2^k). This concludes the proof.
%C A323192 Note that a-b -> 0.5 as k -> oo, i.e., for large k, the fractional part of sqrt(2^(2k-1)) should be less than about 0.5 in order for the integer part to be a term.
%C A323192 (End)
%H A323192 Chai Wah Wu, <a href="/A323192/b323192.txt">Table of n, a(n) for n = 1..721</a>
%o A323192 (Python)
%o A323192 for n in range(1,20000000):
%o A323192     b1 = (1 << n.bit_length()) - 1
%o A323192     n2 = n*n
%o A323192     b2 = (1 << n2.bit_length()) - 1
%o A323192     if b1-n > b2-n2:  print(str(n), end=', ')
%o A323192 (Python)
%o A323192 from sympy import integer_nthroot
%o A323192 A323192_list = []
%o A323192 for k in range(1000):
%o A323192     n = integer_nthroot(2**(2*k+1),2)[0]
%o A323192     if n*(n-1) + 2**(len(bin(n))-2) - 2**(len(bin(n**2))-2) > 0:
%o A323192         A323192_list.append(n) # _Chai Wah Wu_, Jan 10 2019
%Y A323192 Cf. A035327.
%K A323192 nonn,base
%O A323192 1,1
%A A323192 _Alex Ratushnyak_, Jan 06 2019
%E A323192 a(7)-a(13) from _Giovanni Resta_, Jan 07 2019
%E A323192 a(14)-a(17) from _Chai Wah Wu_, Jan 10 2019

# Content is available under The OEIS End-User License Agreement: http://oeis.org/LICENSE