Вот такое интереснее: существует ли число (из как минимум двух цифр), все циклические перестановки цифр которого дают полные квадраты?
Для начала найдите хотя бы такое число, чтобы три его циклические перестановки (не начинающиеся с 0) были квадратами.
Вот кое-какая теория из давнишнего обсуждения в SeqFan:
Цитата:
---------- Forwarded message ----------
From: Max Alekseyev <***>
Date: Fri, Jan 11, 2008 at 10:40 PM
Subject: Re: More digital silliness
To: "David W. Wilson" <***>
Cc: Sequence Fans <***>
On Jan 9, 2008 11:33 AM, David W. Wilson <***> 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(m/d) < 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(m/d) < x, y, z < sqrt(m). Any such solution will give us the required 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 cardinality 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 in "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(m/d),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" solution (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 implemented 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 found.
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
---------- Forwarded message ----------
From: Max Alekseyev <***>
Date: Sat, Jan 12, 2008 at 6:16 PM
Subject: Re: More digital silliness
To: "David W. Wilson" <***>
Cc: Sequence Fans <***>
Corrections:
1) The number of square roots of any number b modulo m (where b and m are coprime) is 2^omega(m), where omega(m) is the number of distinct prime divisors of m, only if m is odd or the power of 2 in its prime factorization is 2 (i.e., valuation(m,2)=0 or valuation(m,2)=2 correspondingly). It is twice as much for valuation(m,2)>2 and twice as low for valuation(m,2)=1.
2) Solutions to the system of congruences:
y = x * r1 (mod m)
z = x * r2 (mod m)
may not be necessary coprime to m. Therefore, we need to go over all square divisors q^2 | m, solve the reduced system:
y' = x' * r1 (mod m/q^2)
z' = x' * r2 (mod m/q^2)
and let x = x' * q, y = y' * q, z = z' * q to get a solution to the original system.
This also has certain implication to the chance of the solution existence: it is larger for m with a large square divisor q^2, especially if m/q^2 and q are not coprime (ideally, q is square-free and m is divisible by q^3 such that gcd(m/q^2,q)=q).
Regards,
Max
таких, что 
и 
являются циклическими перестановками соответственно 
и 
.