Project Euler Forum

I'm having a bit of trouble with question 41.
Existance of an answer to this question implies that there exists a prime such that among all larger primes, none can be pandigital.
Or, simply, there exists a largest such n as defined in the question.

To me this proof is not trivial, but if it is, what have I missed?

What is the largest possible pandigital (as defined in this problem) number?

Yes, if we assume base 10, it seems to me more appropriate to write "pandigital" instead of "n-pandigital".

N-pandigital (to me) implies that there exists a largest n.

The way I understand the problem, n [le] 9

Ah, ok. Though I was more hoping for an elegant proof that a n-pandigital number with n > 9 cannot be prime... =)

but then the problem becomes more solvable, *cough* n < 8 *cough*...

According to the definition of a n-pandigital, there don't exist n-pandigitals in base b for n>=b.
Non-existant numbers can of course not be prime.
Isn't that an elegant proof or not?

PsssT wrote:Ah, ok. Though I was more hoping for an elegant proof that a n-pandigital number with n > 9 cannot be prime... =)

but then the problem becomes more solvable, *cough* n < 8 *cough*...

Ah, yes. The "A number is divisible by 3 iff the sum of digits is divisible by 3" theorem. Can you prove this theorem?

I started to spin off a bit from this problem.
If we allow any base to be used, is there a largest pandigital prime?
Though this might be very difficult to answer, a first approach would be just to show that the set of numbers that can't be written pandigitally in any base is finite (I don't know if it is, but intuitively I think not).
Could someone show me (if possible, the set might be finite) a way to design a number that can't be written pandigitally in any base for arbitrarily large numbers?

If you allow zeros, every n is 0-1-pandigital in base n, if you don't allow zeros, 4 is not 1-k-pandigital in any base.
But that probably doesn't help you much.
Obviously, for any base, the set of pandigital numbers is finite, so if there is any pandigital prime in base b, there's also a largest.
Now if we allow 0-k-pandigitals, every prime p is 0-1-pandigital in base p, that is boring, so let us disallow zeros and only consider 1-k-pandigitals.
Since a 1-k-pandigital in base b is &gt; b^k-1, if there are infinitely many bases which have pandigital primes, there are arbitrarily large pandigital primes. Now take any prime p &gt; 5 and let the base be b = [frac](p-1),2[/frac]. Then p = 2*b+1 = 21 in base b and p is 1-2-pandigital in base b. This is somewhat boring, too. It might become interesting if we only considered pandigitals with at least 3 digits in the base b representation.

If we do only consider pandigitals with at least three digits in the base b representation, then the set of numbers that can't be written pandigitally is indeed infinite. Unfortunately I only have an existence proof for this, so I don't know any way to actually construct such numbers. Anyway, the proof follows (read at your own peril):

--------------------------------------

In short, we're going to show that the number of numbers less than N that can possibly be expressed pandigitally is much smaller than N for sufficiently large N.

If we have a k-digit pandigital number, with digits d_1d_2d_3 ... d_k then by varying the base b, we can get all numbers of the form d_1b^(k-1)+d_2b^(k-2)+d_3b^(k-3)+...+d_k. Note that all such numbers are > b^(k-1), so if the number is less than N, b^(k-1) must be less than N. That gives us, at most, N^(1/(k-1)) numbers for each arrangement. There are k! arrangements, so we have k!*N^(1/(k-1)).

Now, note that b is at least k, so k^(k-1) must be less than N. Let k' be the largest k s.t. k^(k-1) < N. Now, we are summing (k!*N^(1/(k-1)) from k=3 to k=k'. Actually summing this would be a pain, so we'll make another observation - the function f(k) = k!*N^(1/(k-1)) is convex for k>1 (*). Now, since the maximum value of a convex function occurs at its endpoints, the sum is less than k' * f(k) for k = 3 or k = k'.

