More digital silliness

[zak seidov]

--- Max Alekseyev <maxale at gmail.com> wrote:

> I've implementated this approach in PARI/GP (can
> share if anybody

Yes, Max, plz send this to me,

I found that there are exactly  766 pairs
{n<m<10^9) such that n^2 and m^2 are rotated squares;
the first is (12,21) => (144,441),
the last is (960599901, 990010596) =>
{922752169801209801, 980120980192275216},

Can you find all 10-digit pairs (n,m)?

thanks, zak



--- Max Alekseyev <maxale at gmail.com> wrote:
> 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
> 



      ____________________________________________________________________________________
Be a better friend, newshound, and 
know-it-all with Yahoo! Mobile.  Try it now.  http://mobile.yahoo.com/;_ylt=Ahu06i62sR8HDtDypao8Wcj9tAcJ