Problem 043

A place to air possible concerns or difficulties in understanding ProjectEuler problems. This forum is not meant to publish solutions. This forum is NOT meant to discuss solution methods or giving hints how a problem can be solved.
Forum rules
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.

This forum is NOT meant to discuss solution methods for a problem.

In particular don't post any code fragments or results.

Don't start begging others to give partial answers to problems

Don't ask for hints how to solve a problem

Don't start a new topic for a problem if there already exists one


See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
Post Reply
JasonMorand
Posts: 1
Joined: Mon Jun 10, 2013 10:28 pm

Problem 043

Post by JasonMorand »

Hello everyone. I recently found ProjectEuler.net and was excited to find all of the exercises on the site. I'm really terrible at math but I want to get better and hopefully this site can help me a little bit. I've been programming for a couple of years now so I'm still learning at that as well.
For some reason Problem 43 stuck out at me as a really cool pattern. So I decided to start with that one.
I've worked on it for a few hours and came up with a solution but it's way off so I was looking for a little guidance.

Please provide any feedback on my thought process.

1. I created a text file to hold all of the permutations for numbers 0-9. Which I believe is just 10! which comes out to ~ 3million numbers plus.
2. From there, I take each number from the file and look at d1,d2,d3 (set one). If this number is not divisible by two I get another number since there's no point in moving on with this number.
3. Once a number passes the first "test" I call another method that will recursively call itself, passing an incremented index for the sets of "triplets" (if that makes sense?)

i.e. The sample number is 1406357289 so set 1 = 406, set 2 = 063, set 3 = 635 and so on...

Am I on the right track? I'm getting over a million results so there's something I'm clearly missing. As I said I'm not very good at math so I don't see a pattern or an algorithm to this problem and I'm sort of guessing my way through it right now.

Any help would be appreciated. Thanks!!
User avatar
RishadanPort
Posts: 78
Joined: Mon Jun 10, 2013 7:31 am

Re: Problem 043

Post by RishadanPort »

First, -- This is just for clarifying the problem... not for helping with algorithms.

You don't need to store all permutations in a file, maybe you can think of a better way then that.
Image

Rishada is the gateway to free trade—but the key will cost you.
gtwreck
Posts: 2
Joined: Wed May 06, 2015 1:22 am

Problem 43

Post by gtwreck »

I have solved about 25 problems now, and decided to jump ahead and look at a few random ones. I haven't had any problem understanding a problem until problem 43. I came to this forum and got the clarifications that I need, but I don't think that should be necessary. The problem should probably be edited to fix the following:

1) Specify that zero cannot be the most significant digit. That is part of the definition of pandigital numbers, but I don't think that users should have to look that up to know it. Also, if someone codes up a solution without that knowledge, it could be pretty frustrating.

2) Clarify the "interesting sub-string divisibility property". Do those exact conditions need to be met? Can d1d2d3 be divisible by 2 instead of d2d3d4 (and then continue the pattern)? If so, does the last substring have to be divisible by 19?

Just my 2 cents.

Thanks!
TripleM
Posts: 382
Joined: Fri Sep 12, 2008 3:31 am

Re: Problem 043

Post by TripleM »

1) This is nothing to do with the pandigital property - you're told 'number', and by definition numbers simply cannot have leading zeroes. 0123456789 isn't a number - it's a string of ten digits. There are many times throughout Project Euler where basic facts like these aren't stated directly - doing so in every case would just make things too long-winded.

2) I can't really see this being unclear - you're told a property and asked to find numbers with 'this property' - not numbers with different but similar properties.

Someone will always be able to misinterpret a problem, with this forum covering anything else - I think it's as clear as it can be.
gtwreck
Posts: 2
Joined: Wed May 06, 2015 1:22 am

Re: Problem 043

Post by gtwreck »

1) Maybe, but the problem has "Sub-String" in the title. Also, the description takes sub-strings of the number, including "063", which is "divisible by 3". How can it be divisible by three if it isn't a number? I just don't think clarifying would hurt.

2) I still don't know the expected behavior here actually. Should the shift I mentioned be allowed and would it then need to include a number divisible by 19?

I agree, but this one seems pretty far off to me. Should be be necessary to come here to get clarity?
User avatar
mpiotte
Administrator
Posts: 1914
Joined: Tue May 08, 2012 5:40 pm
Location: Montréal, Canada

Re: Problem 043

Post by mpiotte »

Any problem statement can be written many different ways, and one may always argue it could be clearer. However, the real question is not whether it can be made clearer, but rather if it is ambiguous. After re-reading the question carefully, I can only see one reasonable interpretation, so it is not ambiguous in my opinion.
Image
DJohn
Posts: 63
Joined: Sat Oct 11, 2008 12:24 pm

Re: Problem 043

Post by DJohn »

gtwreck wrote: 2) I still don't know the expected behavior here actually. Should the shift I mentioned be allowed and would it then need to include a number divisible by 19?
No. The conditions are precisely those specified by the problem, not any others you choose to invent yourself. The question says that the three digit number formed by the second, third, and fourth digits is to be divisible by 2. If there was any requirement that anything be divisible by 19, the problem statement would have said that.
jon.kiparsky
Posts: 1
Joined: Tue Jul 08, 2014 7:17 pm

Re: Problem 043

Post by jon.kiparsky »

TripleM wrote:1) This is nothing to do with the pandigital property - you're told 'number', and by definition numbers simply cannot have leading zeroes.
It seems to me that your statement is simply not compatible with the description of the problem. As you can see from the problem statement itself, 063 is clearly considered an example of a number - after all, it's stated that it's "divisible by three", and I don't know of any other sort of thing which can have that sort of property.

I would agree that numbers considered as some sort of Platonic ideal do not have leading zeros or indeed any digits at all, but clearly we can represent them in many ways, and for the purposes of this problem a decimal representation, left-padded to three digits with zeros, is perfectly acceptable. It seems strange to me that a similar representation, left-padded to ten digits, is not considered a reasonable representation of a number in the very same problem.

(for the record, I'm not quite as worked up about this issue as gtwreck, but I did find the wording ambiguous, which is why I came to the board to find clarification - which I suppose I've now got, so, um, thanks, I guess. I'll go finish solving this problem now...)
User avatar
jaap
Posts: 554
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

Re: Problem 043

Post by jaap »

jon.kiparsky wrote:
TripleM wrote:1) This is nothing to do with the pandigital property - you're told 'number', and by definition numbers simply cannot have leading zeroes.
It seems to me that your statement is simply not compatible with the description of the problem. As you can see from the problem statement itself, 063 is clearly considered an example of a number - after all, it's stated that it's "divisible by three", and I don't know of any other sort of thing which can have that sort of property.
In the problem those are called sub-strings, not numbers, but does indeed then make the leap that such sub-strings can be divided, by treating them as if they were numbers and so turning the string "063" into the number 63. Generally in PE problems, numbers have no leading zeros, and if leading zeros are allowed they are not called numbers but digit strings. I agree that in this problem that distinction is not made quite as clear.
Post Reply