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

 

Logo

Please make a donation to keep the OEIS running. We are now in our 55th year. In the past year we added 12000 new sequences and reached 8000 citations (which often say "discovered thanks to the OEIS"). We need to raise money to hire someone to manage submissions, which would reduce the load on our editors and speed up editing.
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A323192 Numbers x such that the binary complement of x is larger than the binary complement of x^2: A035327(x) > A035327(x^2). 2
181, 362, 724, 1448, 741455, 11863283, 99516432383215, 1592262918131443, 12738103345051545, 101904826760412361, 203809653520824722, 407619307041649444, 3260954456333195553, 6521908912666391106, 417402170410649030795, 1709679290002018430137083, 3419358580004036860274166 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,1

COMMENTS

Up to a(13) all the terms are of the form floor(sqrt(2^k-1)) for some k. - Giovanni Resta, Jan 07 2019

From Chai Wah Wu, Jan 10 2019: (Start)

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.

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).

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.

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.

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).

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).

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)).

Since k >= 2, sqrt(2^(2k-1)-2^k) = sqrt(2^(2k-1)(1-2^(1-k))) >= sqrt(0.5)*sqrt(2^(2k-1)). This implies that a-b < -1/2 + 2^k/((1+sqrt(0.5))*(sqrt(2^(2k-1)))) = 2sqrt(2)/(sqrt(2)+1) - 1/2 < 0.672. This implies that there is at most one integer between b and a.

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.

The criterion can be simplified as:

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.

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.

(End)

LINKS

Chai Wah Wu, Table of n, a(n) for n = 1..721

PROG

(Python)

for n in range(1, 20000000):

    b1 = (1 << n.bit_length()) - 1

    n2 = n*n

    b2 = (1 << n2.bit_length()) - 1

    if b1-n > b2-n2:  print str(n)+', ',

(Python)

from sympy import integer_nthroot

A323192_list = []

for k in range(1000):

    n = integer_nthroot(2**(2*k+1), 2)[0]

    if n*(n-1) + 2**(len(bin(n))-2) - 2**(len(bin(n**2))-2) > 0:

        A323192_list.append(n) # Chai Wah Wu, Jan 10 2019

CROSSREFS

Cf. A035327.

Sequence in context: A138397 A179484 A142258 * A142030 A267542 A082444

Adjacent sequences:  A323189 A323190 A323191 * A323193 A323194 A323195

KEYWORD

nonn,base,changed

AUTHOR

Alex Ratushnyak, Jan 06 2019

EXTENSIONS

a(7)-a(13) from Giovanni Resta, Jan 07 2019

a(14)-a(17) from Chai Wah Wu, Jan 10 2019

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 December 10 20:53 EST 2019. Contains 329909 sequences. (Running on oeis4.)