[seqfan] Re: A1: In binary representation, a(n)^2 is the smallest square with n^2 as substring.

[David Wilson]

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.