Now, if the maximum is at k=3, then f(k) is 6*N^(1/2), and since in order for 6*k'*N^(1/2) > N, k' would have to be on the order of sqrt(N), which is absurd seeing as k'^(k'-1) < N. So if the maximum is at k=k', then f(k) = k'!*N^(1/(k'-1)). Now, we assume that we take N large enough so that Stirling's approximation for k'! is reasonably good, and replace k'! with (k'/e)^k'. Now, f(k) = (k'^k')/(e^k') * N^(1/(k'-1)). Since k'^(k'-1) < N, k'^k' < N*k'. Also, we chose k' s.t. k'^(k'-1) < N and k' is maximal. So N^(1/(k'-1)) < k'+1. With these bounds, we get
f(k') < Nk'(k'+1)/e^k', and the bound for the sum we desire, k'*f(k') < Nk'^2(k'+1)/e^k'. Since the denominator is exponential, if we take sufficiently large values of k' (which is possible, by taking sufficiently large values of N), we can get k'*f(k') < N/a, for a>1 - in other words, we can get that for any a, for all sufficiently large N, the number of pandigital numbers less than N is less than N/a.

(*) You can probably show this by applying some approximation and then differentiation, but it also makes sense intuitively since first f(k) decreases since the N^(1/(k-1)) term is decreasing rapidly. Then, at some point, N^(1/(k-1)) starts stabilizing at around 1 and k! is still growing rapidly, so f(k) starts to increase again.

---------------------------

Meh, that was a pain to write up (and probably even more of a pain for anyone who tries to read it). But it should be correct, hopefully .

As for the prime thing, it's most probably true, but probably very very hard to show. Reason being, if you take almost any k-digit pandigital number, like 123, then there will probably be an infinity of bases in which b^2+2b+3 is prime. But if you could actually show that, then you would have made significant progress towards solving an open problem. Of course, you do have an infinite number of polynomials to choose from, which probably helps, but pandigital numbers are pretty random.

sajninredoc wrote:If we do only consider pandigitals with at least three digits in the base b representation, then the set of numbers that can't be written pandigitally is indeed infinite. Unfortunately I only have an existence proof for this, so I don't know any way to actually construct such numbers. Anyway, the proof follows (read at your own peril):

--------------------------------------

In short, we're going to show that the number of numbers less than N that can possibly be expressed pandigitally is much smaller than N for sufficiently large N.

If we have a k-digit pandigital number, with digits d_1d_2d_3 ... d_k then by varying the base b, we can get all numbers of the form d_1b^(k-1)+d_2b^(k-2)+d_3b^(k-3)+...+d_k. Note that all such numbers are > b^(k-1), so if the number is less than N, b^(k-1) must be less than N. That gives us, at most, N^(1/(k-1)) numbers for each arrangement. There are k! arrangements, so we have k!*N^(1/(k-1)).

Now, note that b is at least k, so k^(k-1) must be less than N. Let k' be the largest k s.t. k^(k-1) < N. Now, we are summing (k!*N^(1/(k-1)) from k=3 to k=k'. Actually summing this would be a pain, so we'll make another observation - the function f(k) = k!*N^(1/(k-1)) is convex for k>1 (*). Now, since the maximum value of a convex function occurs at its endpoints, the sum is less than k' * f(k) for k = 3 or k = k'.

Now, if the maximum is at k=3, then f(k) is 6*N^(1/2), and since in order for 6*k'*N^(1/2) > N, k' would have to be on the order of sqrt(N), which is absurd seeing as k'^(k'-1) < N. So if the maximum is at k=k', then f(k) = k'!*N^(1/(k'-1)). Now, we assume that we take N large enough so that Stirling's approximation for k'! is reasonably good, and replace k'! with (k'/e)^k'. Now, f(k) = (k'^k')/(e^k') * N^(1/(k'-1)). Since k'^(k'-1) < N, k'^k' < N*k'. Also, we chose k' s.t. k'^(k'-1) < N and k' is maximal. So N^(1/(k'-1)) < k'+1. With these bounds, we get
f(k') < Nk'(k'+1)/e^k', and the bound for the sum we desire, k'*f(k') < Nk'^2(k'+1)/e^k'. Since the denominator is exponential, if we take sufficiently large values of k' (which is possible, by taking sufficiently large values of N), we can get k'*f(k') < N/a, for a>1 - in other words, we can get that for any a, for all sufficiently large N, the number of pandigital numbers less than N is less than N/a.

