More digital silliness

[Max Alekseyev]

On Jan 9, 2008 11:33 AM, David W. Wilson <wilson.d at anseri.com> wrote:

> Let an n-digit number be valid if it does not start or end with 0.
> Let a rotation of n be gotten by rotating its digits. Thus the rotations of
> 256 are 256, 562 and 625.
> We note that 256 has two valid square rotations, 256 and 625.
> Is there a number with more than two valid square rotations?

Surprisingly, such numbers are related to the existence of "small"
solutions to some system of linear modular equations.
Below I will describe this connection and suggest a fast method for
finding such numbers.

Let d be the base of our numeral system (e.g., d=10). Suppose that the
number N consists of n digits, and the rotations are done by u, v, and
w digits so that n=u+v+w. Then there exist positive integers
a,b,c,x,y,z such that

a*d^(v+w) + b*d^w + c = x^2
b*d^(w+u) + c*d^u + a = y^2
c*d^(u+v) + a*d^v + b = z^2

where the numbers a*d^(v+w) + b*d^w + c, b*d^(w+u) + c*d^u + a,
c*d^(u+v) + a*d^v + b represents the three rotations of our number N
in the base d. The numbers a,b,c have in the base d the length u,v,w
correspondingly, i.e.:

d^(u-1) < a < d^u
d^(v-1) < b < d^v
d^(w-1) < c < d^w

implying that

d^(u+v+w-1) < x^2, y^2, z^2 < d^(u+v+w)
and
sqrt(d/m) < x, y, z < sqrt(m)

where m = d^(u+v+w) - 1.
This number m turns to be very important for finding a,b,c (or x,y,z)
since the system of equations above is equivalent to (multiplying the
first equation by d^u and subtracting the second etc.):

x^2 * d^u - y^2 = a * m
y^2 * d^v - z^2 = b * m
z^2 * d^w - x^2 = c * m

that is equivalent to the following system congruences:

y^2 = x^2 * d^u (mod m)
z^2 = x^2 * d^(u+v) (mod m)

We are interested in "small" solutions to this system, namely, that
satisfy sqrt(d/m) < x, y, z < sqrt(m). Any such solution will give us
the requiqed a,b,c whose concatenation in the base d is x^2, while the
concatenation of b,c,a is y^2 and the concatenation of c,a,b is z^2.

Let R1 and R2 be respectively the sets of all square roots of d^u and
d^(u+v) modulo m. Note that each of them is either empty (when the
corresponding power of d is not a square modulo m) or has multiplicity
2^omega(m), where omega(m) is the number of distinct prime divisors of
m.
If either of R1, R2 is empty, our system of congruences does not have
a solution, meaning that the required number does not exist for chosen
parameters d,u,v,w. Otherwise for every r1 from R1 and every r2 from
R2 we have a system of congruences:

y = x * r1 (mod m)
z = x * r2 (mod m)

where we still interested for "small" solutions. We can reformulate
this problem as Closest Vector Problem (CVP) to attack it with LLL
algorithm.

Namely, let C be the integer median of the interval
[sqrt(d/m),sqrt(m)] and let D be an integer half of its length, so
that the distance from every integer in this interval to C is at most
D. Then a "small" solutions (x,y,z) belongs to the lattice L(M)
generated by the columns of the following matrix

[ 1 m 0 0 ]
[ r1 0 m 0 ] = M
[ r2 0 0 m ]

and is close to the vector (C,C,C). Therefore, we need to find the
closest vector (x,y,z) to (C,C,C) in the lattice L(M), and if this
vector is close enough to (C,C,C), it will represent a required
"small" solution.

I've implementated this approach in PARI/GP (can share if anybody
wants to play with different bases) and for d=10 tested all numbers up
to the length n=u+v+w=30. No solutions have been find.

This approach also leads to the following theoretical estimate of the
chance that required number of the length n exists. Namely, it's
roughly:
4^omega(d^n - 1) / d^(n/2)
So, I think that for all bases d>=4 there exists only a finite number
of such numbers (unless there is some clear pattern).

Regards,
Max