[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.
More information about the SeqFan
mailing list