Project Euler Forum

Posted: **Sun Sep 20, 2009 10:01 pm**

I am having difficulty with this problem, although I'm not sure where I'm counting wrong.

Here's my thought process for counting possibilities for a n-digit hex number:

1. Place a '0' anywhere but the first spot. n-1 choices
2. Place a '1' anywhere. n-1 choices
3. Place an 'A' anywhere. n-2 choices
4. Put any digit in the remaining n-3 places. 16 choices each.
Total possibilities = (n-1)*(n-1)*(n-2)*16^(n-3)

Take this sum from n=3...16 to get the total.

Am I completely off here? Or perhaps counting something twice, or forgetting to count something?

Posted: **Sun Sep 20, 2009 10:55 pm**

You're missing the cases where at least two digits are interchangeable. That's pretty much why I haven't solved it yet...

Posted: **Mon Sep 21, 2009 1:19 am**

I dont understand. Can you show an example?

Posted: **Mon Sep 21, 2009 1:27 am**

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)*10² = 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.

Posted: **Mon Sep 21, 2009 1:32 am**

gotcha, thanks. In that case, it would probably be easier to count the numbers that dont have at least one 1,0,and A

Posted: **Mon Sep 21, 2009 7:26 am**

Have you solved problem #1? Go back to that problem. I don't know if you solved it with "brute force", but there is a constant time algorithm that solves it you can find on the forums. Study that algorithm carefully - it might contain a hint to problem 162

Posted: **Tue Dec 29, 2009 10:23 am**

Hello,
I'm using this approach with problem 162: I try to generate all possible "templates" of valid numbers containing "0","1" and "A".
For example, for 5 digits numbers:

10Axx -> can generate 16*16 different numbers
10xAx -> can generate 16*16 different numbers
10xxA -> can generate 16*16 different numbers
...

and I sum all the possibilities. Then, since for example "10Axx" and "10xAx" share 16 solutions of the form "10AAx", I subtract 16 from the previous sum. I do this for all the possible couples (1st with 2nd, 1st with 3rd, etc.), but the result is 9708 solutions, while I know from bruteforcing that there are 9928 numbers with 5 digits containing "0", "1" and "A".

Where can I go wrong?
Thanks.

Posted: **Tue Dec 29, 2009 12:16 pm**

Problem 162 (View Problem)

In your example, you're substracting 10AAx, but that includes 10AAA, which gets substracted many more times I think?

Good luck!

Posted: **Tue Dec 29, 2009 1:13 pm**

@friol : Please do not start a new topic if one already exists for the given problem.

Posted: **Wed Jul 28, 2010 1:51 pm**

Code: Select all

