Problem 162

[hk]

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]

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]

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]

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.

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]

For 5 digits, is 16260 correct or very close?

[thundre]

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.

[PurpleBlu3s]

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

[PurpleBlu3s]

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

EDIT: Nevermind - solved now.

[ymersvennson]

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]

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]

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]

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]

Thanks!

[rayfil]

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.

[Breaker71413901]

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]

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]

All values are correct.

[Breaker71413901]

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

[PierrotLeFou]

It's the first time that I post on this forum, and I have to say that I'm blind.
Sorry if something is wrong with my post.
I checked all posts on problem 162 and I found no explanation why my answer is refused.
So we have to count all hexacecimal numbers that contains the digits $0$, $1$ and $A$ at least once in each number.
And this is for all numbers with $3$ to $16$ digits.
Let me give an example for a $3$-digits number.
Since I can put $3$ digits in each of the $3$ positions, I have $3^3 = 27$ possibilities.
$000 001 00A 010 011 01A 0A0 0A1 0AA$
$100 101 10A 110 111 11A 1A0 1A1 1AA$
$A00 A01 A0A A10 A11 A1A AA0 AA1 AAA$
But we can't have a $0$ in the first position, so we will have $18 = 2 * 3^2$ values.
Now, we want to remove those numbers that don't contain the three digits.
We will take the first digit and only one of the two others:
For $1$ and $0$: $100 101 110$
For $1$ and $A$: $111 11A 1A1 1AA$
Same thing beginning with $A$.
So we will have 2 possibilities for $2$ digits: $2^2 = 4$.
But we have two choices: ($1$ and $0$) or ($1$ and $A$). So we have to multiply by $2$: $2 * 2^2 = 8$.
However, the sequence $111$ appears twice, so we have to remove one: $2 * 2^2 - 1$.
We have considered only situations for $1$. There will be the same amount for the $A$, so the total is $2 * (2 * 2^2 - 1)$.
And what remains is $10A, 1A0, A01, A10$. E.g. $4$ values.
The formula seems to be: $2 * 3^(n-1) - 2 * (2 * 2^(n-1) - 1)$
For a $4$ digits number, it gives $24$ numbers. Someone has found $262$ for $4$. Where does he takes his numbers?
About overflow mentionned in some posts, for a $16$-digits number, we have at most $3^16$ = $43 046 721$.
And the sum of $3^0$ to $3^16$ is less than $3^17$ = $129 140 163$.
It enters easily in a $32$-bits integer number.
Even if my reasonning seems good, my answer is said to be false.
Do I misunderstand the problem that much? Am I getting stupid, or what?

[SAG145]

The numbers may contain digits other than 0,1,A. For example, 210A is a valid number.