[seqfan] Re: A086341
David Wilson
davidwwilson at comcast.net
Wed Nov 14 05:04:12 CET 2012
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/
>
More information about the SeqFan
mailing list