(*) You can probably show this by applying some approximation and then differentiation, but it also makes sense intuitively since first f(k) decreases since the N^(1/(k-1)) term is decreasing rapidly. Then, at some point, N^(1/(k-1)) starts stabilizing at around 1 and k! is still growing rapidly, so f(k) starts to increase again.

---------------------------

Meh, that was a pain to write up (and probably even more of a pain for anyone who tries to read it). But it should be correct, hopefully .

As for the prime thing, it's most probably true, but probably very very hard to show. Reason being, if you take almost any k-digit pandigital number, like 123, then there will probably be an infinity of bases in which b^2+2b+3 is prime. But if you could actually show that, then you would have made significant progress towards solving an open problem. Of course, you do have an infinite number of polynomials to choose from, which probably helps, but pandigital numbers are pretty random.

I really like your approach! =)
Just to sum up:
k'*f(k') is an upper bound on how many pandigital numbers less than N there exists.
Since there are N numbers less than N, and according to the pigeon hole principle; If k'*f(k') < N some numbers (less than N) cannot be pandigital in any base.
If we can show k'*f(k') < N for all N > N' for some N'. This holds for arbitrarily many numbers.
This has now been shown. Have I understood your reasoning?

I started to dabble a bit in a similar way. But it seems as to achieve more than an existance proof is very difficult.

If we replace b in your original expression with N-x.
To construct N from this, we create the expression:
d_1(N-x)^(k-1)+d_2(N-x)^(k-2)+d_3(N-x)^(k-3)+...+d_k = N
For fixed k, to form a pandigital number, just choose d_1,d_2, ..., d_k to be exactly the set [1...k].
All positive integer solutions over x for a fixed N will be represent a pandigital representation.

If we define the problem Pandigital Representation (PR) as:
Given integers N and k determine wheter N can be represented as a k-pandigital in any base.

For k = 2, It's trivial. (any number larger than 4 can be written as 12 in some base).

For any other k, it's equivalent as to decide wheter a k-1 degree polynomial has a integer solution, for k! different polynomials.

To me it seems this is not even in NP, to show that none integer solutions exist, k! different polynomials must be checked. Or am I missing something?

To make it easier on the readers, I have replaced most of the formulas/equations with LaTeX images or slight alterations in the text to make it easier to read.

sajninredoc wrote:--------------------------------------

In short, we're going to show that the number of numbers less than N that can possibly be expressed pandigitally is much smaller than N for sufficiently large N.

If we have a k-digit pandigital number, with digits then by varying the base b, we can get all numbers of the form . Note that all such numbers are > , so if the number is less than N, must be less than N. That gives us, at most, numbers for each arrangement. There are k! arrangements, so we have .

Now, note that b is at least k, so must be less than N. Let k' be the largest k s.t. < N. Now, we are summing from k=3 to k=k'. Actually summing this would be a pain, so we'll make another observation - the function f(k) = is convex for k>1 (*). Now, since the maximum value of a convex function occurs at its endpoints, the sum is less than k' * f(k) for k = 3 or k = k'.

Now, if the maximum is at k=3, then f(k) is , and since in order for > N, k' would have to be on the order of &radic;N, which is absurd seeing as < N. So if the maximum is at k=k', then f(k) = . Now, we assume that we take N large enough so that Stirling's approximation for k'! is reasonably good, and replace k'! with . Now, f(k) = . Since < N, k'^k' < N*k'. Also, we chose k' s.t. < N and k' is maximal. So < k'+1. With these bounds, we get
f(k') < , and the bound for the sum we desire, k' * f(k') < . Since the denominator is exponential, if we take sufficiently large values of k' (which is possible, by taking sufficiently large values of N), we can get k' * f(k') < , for a>1 - in other words, we can get that for any a, for all sufficiently large N, the number of pandigital numbers less than N is less than .

(*) You can probably show this by applying some approximation and then differentiation, but it also makes sense intuitively since first f(k) decreases since the term is decreasing rapidly. Then, at some point, starts stabilizing at around 1 and k! is still growing rapidly, so f(k) starts to increase again.

---------------------------

Whew....I'm glad that's done....

PsssT wrote: I really like your approach! =)
Just to sum up:
k'*f(k') is an upper bound on how many pandigital numbers less than N there exists.
Since there are N numbers less than N, and according to the pigeon hole principle; If k'*f(k') < N some numbers (less than N) cannot be pandigital in any base.
If we can show k'*f(k') < N for all N > N' for some N'. This holds for arbitrarily many numbers.
This has now been shown. Have I understood your reasoning?