digits = {"0", "1", "A"};
sum = 0;
For[x = 0, x < 14, x++; AppendTo[digits, "x"],
sum += Length[Select[Permutations[digits], First[#] != "0" &]]*16^x
]
Print[BaseForm[sum, 16]]

As far as I understand it, this algo doesn't eliminate duplicates ...
I'm still trying to wrap my head around the inclusion-exclusion principle - hoping that I'd then know what to subtract at each loop.
Is my reasoning right?

And also, is the smithdale87's idea correct, given that the answer would be "total combinations - those that don't have 1, 0 or A" ?

smithdale87 wrote:gotcha, thanks. In that case, it would probably be easier to count the numbers that dont have at least one 1,0,and A

Posted: **Sat Aug 21, 2010 5:59 pm**

Having some trouble with this one..
I think I have it figured out, pretty sure my algorithm is correct but obviously I'm getting a wrong answer.

Would be nice if someone can verify any of the following results:
The decimal answer I'm getting has 19 digits, hexadecimal answer has 16 digits.
upto 4 digits : decimal 236 (hex EC)
upto 6 digits: decimal 253416 (0x3DDE8)
upto 13 digits: decimal 522938110477248 (1DB9C045083C0)

upto 30 digits: decimal 584567612995457040483777512143834872

Do these look reasonable? Any specific error I possibly made?

EDIT: I created a brute-force program to check numbers upto 4 digits and it returns 262.. I have no idea how that is correct. Can someone offer any help? I'm definitely missing something.
It it helps, My algorithm is based on a finite state machine.

Posted: **Sat Aug 21, 2010 6:51 pm**

For 4 digits, 262 is correct.

Posted: **Thu Sep 30, 2010 9:12 am**

how did you reached 262 ?

i have wrote a brute force for numbers with 4 digits

Code: Select all

int main()
{
    unsigned long Count = 0;

    int dc[0xF + 1] = {0};

    for(int a = 1;a <= 0xF;a++)
        for(int b = 0;b <= 0xF;b++)
            for(int c = 0;c <= 0xF;c++)
                for(int d = 0;d <= 0xF;d++)
                {
                    memset(dc,0,sizeof(dc));

                    dc[a]++;
                    dc[b]++;
                    dc[c]++;
                    dc[d]++;

                    if(dc[0] > 0  && dc[1] > 0 && dc[0xA] > 0)
                    {
                        Count++;

                        cout << Count << "\t" << hex << uppercase << a << b << c << d << endl;
                    }
                }


    cout << Count << endl;
}

its find 258 numbers,moreover i have another algorithm which works in another way (not brute force) which also found 258 numbers for numbers with up to 4 digits

can someone explain or at least verify that for up to 4 digits there are 258 and not 262 numbers

edit : i have now solved the problem,for this who reached the same situation i dont know if its clear from the problem description or not
but the problem ask you to count numbers with 16 digits + numbers with 15 digits + numbers with 14 digits and so...
not only numbers with 16 digits

Posted: **Sun Oct 03, 2010 5:56 am**

How many hexadecimal numbers containing at most sixteen hexadecimal digits ...

Why would anyone interpret that as meaning only numbers with 16 digits?????

Posted: **Fri Oct 29, 2010 4:59 am**

There seems to be a problem with the input that problem 162 accepts these days. If I enter any hex number that contains a letter, say 1A, I get a red message at the top of the page that says:

Your answer seems to contain unexpected characters.

It seems to accept decimal numbers just fine, but my answer unfortunately (for me) has some alphas. Perhaps some error checking code gone awry?

Best wishes,
Henry Laxen

Posted: **Fri Oct 29, 2010 5:32 am**

This was just added recently - see viewtopic.php?f=5&t=2055#p22160

As far as I'm aware it is just a warning though; if your answer is correct it will still be accepted.

Posted: **Fri Oct 29, 2010 7:20 am**

@henrylaxen : Yes, currently there is a bug with the answer-checking script; it will soon be fixed (and a post will be made here to that effect).

Posted: **Fri Oct 29, 2010 9:45 am**

Our apologies for the inconvenience. The bug has been fixed; everything should be ok now

Posted: **Tue Jun 07, 2011 8:33 pm**

Hello all,

I'd be very grateful if any programming experts out there could shed some light on the following. Are certain languages slower than others at performing recursion and/or looping? In particular, is recursion in MATLAB inherently slow? I've tried to do recursion in MATLAB for several problems including this one, but it always ends up taking up way too much time, and I was wondering if this is intrinsic to MATLAB, or whether the problem was designed to require optimisation and it's simply a case of my algorithm being inefficient. Apart from MATLAB, all I know is very basic C++. Is it worth implementing the same algorithm in C++, maybe it runs faster?

(I know this is not exactly the place for this question, but I'm unable to find the answer to my question through google)

Posted: **Tue Jun 07, 2011 9:05 pm**

Recursion is slow if your programming language does not use lazy evaluation or internal memoization. Most languages don't. In such cases, it helps (most of the time) to implement memoization yourself (i.e., an array of previous results) and then build up the result gradually. This resolves the performance issues most of the time.

As for the question itself, it might be better asked in the Programming Languages section (mods?)

Project Euler Forum

Problem 162

Problem 162

Re: Problem 162

Re: Problem 162

Re: Problem 162

Re: Problem 162

Re: Problem 162

Problem 162

Re: Problem 162

Re: Problem 162

Re: Problem 162

Problem 162

Re: Problem 162

Re: Problem 162

Re: Problem 162

Re: Problem 162

Re: Problem 162

Re: Problem 162

Re: Problem 162

Re: Problem 162

Re: Problem 162