// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (17 votes, average: 4.94 out of 5)
Loading...

Project Euler Solutions

Project Euler 162 Solution

Project Euler 162 Solution

Project Euler 162: Find hexadecimal numbers containing at most 16 hexadecimal digits exist with all of the digits 0, 1 and A present at least once


Problem Description

In the hexadecimal number system numbers are represented using 16 different digits:

0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F
The hexadecimal number AF when written in the decimal number system equals 10×16+15=175.

In the 3-digit hexadecimal numbers 10A, 1A0, A10, and A01 the digits 0,1 and A are all present.
Like numbers written in base ten we write hexadecimal numbers without leading zeroes.

How many hexadecimal numbers containing at most sixteen hexadecimal digits exist with all of the digits 0,1, and A present at least once?
Give your answer as a hexadecimal number.

(A,B,C,D,E and F in upper case, without any leading or trailing code that marks the number as hexadecimal and without leading zeroes , e.g. 1A3F and not: 1a3f and not 0x1a3f and not $1A3F and not #1A3F and not 0000001A3F)

Analysis

This is a typical application of the inclusion-exclusion principle. It is helpful in answering questions where the number of elements of a set are required but not the elements themselves. We just need to know the number of elements in two sets and subtract the number in the intersection.

The equation, after combining some terms looks like: 15 x 16(n-1) + 41 x 14(n-1) – (43 x 15(n-1) + 13n) for each possible hex number containing n digits {3..16}.

Since the first digit is non zero the total possibilities without consideration for the constraints is 15 x 16(n-1). Then remove those with no {0, 1, A}. But we need to add back in those that have no 1 or 0, no 1 or A, no 0 or A. Then remove the duplicates that, again, have no {0, 1, A}. There are 258 4 digit hex numbers that follow this pattern.

Project Euler 162 Solution

Runs < 0.001 seconds in Python 2.7.
download arrowUse this link to get the Project Euler 162 Solution Python 2.7 source.

Answer

Slowly swipe from either end beginning with the white vertical bar to get an idea of the starting or ending digits. For less drama, just double click the answer area. The distance between the two bars will give you an idea of the magnitude. Touch devices can tap and hold the center of the box between the two bars and choose define to reveal the answer.
|3D58725572C62302|

Afterthoughts

  • This code could be modified to broaden the range of counting problems it could solve.
Project Euler 162 Solution last updated

Discussion

No comments yet.

Post a comment