[seqfan] Re: A1: In binary representation, a(n)^2 is the smallest square with n^2 as substring.
David Wilson
dwilson at gambitcomm.com
Tue Aug 18 23:19:55 CEST 2009
I wrote:
> Abbreviate a(n) = a.
>
> Let || be base 2 string concatenation.
>
> We are trying to solve
>
> n^2 is a substring of a^2, a > n.
>
> a(0) = 2 is what it is.
>
> For n > 0, we have
>
> a^2 = n^2 || 00 is satisfied by a = 2n > 0
>
> This implies a <= 2n, which leaves the following possibilities:
>
> [1] a^2 = 0 || n^2, satisfied by a = n.
> [2] a^2 = n^2 || 0, satisfied by a = n = 0.
> [3] a^2 = 1 || n^2, satisfied by n = 3*2^k, a = 5*2^k.
> [4] a^2 = n^2 || 1, satisfied by a^2 = 2n^2+1, n > 0.
>
> Since a > n, we reject [1] and [2]. This leaves
>
> a(n) = 2, if n = 0,
> 5*2^k, if n = 3*2^k,
> k, if k^2 = 2n^2+1
> 2n, otherwise.
>
> The only nontrivial part is solving k^2 = 2n^2+1. To do this, start with
>
> (n, k) = (0, 1)
>
> Should be (n, k) = (2, 3)
>
> and repeatedly apply the map
>
> (n, k) => (3n+2k, 4n+3k)
>
> This produces the pairs
>
> (0, 1) => (2, 3) => (12, 17) => (70, 99) => ...
>
> Should be (2, 3) => (12, 17) => (70, 99) => ...
>
> so that
>
> f(0) = 1; f(2) = 3; f(12) = 17; f(70) = 99; etc.
>
> Should be a(2) = 3; a(12) = 17; a(70) = 99; ...
Forgive me, I just dashed it off.
We do not have f(0) = 1 because 0 has an exceptional numeral. 0 should
be written as the null string, but mathematicians have this perverse
attachment to visible numerals, so it is given the exceptional numeral
"0". This causes 0 to have exceptional values in digit-related
sequences, which irritates us purists.
More information about the SeqFan
mailing list