wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Pandigital Products
        
(Message started by: Sir Col on Jun 13^th, 2003, 11:05am)

Title: Pandigital Products
Post by Sir Col on Jun 13^th, 2003, 11:05am

^{I'm not sure if this is better suited to 'cs' problems, but I'll post it here anyway...}

We shall call 30576 a 0 to 9 pandigital product, because it can be factored in such a way that is uses all the digits 0 to 9: 30576 = 8 x 42 x 91. Similarly, 364 is a 1 to 7 pandigital product, as 364 = 1 x 7 x 52.

1. What is the smallest pandigital product?
2. Find the smallest n for which you can form a 1 to n pandigital product.
3. How many 1 to 9 pandigital products can you find?
4. What about 0 to 9 pandigital products?

Title: Re: Pandigital Products
Post by wowbagger on Jun 13^th, 2003, 11:32am

on 06/13/03 at 11:05:36, Sir Col wrote:

2. Find the smallest n for which you can form a 1 to n pandigital product.

How about n=[hide]4[/hide]?

Title: Re: Pandigital Products
Post by Sir Col on Jun 13^th, 2003, 11:36am

The product being... ? ::)

Okay, it was trivial, so I suppose the obvious question to ask is, what is the next smallest n and what is the product?

Title: Re: Pandigital Products
Post by THUDandBLUNDER on Jun 13^th, 2003, 2:17pm

Oh, wait till Leonid sees this one. :D

Nitpick: "...it uses all the digits" once only.

3)
: [hide]

4396 = 28 x 157
5346 = 18 x 297
5346 = 27 x 198
5796 = 42 x 138
5796 = 12 x 483
5986 = 2 x 41 x 73
7254 = 39 x 186
7632 = 48 x 159 [/hide]
:
4) Are leading zeroes allowed?
:[hide]
28651 = 7 x 4093
: [/hide]

Title: Re: Pandigital Products
Post by Sir Col on Jun 13^th, 2003, 4:01pm

Good point, T&B: yes, "...uses the digits once and only once." :)

Nice work on 3#, but there are more. In fact there are more 1 to 9 pandigital products that can be written as a product of 3 factors than 2. And, as you would expect, there are lots more for #4. Out of interest, how did you find them? Some combination of computer, trial and/or analysis?

Title: Re: Pandigital Products
Post by Chronos on Jun 13^th, 2003, 11:55pm

Quote:

We shall call 30576 a 0 to 9 pandigital product, because it can be factored in such a way that is uses all the digits 0 to 9: 30576 = 8 x 42 x 91.

I think I'm totally missing the point here... 8 x 42 x 91 does not use 0, 3, 5, 6, nor 7. Similar problems occur for the second example, though I can see that neither reuses a digit. Further, it seems like n! is a 1 to n pandigital product, for n < 10 (I'm not sure what it would mean for n to be greater than 10).

Could anyone care to enlighten me?

Title: Re: Pandigital Products
Post by THUDandBLUNDER on Jun 14^th, 2003, 2:35am

Quote:

Out of interest, how did you find them?

During my 'research'. ;)

Quote:

I think I'm totally missing the point here... 8 x 42 x 91 does not use 0, 3, 5, 6, nor 7.

OK, his wording was not so accurate, but his meaning is discernible by inspection.
He means that the digits of the number - together with the digits of its factors -
use all the digits 0-9 once, and once only.

Title: Re: Pandigital Products
Post by Sir Col on Jun 14^th, 2003, 4:30am

I thought the meaning was clear, but I'll restate it:

We shall call A a 1 to n pandigital product if it can be factored in such a way that the equality A=f₁ x f₂ x ... x f_m contains all the digits 1 to n once and only once.

I forgot to answer your other question, T&B: no, you cannot include leading zeroes.

Title: Re: Pandigital Products
Post by Leonid Broukhis on Jun 14^th, 2003, 9:44am

I'm not sure if I have time to use my brute force toward this problem, but I'd like to point out that factoring of a number never includes 1 as one of the factors.
If you want to include 1, you need to call them divisors.

Title: Re: Pandigital Products
Post by Sir Col on Jun 14^th, 2003, 10:09am

Good point, Leonid.

I'm not sure if brute force alone will help much in solving this problem. Unless you apply an efficient algorithm your computer could spend a long time churning through possibilities. I know with problems like this that standards/benchmarks are difficult to determine, but to give others something to work around, the algorithm I wrote found all the solutions for 0 to 9 pandigital products in less than 3 minutes. For your reference I used VB6 and ran it on a P4 -1.8GHz processor with 512MB RAM.

Title: Re: Pandigital Products
Post by Chronos on Jun 17^th, 2003, 4:00pm

Can I use the excuse that I was posting that really late at night, and my brain wasn't working properly? I really should have seen that.

Title: Re: Pandigital Products
Post by Lightboxes on Aug 6^th, 2003, 10:06pm

The only next smallest n I could get is:
[hide] 162 = 54 * 3[/hide]

Title: Re: Pandigital Products
Post by Sir Col on Aug 7^th, 2003, 4:40am

For reference:
::
[hide]1 to 4 pandigitals...
3 x 4 = 12
1 solution

1-5 pandigitals...
4 x 13 = 52
1 solution

1-6 pandigitals...
3 x 54 = 162
1 solution

1-7 pandigitals...
0 solutions

1-8 pandigitals...
3 x 582 = 1746
6 x 453 = 2718
24 x 57 = 1368
34 x 52 = 1768
37 x 58 = 2146
58 x 64 = 3712
6 solutions

1-9 pandigitals...
4 x 1738 = 6952
4 x 1963 = 7852
12 x 483 = 5796
18 x 297 = 5346
27 x 198 = 5346
28 x 157 = 4396
39 x 186 = 7254
42 x 138 = 5796
48 x 159 = 7632
9 solutions
[/hide]::

Of course, there is nothing to stop you using more than two factors. ;)

Title: Re: Pandigital Products
Post by Icarus on Aug 7^th, 2003, 6:02pm

on 06/13/03 at 11:05:36, Sir Col wrote:

Similarly, 364 is a 1 to 7 pandigital product, as 364 = 1 x 7 x 52.

on 08/07/03 at 04:40:11, Sir Col wrote:

1-7 pandigitals...
0 solutions

Have the rules of arithmetic changed in the last 2 months, so that 1x7x52 != 364 anymore?

Title: Re: Pandigital Products
Post by Sir Col on Aug 7^th, 2003, 6:57pm

Not forgetting, 1 x 6 x 57 = 342. :)

Interestingly, the first 1-n pandigial product made up of 3 factors is for n=7, of which there are two examples.

There are no pandigital products made up of three factors for n=8, but for n=9 there are are 35!

After that there are only two that are made up of 4 factors, one for n=8 and one for n=9:
1 x 3 x 8 x 24 = 576
1 x 6 x 9 x 47 = 2538