Problems & Puzzles:
Puzzle 308. AxB
= N =A'xB'
In certain page
of the solutions section of the beautiful book of Nobuyuki
Yoshigahara 'Puzzles 101', he wrote:
an amazing 0-9 computation. I'm not sure how anybody could have
5103 = 1463509782 = 479682 x 3051"
must be admiring is that:
pandigital (0-9) number has been found such that it can be expressed
in two ways a a product of two factors such that each pair of
factors contain again the ten distinct digits 0 to 9, PLUS
b) the curious
fact that the factors involved in one side are almost the
reverse of the factors in the other side, that is to say:
almost the reverse of 479682.
almost the reverse of 3051.
So, I will ask
for perfect examples of this type:
A x B = N =
A' x B'
1) A' is the
reverse of A & B' is the reverse of B
collection of digits in N is the same collection of digits in A&B
and also the same collection of digits in A'&B'
2886 x 93 =
268398 = 6882 x 39
disregard the condition 2), the earliest non trivial example is:
12 x 42 = 504 =
21 x 24
it can be
shown that there are infinite examples of this kind.
But what about
with the two conditions...?
1. Can you find
some more examples as for
2. Is there one
single example using all the digits 0 to 9 (repetitions permitted)?
Contributions came from J. C. Rosa, Faride Firoozbakht &
Giovanni Resta. I will show only these results where A & B are not
palindromes, or where B=A'. They (and also Faride Firoozbakht) found many
other interesting solutions of this type that fit the explicit conditions
but I think that they will forgiver to me for not showing them for the
sake of the good spirit of the original Nob's observation.
Nevertheless at the minimal complain from anybody of them I will show the
hidden results obtained by the complainer.
From my point of view, solutions for Q2 are still to be discovered.
J. C. Rosa wrote:
Question 1 : I found the following solutions
Giovanni Resta wrote:
Question 1 : I found the following
101909 * 99011 = 10090111999
215736 * 6312 = 1361725632
1560156 * 651 = 1015661556
found several solutions for Q2:
1479852 * 6930693 = 2589741 * 3960396 =
35471907 * 7723683 = 70917453 * 3863277 = 273973765073481
15723961572 * 806064 = 27516932751 * 460608 = 12674519360572608
3504242316 * 4689762 = 6132424053 * 2679864 = 16434062452368792
Here is the method I used.
We are searching for 4 numbers, say a, ra, b and rb, where ra =
reverse(a) and rb=reverse(b), such that a * b = ra * rb = m and m
contains exactly the digits of a and b.
Then we want to check if m is pandigital.
Let us fix a prime number p sufficently large (how much large will be
clear later on) and let us suppose that all the numbers a,b,ra,rb are
prime with p (that is, they are not divisible by p).
Then, in modular arithmetic, it must hold
a * b = ra*rb (mod p)
and since p is prime and a,b,ra,rb are not equal to 0 (mod p) we can
divide (modularly) both terms of the equation by ra*b obtaining
a / ra = rb / b (mod p)
a * ra^(-1) = rb * b^(-1) (mod p)
where with x^(-1) I denote the modular inverse of x, that is the
number y such that x*y=1 (mod p).
This means that if I'm considering a particular value a, with d = a*ra^(-1)
(mod p) then the "matching" b must satisfy
rb*b^(-1) = d (mod p).
Now I can describe my simple method.
I decided to check the couples a,b where a is unbounded and b is below
10,000,000=10^7 (this limit depends on the fact that I need to store a
lot of precomputed values...).
I choose a prime slightly larger that this bound,say p = 10,000,019.
I computed a table of modular inverses for all the numbers less than
10^7, to speed up subsequent calculations.
Then, for each value b>0 less than 10^7 I computed rb, I discarded the
palindromes (rb=b) and I computed the value
rb*b^(-1) = d (mod p). I stored this values in a vector of lists, in
such a way that, given a value d I could retrieve very fast the values
of b that give rise to that d.
I also stored the values of reverse(x) for each x<10^7, to speed up
things a little, but it was not really necessary.
The rest of the program is straightforward:
I consider the values of a=1,2,..... discarding those for which a or
ra are divisible by p. (One can always check this relatively few
remaining values, using the same program with another prime, but I was
For each value a I compute ra (and if a=ra I skip it, since I have
already discarded palindromes b).
Then I compute the value d=a*ra^(-1) (mod p).
Given this d I retrive the very few (if any!) candidates for b and I
check if a*b=ra*rb.
If this is the case I check if the condition on the digits also hold
and finally I check the pandigitaligy of a*b.
Since there are about p possible values for d then on the average
(roughly speaking) I have to check only one value b for every value a
and thus it is pretty fast with respect to a brute force approach.
The method trades memory for speed, and with some fantasy, can be
applied to similar problems in which in place of reverse() there is
another transformation of the digits.