Problem 038

[Raveler]

The description of problem 38 http://projecteuler.net/index.php?secti ... lems&id=38is very, very confusing. The two initial examples indicate that the products need to be consecutive digits 1 through n (max 9), which would make sense. But the trivial example 987654321 does either the inverse (concatenates 1x9, 1x8, 1x7, ..., 1x1), indicating that the order is irrelevant, or does 987654321x1. In either case, I think the optimal solution to the problem would be 987654312x1, which does not seem to work. And as far as I can see my solution is conform the problem specification, so maybe it should be specified more clearly?

Thanks! I love the website.

[GraemeMcRae]

The question reads, "Excluding the trivial example, 987654321, what is the largest 1 to 9 pandigital number that can be formed this way?"

[Raveler]

You missed my point. Excluding 987654321, I'd say the second highest possible number is 987654312. Achieved by doing 987654312 x 1.

[ed_r]

You're right, it is poorly phrased. I can do no better than to quote, and agree with, what xenon said on the problem 38 solution topic:

987654321 is not the only 'trivial' number, 987654312 is another one. In fact all the permutations of the nine digits can be considered trivial.
I think the definition of non-trivial should be: the concatenation of at least two products. But that might be nit-picking...

[GraemeMcRae]

You missed my point.

D'oh!

[ed_r]

Hey, that's my line!





( Woo-hoo, I made Corporal! How much inanity do I need to post to make General, I wonder. )

[Raveler]

You're right, it is poorly phrased. I can do no better than to quote, and agree with, what xenon said on the problem 38 solution topic:

987654321 is not the only 'trivial' number, 987654312 is another one. In fact all the permutations of the nine digits can be considered trivial.
I think the definition of non-trivial should be: the concatenation of at least two products. But that might be nit-picking...

Thanks, this information helped me understand the problem. My suggestion (I guess that's what this forum is for) is to rephrase the problem and change it so that:
1. it's clearer that you need to concatenate products x1, x2, ... in order
2. you need to concatenate at least 2 products

[euler]

Good points, Raveler, and thanks for taking the time to mention it. I've changed the wording of the last sentence from
"Excluding the trivial example, 987654321, what is the largest 1 to 9 pandigital number that can be formed this way?"
to
"Excluding the trivial example, 1 [times] (any permutation of 987654321), what is the largest 1 to 9 pandigital number that can be formed this way?"

http://projecteuler.net/index.php?secti ... lems&id=38

I hope that makes it clearer.

[hk]

Aren't we excluding all pandigitals this way, so that the problem has no solution?
I think indeed that we must state that more than one product must be concatenated.
This reminds me of some other discussions...

[GraemeMcRae]

To address hk's concern, it might be necessary to introduce some terminology. For example,

Take the number 192, and multiply it by each of 1, 2, and 3:

    192 x 1 = 192
    192 x 2 = 384
    192 x 3 = 576

By concatenating each product we get the 1 to 9 pandigital, 192384576. We will call 192384576 the "concatenated product of 192 and (1,2,3)"

The same can be achieved by starting with 9 and multiplying by 1, 2, 3, 4, and 5, giving the pandigital, 918273645, which is the concatenated product of 9 and (1,2,3,4,5).

What is the largest 1 to 9 pandigital 9-digit number that can be formed as the concatenated product of an integer by at least two consecutive integers?

[rayfil]

And, in order to be more specific, that last sentence might be:

Code: Select all

What is the largest 1 to 9 pandigital 9-digit number that can be formed as the concatenated product of j>1 by at least two different integers?

Specifying a 9-digit number would remove any ambiguity as to numbers containing more than 9 digits but having all the digits from 1 to 9.
The j>1 removes the possibility of answers such as 1x9876 concatinated with 1x54321.
The "at least two different integers" does not put any restriction as to which integers as long as they are all different.

[GraemeMcRae]

Maybe my earlier last sentence too specifically described the form of the answer, so I took the liberty of editing my proposal and replacing the last sentence with yours, so that people reading this thread who have not yet solved the problem won't get unnecessarily specific hints.

However I'm concerned that the new last sentence is not specific enough. Doesn't it admit solutions such as 3 x (3292,18107) = 987654321 ?

Or one I particularly like: 4931 x (2,7) = 986234517

[rayfil]

You are absolutely right. The word "different" could be changed to "consecutive" which would disallow your examples. It would also remove the necessity of specifying j>1.

[euler]

I like the phrase "concatenated product of x and (a,b,c)".

This seems to work...

Take the number 192, and multiply it by each of 1, 2, and 3:

    192 x 1 = 192
    192 x 2 = 384
    192 x 3 = 576

By concatenating each product we get the 1 to 9 pandigital, 192384576. We will call 192384576 the "concatenated product of 192 and (1,2,3)"

The same can be achieved by starting with 9 and multiplying by 1, 2, 3, 4, and 5, giving the pandigital, 918273645, which is the concatenated product of 9 and (1,2,3,4,5).

What is the largest 1 to 9 pandigital 9-digit number that can be formed as the concatenated product of an integer with (1,2, ... , n) where n > 1?

[GraemeMcRae]

LOL, that's what I wrote before rayfil scared me off it! (I changed it because I thought it might give more hints than the original problem, and I didn't want to tip off the people who hadn't solved 38 yet.)

[euler]

I must say that although it is over four years ago that I wrote the problem I think that I always intended the examples given to suggest that it should be the product of an integer with the set of natural numbers 1, 2, 3, ... , n. However, inadvertently it seems that I'd created a more challenging problem with some people making it more difficult than I intended by trying out sets of consecutive integers not necessarily starting with one.

I know that compared with other problems it is fairly contrived - not as elegant and natural as some of the other problems - but I am ever aware of ensuring that the range of difficulty should be as large as possible and this one should rank in the easiest half of problems. I think that the new wording makes the purpose of the problem much clearer and more accessible, consequently placing it at the appropriate difficulty level.

[Raveler]

Thank you, the new problem description is much better. Up until where I'm now (problem 49) 38 has been the most confusing (but not most difficult).

there are some silly problems (such as 17, which is more annoying than challenging, took me a while to figure out I was using "fourty" instead of "forty", you tend to overlook it), but I liked most of them so far. Great fun.

[Reinderien]

In http://projecteuler.net/index.php?secti ... lems&id=38, one sees:
(1,2,3)
(1,2,3,4,5)
(1,2, ... , n)

Parentheses indicate open intervals. Shouldn't these intervals be closed? ie. with [ ]

Cheers.

[jaap]

They are not intervals (which only use 2 numbers in the notation).
They are n-tuples, i.e. ordered (multi-)sets.

[Reinderien]

Interesting, thanks.