## 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

Don't post any spoilers
hk
Posts: 10806
Joined: Sun Mar 26, 2006 10:34 am
Location: Haren, Netherlands

### Re: Problem 162

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?

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

### Re: Problem 162

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 8:49 am

### Re: Problem 162

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: 165
Joined: Tue Aug 02, 2011 2:05 am

### Re: Problem 162

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...

PurpleBlu3s
Posts: 73
Joined: Mon Sep 19, 2011 6:49 pm

### Re: Problem 162

For 5 digits, is 16260 correct or very close?

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

### Re: Problem 162

PurpleBlu3s wrote:For 5 digits, is 16260 correct or very close?

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

PurpleBlu3s
Posts: 73
Joined: Mon Sep 19, 2011 6:49 pm

### Re: Problem 162

thundre wrote:
PurpleBlu3s wrote:For 5 digits, is 16260 correct or very close?

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. :<

PurpleBlu3s
Posts: 73
Joined: Mon Sep 19, 2011 6:49 pm

### Re: Problem 162

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

EDIT: Nevermind - solved now.

ymersvennson
Posts: 11
Joined: Wed Aug 24, 2011 12:44 pm

### Re: Problem 162

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 2:22 pm

### Re: Problem 162

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

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.

nicolas.patrois
Posts: 118
Joined: Fri Jul 26, 2013 4:54 pm
Contact:

### Re: Problem 162

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.

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

### Re: Problem 162

Thanks!

rayfil
Posts: 1405
Joined: Sun Mar 26, 2006 5:30 am
Contact:

### Re: Problem 162

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.

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

### Re: Problem 162

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?

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

### Re: Problem 162

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

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

### Re: Problem 162

All values are correct.

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

### Re: Problem 162

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