# [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.

```