Pandigital numbers were the topic of Problem 32 and here in Problem 38 of Project Euler we visit them again. The problem reads

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 = 576By 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) wheren> 1?

As we shall see the problem is pretty easy to solve once we do a bit of analysis. Doing the analysis will give us a really simple piece of code which needs to check only a few numbers.

## Analysis

First of all the fixed number must contain less than 5 digits, since *n* has to be greater than 1.

Second thing to not in our analysis is that we are given a candidate which starts with 9, so the fixed number we need to find needs to start with 9 as well which gives us some properties to use in the analysis.

If the fixed number is 2 digit we wont be able to generate a 9 digit number since n = 3 yields an 8 digit number and n=4 yields an 11 digit number. Same goes for 3 digit numbers where we end at 7 or 11 digits in the result. That leaves us with a four digit number starting with 9.

So already now we can limit the search to numbers between 9123 and 9876 a mere 753 numbers.

We can rather easily limit it a bit more. If the second digit is >4 then we get a carry over which results in the multiplying by 2 part will yield 19xxx instead of 18xxx and thus we have two 9’s which are not possible solutions. Further more non of the digits can be 1 since we will end up with a solution candidate with two 1’s in it.

So the solution space can be shrunk to numbers between 9234 and 9487 which means we would need to check 253 solutions.

## Algorithm

In the solution for problem 32 we built efficient algorithms for concatenating two longs and checking if a number is pandigital. We will reuse these functions, which leaves us with writing a piece of code that looks like

long result = 0; for (long i = 9387; i >= 9234; i--) { result = concat(i, 2*i); if(isPandigital(result)){ break; } }

This will give us a solution in 0ms on my computer giving the result

The largest pandigital product is 932718654 Solution took 0 ms

## Wrapping up

The solution for this problem was rather easy once the analysis hits the right track and coding the solution once you have figured it out was trivial.

As a curious fact there are 3 9 digit pandigital numbers that fulfill the rules of the exercise between 9234 and 9487. How many there are in total I don’t know.

The source code is available for download as always.

You can use the sw.Elapsed.TotalMilliseconds (where sw is StopWatch) to get a more precise timing. 🙂

Hi Freeman

Thanks for the comment. The API for C# is really big, so as usually when people point out stuff like that, I am completely unaware. So thanks for letting me know. I will have to test this a bit and see if I can improve precision in the measurement.

/Kristian

I also found out about that from someone else. And precise timing is awesome so I couldn’t abstain from sharing. 🙂 (it’s like ctrl+shift+esc or windows + break ^_^ )

Anyway, your posts of project Euler are great 😀 When I don’t know exactly how to do a problem in reasonable time or I just want to see a glimpse of a possible solution I refer here. 🙂

Thanks for the kind words. I am glad you like the blog. I must admit that I am doing it mostly for my own sake, since it forces me to get a deeper understanding of the problems that I would otherwise have needed. Plus I am getting tons of useful feedback from people like you.

So once again, thanks.

/Kristian

what did you mean that the fixed number has to be less than 5 digits since n > 1? I did not follow that reasoning. can you please elaborate?

We want to end up with a 9 digit number or less and we need to contatenate the final number from 2 or more numbers each of your numbers you are concatenating from needs to be 5 digits or less or else the final number will be too long.

[…] Kristian points out that the second digit in our upper limit must be < 5 otherwise the multiplication by 2 will yeild a nine, but a nine already exists in the first multiplication. We can’t have two. […]

For strict reasoning, the case of single digit (9, to be precise) should also included in the code in case that there were no such number that fulfills the requirements within the targeted four-digit range.

Shouldn’t the valid solution space be between 9234 and 9476 for the opposite logic used to discount the second digit from being >4, in that 8 is already used from 9*2?

You might be right. I am uncertain about it when reviewing the question. Can’t you come in a situation where you have a carryover from the previous digit, such that the 2*9 ends up as 19?

I think I worded my response poorly, I was referring to the situation where there would be two 8’s in the solution. What I meant was we know that a valid solution is 9xxx concatenated with 18xxx, so the remaining valid digits are 234567. The largest valid upper bound is then 9476 (< 9487) which is the largest value formed of the remaining valid digits less than your original upper bound.

As I saw your analysis, I thought of getting the upper bound further down:

You pointed at the possibility of (9…18…) becoming (94..18…).