Right on.

PsssT wrote: I started to dabble a bit in a similar way. But it seems as to achieve more than an existance proof is very difficult.

If we replace b in your original expression with N-x.
To construct N from this, we create the expression:
d_1(N-x)^(k-1)+d_2(N-x)^(k-2)+d_3(N-x)^(k-3)+...+d_k = N
For fixed k, to form a pandigital number, just choose d_1,d_2, ..., d_k to be exactly the set [1...k].
All positive integer solutions over x for a fixed N will be represent a pandigital representation.

If we define the problem Pandigital Representation (PR) as:
Given integers N and k determine wheter N can be represented as a k-pandigital in any base.

For k = 2, It's trivial. (any number larger than 4 can be written as 12 in some base).

For any other k, it's equivalent as to decide wheter a k-1 degree polynomial has a integer solution, for k! different polynomials.

To me it seems this is not even in NP, to show that none integer solutions exist, k! different polynomials must be checked. Or am I missing something?

Yeah, it seems like in k the problem is O(k!). If we express the complexity in terms of N and k, though, we can get it down to O(N^(1/(k-1)), since we need N to have k digits in base b, which means that N>b^(k-1), so we need only try all b < N^(1/(k-1)) and check if the resulting representation is pandigital. But N is probably quite large compared to k, so it still makes the problem quite hard.

@elendiastarman: Thanks for the LaTeX!

Problem 041 (View Problem)

Hi all. I`m trying to solve the problem, but I`m running out of ideas. Any hint would be helpful.

Is it possible I haven`t understood what pandigital means? A number with distinct digits? That`s what I realised from problem description

it makes use of all the digits 1 to n exactly once.

But wikipedia states otherwise:

a pandigital number is an integer that in a given base has among its significant digits each digit used in the base at least once.

panther-tamer wrote:Problem 041 (View Problem)

Hi all. I`m trying to solve the problem, but I`m running out of ideas. Any hint would be helpful.

Is it possible I haven`t understood what pandigital means? A number with distinct digits? That`s what I realised from problem description

it makes use of all the digits 1 to n exactly once.

But wikipedia states otherwise:

a pandigital number is an integer that in a given base has among its significant digits each digit used in the base at least once.

For the purpose of solving this problem, use the definition given in the problem. Basically it has to be a permutation of the digits 1-n.

The same problem with the other definition would be much harder. It might not even have an answer (i.e. there probably are infinitely many primes that fit Wikipedia's definition of pandigital).

Is it about zeroless pandigitals?

I calculated the biggest number for both ways, zeroless and with-zero pandigitals, but euler didn't accept either answer.

I`m not sure how to ask further questions without posting spoilers. I`m pretty much clueless right now, I have no idea why my answers aren`t the right one. If someone would be willing to help me on PM, I would appreciate it much.

panther-tamer wrote:Is it about zeroless pandigitals?

Yes, neither the example nor the solution contains a 0.

I have solved it already, so you won't spoil anything by sending me a PM. I'll be happy to tell you what's wrong with your answer, presumably one of "not pandigital" (as defined in the problem), "not prime" or "not the largest".

Got it. It`s not enough that digits are distinct for number to be pandigital.

panther-tamer wrote:Got it. It`s not enough that digits are distinct for number to be pandigital.

Glad you solved it! Sorry I wasn't up early enough to answer your PM.

Hello all,
I'm new here at the project and trying to figuring out problem no 41, it's about finding the largest n-digit pandigital prime. I got from my calculation but it's wrong. I already test the nine digit numbers counting down from 987654321 into 123456789, and apparently they aren't any prime numbers in that range. So I tried the 8 digit, between 98765432 and 12345678 and it came that number....

Is there any range of numbers that I haven't covered?

regards