Problem 162

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.
User avatar
hk
Administrator
Posts: 10563
Joined: Sun Mar 26, 2006 9:34 am
Location: Haren, Netherlands

Re: Problem 162

Post by hk » Wed Jun 08, 2011 11:00 am

Lord_Farin wrote: As for the question itself, it might be better asked in the Programming Languages section (mods?)
Yes, but will Waldowski find it back there?
Image

Waldovski
Posts: 27
Joined: Thu Jul 08, 2010 10:11 am

Re: Problem 162

Post by Waldovski » Wed Jun 08, 2011 8:33 pm

First off, thank you Lord_Farin for the answer.

Second, I apologise for not noticing the Programming Languages section. I should have checked first. But I still feel there is justification for asking the question here, as the context is the problem. In any case, I apologise again.

oleglyamin
Posts: 38
Joined: Mon Aug 08, 2011 7:49 am

Re: Problem 162

Post by oleglyamin » Wed Sep 14, 2011 4:51 pm

Could someone post answer for the case of "at most 5 digits", please?

EDIT: Not needed any more. I have very peculiar situation here - answers up to and including "at most 13 digits" are correct, but after that start to differ - at 14 digits by only 6, at 16 digits by ~2000. I thought it had something to do with rounding (you can have that in c# while raising numbers to power), so I made it round-proof, but the error stays. Very interesting. :)

EDIT2: Managed to make my answer coincide with the correct one at 14 digits. Now they differ by only 36 at 15 digits and ~600 at 16 digits. I guess chances are virtually zero that my algorithm is fundamentally wrong - has to be some precision problem.

EDIT3: Problem solved. But this is stupid. Spending an hour or more on overflow issues, rounding, etc.. But as a reward, I guess, it takes less than 10ms for my program to deliver the answer.

mdean
Posts: 154
Joined: Tue Aug 02, 2011 1:05 am

Re: Problem 162

Post by mdean » Thu Oct 27, 2011 10:20 am

daniel.is.fischer wrote:How many 4-digit (decimal) numbers are there containing the digits 0 and 1?
According to your first post there would be (4-1)*(4-1)*102 = 900.
But you've counted 1001 several times:
1) place 0 in second place, then 1 in first, fill remaining places
2) place 0 in second place, then 1 in last, fill
3) place 0 in third place, 1 in first, fill
4) place 0 in third place, 1 in last, fill.
Actually, there are only 703 decimal 4-digit numbers containing the digits 0 and 1.
I got 703 doing this by hand. I programmed the same method for this problem, but I can't seem to get the answer correct. Is there anyone I can PM with my numbers for 11-16 digit numbers?

Err... and how do you PM someone anyway? Last PM I tried to send seems to be stuck in my outbox. Is there a way to actually send it or does it stay marked this way until the person reads it?

Edit: cancel that. Seems I misread the problem badly and was counting the number that contained all the digits 0-A at least once...
Image

User avatar
PurpleBlu3s
Posts: 73
Joined: Mon Sep 19, 2011 5:49 pm

Re: Problem 162

Post by PurpleBlu3s » Sat Oct 29, 2011 5:15 pm

For 5 digits, is 16260 correct or very close?
Image

thundre
Posts: 356
Joined: Sun Mar 27, 2011 9:01 am

Re: Problem 162

Post by thundre » Sun Oct 30, 2011 11:50 am

PurpleBlu3s wrote:For 5 digits, is 16260 correct or very close?
Wrong radix, I think. "Give your answer as a hexadecimal number."

If treated as a decimal number, that answer is wrong at the second digit.
Image

User avatar
PurpleBlu3s
Posts: 73
Joined: Mon Sep 19, 2011 5:49 pm

Re: Problem 162

Post by PurpleBlu3s » Sun Oct 30, 2011 12:06 pm

thundre wrote:
PurpleBlu3s wrote:For 5 digits, is 16260 correct or very close?
Wrong radix, I think. "Give your answer as a hexadecimal number."

If treated as a decimal number, that answer is wrong at the second digit.
Yeah that was the decimal version. I thought I was very close to a formula for the answer, but I guess not then. :<
Image

User avatar
PurpleBlu3s
Posts: 73
Joined: Mon Sep 19, 2011 5:49 pm

Re: Problem 162

Post by PurpleBlu3s » Sun Oct 30, 2011 2:25 pm

Is 10190 correct for at least 5 digits? (Making sure my brute force test works.)

EDIT: Nevermind - solved now.
Image

ymersvennson
Posts: 11
Joined: Wed Aug 24, 2011 11:44 am

Re: Problem 162

