Problems & Puzzles: Puzzles

 Puzzle 363. A magnanimous company J. S. Madachy, in his nice "Madachy's Mathematical Recreations", on pp. 160-162 describes the Nelson's complete results about the factorization of the pandigital zero-less numbers such that the factors concatenated is another pandigital zero-less number. Examples: 48*2573916 = 123547968 4*6*8*93*7251 = 129473856 From the 2624 solutions available I rescue for this puzzle two outstanding results: 1) No solution exist with 6-9 factors, only with 2-5 factors. 2) There is one zero-less pandigital with 4 distinct factorizations: 169857324 = 36*4718259 = 3276*51849 = 4*91*567*823 = 6*7*54*91*823 Nelson programmed a computer (when before 1966?) in order to get these 2624 and Madachy ends his article this way: "It remains now for some magnanimous company to permit one of its computers to be programmed to determine all the 10 digit solutions to this problem" Well... we are that magnanimous company! Questions. 1. How many solutions of factorization for a 10 digits pandigital number, such that the concatenated factors is another 10 digits pandigital number? (please count separately per quantity of factors) 2. What is the 10 digits pandigital number with the most distinct factorizations of the asked type? 3. In doing so, please confirm the Nelson's results, 40 years old now.

Contributions came from Giovanni Resta.

***

The most surprising fact was that from the Resta results we learned that the Madachy stats for the zero-less pandigitals - as written in the page 160 of his book - were wrong: The Madachy/Nelson's total solutions were 2624 (as said above) while the Resta's solutions were 2900. [I can tell that I have confirmed the Resta's results using an independent code ran in my PC].

In the following Table are the detailed results Madachy's vs Resta, showing in red the discrepancies.

 Factors Model Qty M/N Total M/N Qty R Total R 2 A*BCDEFGHI 567 567 2 AB*CDEFGHI 342 342 2 ABC*DEFGHI 370 370 2 ABCD*EFGHI 346 1625 346 1625 3 A*B*CDEFGHI 87 87 3 A*BC*DEFGHI 210 210 3 A*BCD*EFGHI 244 244 3 A*BCDE*FGHI 109 109 3 AB*CD*EFGHI 0 99 3 AB*CDE*FGHI 52 205 3 ABC*DEF*GHI 39 741 39 993 4 A*B*C*DEFGHI 16 16 4 A*B*CD*EFGHI 55 55 4 A*B*CDE*FGHI 53 53 4 A*BC*DE*FGHI 59 59 4 A*BC*DEF*GHI 66 67 4 AB*CD*EF*GHI 0 249 23 273 5 A*B*C*D*EFGHI 0 0 5 A*B*C*DE*FGHI 3 3 5 A*B*C*DEF*GHI 1 1 5 A*B*CD*EF*GHI 5 5 5 A*BC*DE*FG*HI 0 9 0 9 6 A*B*C*D*E*FGHI 0 6 A*B*C*D*EF*GHI 0 6 A*B*C*DE*FG*HI 0 7 A*B*C*D*E*F*GHI 0 7 A*B*C*D*E*FG*HI 0 8 A*B*C*D*E*F*G*HI 0 9 A*B*C*D*E*F*G*H*I 0 2624 2900

The 2900 solutions were obtained by Resta in 40  minutes of computations [while my code used 22 minutes]. The 2900 Resta's solutions can be see at: http://www.imc.pi.cnr.it/resta/pan9.txt

Resta also computed the solutions for the 10 digits pandigital [again, his results were confirmed independently by me] and are available here:http://www.imc.pi.cnr.it/resta/pan10.txt

***

This is what Resta wrote:

...for the zero-less pandigitals, the format of the file is:

1 3 123459678 = 9*83*165274
1 4 123475896 = 9*34*562*718
1 4 123475968 = 4*87*512*693
2 3 123475968 = 24*87*59136
3 3 123475968 = 87*924*1536
1 3 123497568 = 19*864*7523

where the first number counts factorizations of the same number
(for example, above there are 3 factorizations of 123475968) and the second
number indicate how many factors.
So, at least according to my computation, there are 2900 factorizations
of 2728 distinct numbers. The 2900 factorizations are partitioned:
1625 -> 2 factors
993 -> 3 factors
273 -> 4 factors
9 -> 5 factors

There are 6 numbers which admit 4 factorizations, i.e.,
127359648, 132759648, 164759832, 169857324, 172349856, 419527836.
There are 19 numbers with 3 factorizations and 116 with 2 factorizations.

The complete log for the 10 digits factorizations can be seen at
http://www.imc.pi.cnr.it/resta/pan10.txt or, zipped, at
http://www.imc.pi.cnr.it/resta/pan10.zip

There are 24128 factorizations of 18548 distinct numbers.
The number of factors are
F | #
2 | 12449
3 | 8874
4 | 2711
5 | 94

The number which can be factorized in more ways is 1723498560
which has 16 factorizations, which derive all from the 4 factorizations
172349856 = 3*672*85491 = 6*7*84*92*531 = 8*92*413*567 = 46*72*98*531
adding a zero to one factor in all the possible ways, as in
1723498560 = 30*672*85491 = 3*6720*85491 = etc.etc.

If we consider only number non ending in 0, the number with more
factorizations, i.e. 6, is 1064938752, as stated in my first message.

If we search 10 digits factorizations of 9 digits numbers we
find some interesting results among these 10286 factorizations.
( http://www.imc.pi.cnr.it/resta/pan0.txt )

Indeed there are 3 numbers which admit 11 factorizations !
186347952 = 2*3*6*574*9018 = 2*9*574*18036 = 3*4*6*7*9*82*501
= 3*6*7*8*9*20541 = 3*7*8*9*246*501 = 3*9*82*167*504 = 4*6*7*9*82*1503
= 4*9*36*287*501 = 6*7*8*123*4509 = 6*18*492*3507 = 7*8*9*246*1503
the other 2 such numbers are 237659184 and 295184736.
F #
2 2159
3 3918
4 3628
5 554
6 26
7 1
---------------
where the number with 7 factors is the 186347952 = 3*4*6*7*9*82*501 already seen above.

I wrote a very simple and short program in c++ (the choice of c++ over c was only due to
the fact that there is a standard c++ library that perform permutations).
The program run on a PentiumD workstation, using only one of the two cores
the processor contains. The running time was about 40 minutes for the 9 digit
factorizations and about 18 hours for the 10 digit factorizations [my code spent 4 hours].
Using both cores I could have cut the time more or less in half, but I was not
in a hurry.
The program computes all the permutations of the string "0123456789", then
convert the string in a number N and compute recursively all the possible
factorizations, and every time a factorization is obtained it checks if it is pandigital.
The computations is speeded up thanks to the fact that all the factors
must be distinct and increasing and only one factor can exceed the square root of N.
A partial factorization is not pursued if it contains already a digit twice.
Since this program, written in few minutes, was enough to find all the solutions
in a reasonable time, I did not waste my time implementing more sophisticated algorithms.

***

 Records   |  Conjectures  |  Problems  |  Puzzles