At that point I did not agree as it would give an 8 or 9 right after the 8, which is not possible because those numbers are already used. Working with (93..18…) as upper bound would give a 6 or 7 right after the 8, which is possible. While trying to get a better upper bound, I ended up solving the problem by hand!

hi

there is a typo in your program. From your argumentation follows that the fo loop should start with i = 9487

regards g

I wrote a slightly more complicated program in C++. I found 18 numbers from 1 to 9999 (in ~8 ms on a 2.5 ghz laptop) that fit. It also said that 4780 (not included in count) was one but that one suffered from a rollover error. I only checked to make sure they weren’t negative (thus showing the error) or they weren’t 9 digits. Checking only the range you gave, it does it in ~0.9 ms

Table 1

List of 1 to 9 pandigital 9-digit numbers that can be formed

as the concatenated product of an integer with (1,2).

[Re: Project Eulet – Problem 38]

http://img15.hostingpics.net/pics/708178pe38tab1.jpg

Observations on the pandigital 9-digit numbers in Table 1.

Considering the pandigital 9-digit numbers in 9 columns:

Contents of columns 1 to 9:

Digits in column 1: 6, 7, 9

Digits in column 2: 2, 3, 6, 7, 9

Digits in column 3: 2, 3, 6, 7, 9

Digits in column 4: 2, 3, 7, 9

Digits in column 5: 1

Digits in column 6: 3, 4, 5, 8

Digits in column 7: 3, 4, 5, 6, 8

Digits in column 8: 3, 4, 5, 6, 8

Digits in column 9: 4, 6, 8

The four integers can be regrouped into “two permutation groups”:

Group 1: [2, 6, 7, 9]:

(6729, 6792, 6927, 7269, 7692, 9267)

Group 2: [2, 3, 7, 9]:

(7293, 7329, 7923, 7932, 9273, 9327)

___

Sources:

1) The integer digits of n joined to the integer digits of 2n contain each of the digits from 1 to 9 once.

http://oeis.org/A064160

2) Microsoft Office Excel (2007)

Table 1 in my previous comment shows a list of 1 to 9 pandigital 9-digit numbers that can be formed as the concatenated product of an integer with (1,2).

This list can be generated by using two algos: one from Kristian (1) and the other one from Sir Alan (2). Results are presented in Table 2 and 3

Table 2

1 to 9 pandigital 9-digit numbers that can be formed as the concatenated product of an integer with (1,2) using algo (1).

Table 3

1 to 9 pandigital 9-digit numbers that can be formed as the concatenated product of an integer with (1,2) using algo (2).

http://img11.hostingpics.net/pics/291134pe38table2and3.jpg

In Table 2, we finally reached a 9-digit number which is not a 1-9 pandigital.

In Table 3, the final 9-digit number is a 1-9 pandigital which is the product of 9 x (1,2,3,4,5)=918273645.

So both algorithms produce the 4-digit numbers 9327 and 9267 which (after permutations) multiply by one and two will produce the series of twelve 1-9-pandigital 9-digit numbers from the minimum 672913458 to the maximum 932718654 (Table 1 of the previous comment).

___

Sources:

1) Project Euler – Problem 38 (Kristian’s algorithm)

http://www.mathblog.dk/files/euler/Problem38.cs

2) Project Euler #38 (Sir Alan’s algorithm)

http://siralansdailyramble.blogspot.ca/2009/04/project-euler-38.html

3) Microsoft Visual C# 2010 Express

4) Microsoft Office Excel (2007)

another method could be :

#include<stdio.h>

#include<conio.h>

#include<iostream.h>

void main()

{

long int i,a,b,c,m1,m2,m3,m4,m5,m6,m7,m8,m9,l,m,n;

clrscr();

for(i=134;i<329;i++)

{

l=i;

m=2

i;i;n=3

a=l;b=m;c=n;

`m1=a%10;`

a=a/10;

m2=a%10;

a=a/10;

m3=a%10;

m4=b%10;

b=b/10;

m5=b%10;

b=b/10;

m6=b%10;

m7=c%10;

c=c/10;

m8=c%10;

c=c/10;

m9=c%10;

if(m1+m2+m3+m4+m5+m6+m7+m8+m9==45)

{

if(m1*m2*m3*m4*m5*m6*m7*m8*m9==362880)

cout<<l<<"\t"<<m<<"\t"<<n<<"\t";

}

}

`getch();`

}