Post by ymersvennson » Thu Jan 19, 2012 11:47 am

This one was very difficult for me, as I am not very good at calculating combinatorics with confidence. Usually the examples given in the problem are more useful then here. There could've been an example for 4 digit numbers instead of just 3 digit numbers. Would have helped a lot with the debugging.

Losty
Posts: 1
Joined: Mon Apr 15, 2013 1:22 pm

Re: Problem 162

Post by Losty » Mon Apr 15, 2013 1:25 pm

For those who use Math.Pow(x,y) function of C# it may be useful (actually - very useful - as i spen two hours debugging the bug) to know that if you try to convert the result to long you may loose significant bits if the result is close to 2^64.....

pimspelier
Posts: 41
Joined: Tue Jan 21, 2014 2:06 pm
Location: The Netherlands

Re: Problem 162

Post by pimspelier » Thu Apr 17, 2014 12:59 pm

After a few hours of typing in answers with only the last 4 digits wrong, I've finally solved. But I still have a few questions:

How did all those people solve it? All those formula's... I've solved it like kotulek (almost exactly the same, but other language) and I don't understand what they are doing. It doesn't help that all formula's seem to differ just a bit. There's also something wrong with the formula from rayfil, the only one who explained it a bit: it's mostly weird characters like à and ¬. So could anyone explain that to me?

Second question: first I tried it in C, but I forget to adapt my pow() to unsigned long long, so it didn't work and I thought the numbers were just to big. Then I tried Python, but strangely, I had a precison problem: because I divided bij n, it handled the numbers as floats, not integers. Even when I typed int(.../n), it didn't work. Is there a way around this: it would seem strange if Python, with unlimited precision with integers, couldn't handle division.
Image

User avatar
nicolas.patrois
Posts: 117
Joined: Fri Jul 26, 2013 3:54 pm
Contact:

Re: Problem 162

Post by nicolas.patrois » Thu Apr 17, 2014 1:25 pm

14/5=2 in Python 2 but 14/5=2.8 in Python 3. Use 14//5 in Python 3 if you want the integer quotient.
Image

pimspelier
Posts: 41
Joined: Tue Jan 21, 2014 2:06 pm
Location: The Netherlands

Re: Problem 162

Post by pimspelier » Thu Apr 17, 2014 1:44 pm

Thanks!
Image

User avatar
rayfil
Administrator
Posts: 1403
Joined: Sun Mar 26, 2006 4:30 am
Location: Ontario, Canada
Contact:

Re: Problem 162

Post by rayfil » Fri Apr 18, 2014 1:06 am

There's also something wrong with the formula from rayfil, the only one who explained it a bit: it's mostly weird characters like à and ¬. So could anyone explain that to me?
Sorry about that mishap. This is the very first report regarding this anomaly. Something may have changed in the site script since that post in October 2007. It did seem to display correctly at that time.

I have now edited the post to replace what had been used at the time to indicate a multiplying sign (being currently displayed as a series of funny characters such as what you described) by the more standard "*" sign.
When you assume something, you risk being wrong half the time.

User avatar
Breaker71413901
Posts: 5
Joined: Sun Dec 27, 2015 12:35 am

Re: Problem 162

Post by Breaker71413901 » Fri Jan 01, 2016 1:46 am

This is the first time I am posting in such a thread.
For this problem, my program's results for the exactly 3, 4 and 5 long numbers agrees with those of this thread's and also for my brute forced exactly 6. But when I add all the results from exactly 3 to exactly 16 and convert it to hexadecimal, I get a wrong answer.
I am using Python 2.something.
My algorythm is the same as for some other problems I already got a correct answer.
How am I able to get some guide without spoiling any details of the problem or breaking any rules?
Image

User avatar
Georg
Posts: 157
Joined: Mon Jan 21, 2008 7:00 am
Location: Mannheim, Germany
Contact:

Re: Problem 162

Post by Georg » Fri Jan 01, 2016 2:24 am

You can PM me your results for up to 6, up to 7, ... hexadecimal digits and I'll tell you the 1st wrong value.

User avatar
Georg
Posts: 157
Joined: Mon Jan 21, 2008 7:00 am
Location: Mannheim, Germany
Contact:

Re: Problem 162

Post by Georg » Fri Jan 01, 2016 3:37 am

All values are correct.

User avatar
Breaker71413901
Posts: 5
Joined: Sun Dec 27, 2015 12:35 am

Re: Problem 162

Post by Breaker71413901 » Fri Jan 01, 2016 4:02 am

Thanks. The problem was with my converting. I guess I should not use online converters again, I was just being lazy.
Image

Post Reply