Problem 162

[smithdale87]

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?

[elendiastarman]

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

[smithdale87]

I dont understand. Can you show an example?

[daniel.is.fischer]

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.

[smithdale87]

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

[zwuupeape]

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

[friol]

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.

[stijn263]

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!

[harryh]

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

[MaJJ]

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" ?

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

[DDgeva]

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.

[jaap]

For 4 digits, 262 is correct.

[elr]

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

[rayfil]

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

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

[henrylaxen]

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

[TripleM]

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.

[harryh]

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

[harryh]

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

[Waldovski]

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)

[Lord_Farin]

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?)