Problems & Puzzles:
Puzzles
Puzzle 115. Prime squares composed by no more
than two digits
Here
are the first eight primes with that property: 2,
3, 5, 7, 11, 109, 173 & 81619
Example:
81619^2
= 6661661161
Questions:
1.
Can you extend the sequence?
2.
Can you argue if this sequence is finite or infinite?
References.
F24, p.262.
UNiTN, R.K. Guy
Solution
Patrick
De Geest has sent (17/11/2000) the following Web links to this
problem:
Hisanori
Mishima, Ruskin
and
several Sloane's sequences: A057659,
A016069,
A016070,
A018884
& A018885
.
In
particular interesting is the range covered by the search of Mr.
Mishima. I have asked to Patrick please to ask him how is that
he covered that incredible large range. Hopefully we should have some news
soon about this issue.
***
Here
is the kind explanation of the Mishima's method explained by
himself according to an email he sent to me the 23/11/2000:
The search method for tridigital squares.
"tridigital square" means B=A^2 and B is consisted of
less than three different numbers.
There are two ways of searching such that
(method 1) loop of A.
* (11) A is moved within certain range.
Compute B=A^2.
* (12) Check whether B is tridigital or not.
(method 2) loop of B.
* (21) Fix the three different digits.
Construct B from these digits.
* (22) Compute square root of B as A in the set of real number.
* (23) Check whether A is integer or not.
At a glance, it seems that there are no differences between
method 1 and method 2. But in realty,
method 2 has a great advantage.
Let B be 2ndigits number. The square root of B [A] is consisted
of ndigit integer part and infinite fraction part. This ndigit integer
part [of A] depends only on upper ndigits part of B.
So when we perform in method 2 and construct three digits number
B, we need not 2ndigits three number, only make ndigits number and concatenate
n times zero.
More easily say, let B=A^2. We need not make B=ababaa....bba
(ndigits), just make B=ababa...b(n/2digits)00000..000(n/2digits).
So using refined method 2, the
search range becomes double length for B of method 2.
In case we want to search 2digits square by using this method,
first we must make two kind of sequences,
case 1 : including zero
0
a
a0
aa
a00
a0a
...
case 2 : nonzero
a
b
aa
ab
ba
bb
aaa
...
There is apparent correspondence between these sequences
and binary notation of integer n,
case 1 : including zero
0 : 0
a : 1
a0 : 10
aa : 11
a00 : 100
a0a : 101
...
(represent n as binary, and replace '1' by 'a'.)
case 2 : nonzero
a : 10
b : 11
aa : 100
ab : 101
ba : 110
bb : 111
aaa : 1000
...
(represent n as binary, omit uppermost [ leftmost ]^{ }bit,
and replace '0' by 'a', '1' by 'b'.)
(refined method 2) loop of B.
* (21) Fix the two different numbers.
Construct ndigits B from these numbers.
* (22) Concatinate n times zero.
* (23) Compute square root of B as a in integer number.
* (24) Add 1 to A.
* (25) Compute B=A^2.
* (26) Check whether B is 2digits or not.
And if we want to check (26), we need not perform
(25).
For example, let B assume consisting from 2 and 5. If B is perfect
square, the lower [ rightmost ] 3digits must be '225', so lower [
rightmost ] 3digits of A (B=A^2) must be,
015, 035, 065, 085, 115, ...
Therefore,
* (24) Add 1 to A.
* (25) Let C=A mod 1000.
* (26) If C is not 015, 035, 065, 085, 115, ... then
next A
* (27) Else compute B=A^2.
* (28) Check whether B is 2digits or not.
"(26)" can be computed only table searching.
Make the table T[1000],
* T[i]=0 (i=0, 999)
* T[15]=1, T[35]=1, ...
only check T[C]=0 or 1.
If we want to search up to B=10^48 in B=A^2, we must make
24lengths of , including zero : 3 patterns; nonzero : 18
patterns so, 3 * 2^25 + 18 * 2^26 = 1308622848. These are the required
search patterns. I made this computation using 486 DX2 66MHz, programmed
in UBASIC, and cost 2 or 4 days (perhaps 3 or 5 years ago). I performed
the search for tridigital square using same method up to B=10^34,
required search patterns are, including zero : 25 patterns nonzero : 67
patterns 25 * 3^18 + 67 * 3^19 = 87557030514. This is approximately 67
times of former computation. I made this search by using Pentium III 650
Mhz machine, programmed in UBASIC, cost about 2 months. If we proceed
the same computation on today's machine in the same time, 3 * 2^31 + 18
* 2^32 = 83751862272 is almost same to 87557030514, so we can search up
to 10^60 digits of B.
***
After the Mr. Mishima's search (without the
dispense of a desirable confirmation) seems that the next move with this
puzzle is not to try to get the next positive example . Maybe is
time to start arguing why no other example should come any more...
***
