# [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 16:38:44 CEST 2009

```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)

and repeatedly apply the map

(n, k) => (3n+2k, 4n+3k)

This produces the pairs

(0, 1) => (2, 3) => (12, 17) => (70, 99) => ...

so that

f(0) = 1; f(2) = 3; f(12) = 17; f(70) = 99; etc.

zak seidov wrote:
> While OEIS on vacation...
>
> %N A1 In binary representation,
> a(n)^2  is the smallest square
> with n^2 as substring.
>
> %S 2,3,5,8,10,10,14,16,18,20,22,17,26,28,30,32,34,36,38,
> 40,42,44,46,40,50,52,54,56,58,60,62,64,66,68,70
>
> %C
> In most cases a(n)=a(n-1)+2 but the sequence is not monotonic:

In base 2 language

(2n)^2 = concat(n^2, "00")

This means a(n) <= 2n.

If n^2 is to be a numerically smaller substring of a(n)^2, that leaves
the following possibilities:

a(n)^2 = concat(1, n^2), satisfied by n = 3*2^k; a(n) = 5*2^k.

a(n)^2 = concat(

> the terms a(n) which are less than previous ones, a(n)<a(n-1), are:
> a(n)=17,40,80,99,160,320,640,577,1280,
> with corresponding n: 12,24,48,70,96,192,384,408,768.
>
> Q Are all n=12*k giving a(n)=40*k for k>2?

Actually, all n = 3*2^k give a(n) = 5*2^k for k >= 0.

```