[seqfan] Re: A086341

[David Wilson]

A perhaps cleaner proof.

Let x  > 0 be odd.

Then there exist unique odd j > 0 and n >= 2 that satisfy

         x = j*2^n + 1 if x == 1 (mod 4)
         x = j*2^n - 1 if x == 3 (mod 4)

In either case we have

         x = j*2^n +- 1

Squaring gives

         x^2 = j^2*2^(2n) +- j*2^(n+1) + 1
         = (j^2*2^(n-1) +- 1)*2^(n+1) + 1

Let k = j^2*2^(n-1) +- 1 and m = n + 1. Then we have

     x^2 = k*2^m + 1.

Notice that since n >= 2, 2^(n - 1) is even and so k is odd.

So now we have

             x^2 is Proth
     <=>  k*2^m + 1 is Proth
     <=>  k < 2^m                      (definition of Proth number, 
given that k is odd and m > 0)
     <=>  j^2*2^(n-1) +- 1 < 2^(n+1)
     <=>  j^2 +- 1/2^(n-1) < 4   (divide by 2^(n-1))
     <=>  j^2 < 4 + 1/2^(n-1)
     ==>  j^2 < 4 + 1                   (n >= 2)
     ==>  j <= 2
     ==>  j = 1                             (j > 0 is odd)
     ==>  x = 2^n +- 1

Thus a Proth square must be of form (2^n +- 1)^2 with n >= 2. In the 
other direction, it is easy to show that numbers of this form are indeed 
Proth squares, so this form characterizes Proth squares.

A086341 gives the numbers of form (2^n +- 1)^2 with n >= 1. If you 
remove the two initial terms, you get numbers of form (2^n +- 1)^2 with 
n >= 2, precisely the Proth squares, as you observed.

On 11/11/2012 7:54 AM, Uwe Lauth wrote:
> Hello,
>
> I suggest to add the following comment to A086341:
> "With the exception of 1,
> these are the integers whose squares are Proth numbers."
>
> Let me briefly describe this.
>
> Any odd integer can be written as n = k * 2^m + 1, with odd k.
> Proth numbers (A080075) are those where k < 2^m.
>
> Some Proth numbers are also square numbers:
> 9, 25, 49, 81, 225, 289, 961, ...
> I suggest to call them Proth squares.
>
> That sequence is not in the OEIS. But the sequence of their roots,
> 3, 5, 7, 9, 15, 17, 31, ...
> is A086341 where the first two numbers (1,3) are omitted.
>
> A086341 is the powers of 2, plus/minus 1.
> Their squares (with the exception of 1) are Proth numbers:
> (2^(m-1) +- 1)^2 = k * 2^m + 1  where  k = 2^(m-2) +- 1
>
> No other square can be a Proth number. To show that,
> write the root b = a * 2^(m-1) +- 1 (with m>1 and odd a).
> b^2 = k * 2^m + 1  where  k = a^2 * 2^(m-2) +- a
> k becomes "too big" already for a = 3, since 9 > 2^2.
>
> (Note: that proof does not work for the first few squares,
> but these can be verified by hand.)
>
> I verified this numerically up to b = 2^32-1.
>
> Another conclusion:
> The set of Proth squares is infinite.
>
> Kind regards,
> Uwe
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>