Skip to content
May 11, 2010 / steve8

Another Fun Puzzle

The prime number 4535653, when translated to base 16, gives the hexadecimal number 0x453565, which has the same digits as the original number, omitting the last digit.

Find another example of a prime number that, translated to hexadecimal, yields the same digits, omitting the last 21 digits

This was the Ponder This Challenge for April 2010.

 

It relies on positional base numeral systems which are widely used and rarely thought about in our culture.

Let’s consider the 7-digit decimal (base 10) number: 4535653

digit’s place 7 6 5 4 3 2 1
unit value 10^6 10^5 10^4 10^3 10^2 10^1 10^0
digit integer 4 5 3 5 6 5 3
value per place 4*10^6 5*10^5 3*10^4 5*10^3 6*10^2 5*10^1 3*10^0

So to get the value for the entire 7-digit number, we simply sum the values per each place of the decimal number, which is

4*10^6 + 5*10^5 + 3*10^4 + 5*10^3 + 6*10^2 + 5*10^1 + 3*10^0

which = (as written in decimal) 4535653

I’ll do the same table for the hexadecimal (base 16) number 453565:

digit’s place 6 5 4 3 2 1
unit value 16^5 16^4 16^3 16^2 16^1 16^0
digit 4 5 3 5 6 5
value per place 4*16^5 5*16^4 3*16^3 5*16^2 6*16^1 5*16^0

4*16^5 + 5*16^4 + 3*16^3 + 5*16^2 + 6*16^1 + 5*16^0 = (decimal) 4535653 = (hexadecimal) 453565

 

 

Let’s get back to the problem, they want us to find a number with two properties:

1. the hexadecimal representation is identical to the decimal representation omitting the last 21 digits.

2. The Integer is Prime.

for now lets examine #1 for a moment, How do we find numbers with that property…

well each digit in a number of any base normally has this value to contribute:

unit_value * digit_integer

where:

unit_value = base ^ (digit_place – 1)

0 <= digit_integer < base , so max(digit_integer) = base – 1

maximum_cumulative_value_of_previous_digits(digit_place) = sum(max(digit_integer)*unit_value(p), p=1..digit_place – 1)

which = unit_value(digit_place) – 1

numeral system

let’s declare a couple variables

 

n is an integer

hexn is the base 16 representation of n

decn is a base 10 number constructed by appending 21 0s to the right of the literal hexn.

 

for this problem, the decimal number must be of equal value to the hex number, but must share all digits except for the last 21…

This means that we can  use the last 21 digits of the decimal number to make up for any discrepancy of value, and 21 digits of decimal can get up to sum ( 9 * 10^place-1,place = 1..21) = 999999999999999999999 = 10^21 – 1

So any integer n, where hexn – decn is positive and no more than 10^21 – 1 is a candidate to be a solution.

 

our integer n will satisfy the first condition of the puzzle IFF:

0 <= hexn – decn < 10^21

 

So let’s design a different positional numeral system to examine the value of this difference hexn – decn.

let’s define a numeral system where the value is the contribution to hexn-decn, and the character set are 0-9

special_unit_value(digit_place) = the difference in unit value in the hex to the unit value in the decimal after 21 0s are appended…

special_unit_value(digit_place) = 16^(digit_place – 1) – 10^(21+ digit_place – 1)

 

ttop

so we see from the graph above that we can get positive values if we get enough digits in the hex number, let’s look at a more detailed chart of unit_value per digit_place:

 

Capture

we see the minimum cumulative value for all digits maxes out at

-3653862699613613450061613042885398017647315043542900294867371565365704404131411080078183579778733265462124364559775760279143

~=-3.65*10^123

our first positive unit value is at digit 104 where special_unit_value = +576895500643977583230644928524336637254474927428499508554380724390492659780981533203027367035444557561459392400373732868
096

~=+5.77*10^122

This is good, very positive, but not nearly too big for the negative contribution of all the previous digits.

 

The next positive special_unit_value at place 105 = +69230328010303641331690318856389386196071598838855992136870091590247882556495704531248437872567112920983350278405979725889536

~=+6.92*10^124

this tells us that our number cannot even have a single non-negative integer after place 104, because the 105th special_unit_value is so much larger than all the negative contribution the lesser digits can make, in fact if we max out the negative for all the lesser digits, it only subtracts about 0.5% of the value of 1 unit of the 105th digit.

(6.23*10^125 – 3.65*10^123 = 6.19*10^125)

Which is way larger than 10^21, the maximum acceptable special_value in this problem.

 

so hexn must be 104 digits exactly.

 

 

we could increment n  or hexn , starting at 16^105, but to cover all 104 digit hex integers with digits [0-9], that will take 9*10^103 tests to see if 0<hexn-decn<10^21

9*10^103~=which is ~2^345.3285, which isn’t even close to feasible.

 

 

Instead we can go from the 104th digit to lesser digits, only considering values which (considering the maximum negative cumulative value of lesser digits) can yield a value within our range of (0,10^21).

here’s the code:

def specialUnitValue(place):
	return 16**(place-1) - 10**(21+place-1)

def maximumCumulativeValue(place):
	r=0
	for x in range(1,place):
		r+=9*max(specialUnitValue(x),0)
	return r

def minimumCumulativeValue(place):
	r=0
	for x in range(1,place):
		r+=9*min(specialUnitValue(x),0)
	return r

def getValue(digit_list):
	v=0
	digit_list.reverse()
	p=0
	for digit_value in digit_list:
		p+=1
		v+=digit_value*(16**(p-1))
	digit_list.reverse()
	return v

def recursiveFilter(place,digit_list,current_value):
	if place == 0:
		number_list.append(getValue(digit_list))
		return
	for x in range(0,10):
		new_current_value = current_value + x*specialUnitValue(place)
		if -maximumCumulativeValue(place) <= new_current_value < 10**21 - minimumCumulativeValue(place):
			recursiveFilter(place-1,digit_list+[x],new_current_value)
	return

place = 104
digit_list = []
number_list =[]
current_value = 0
recursiveFilter(place,digit_list,current_value)
print("the following numbers are represented exactly the same in hex and decimal, omitting the last 21 digits of the decimal representation:")
for n in number_list:
	print()
	print("(dec)",str(n))
	print("(hex)",str(hex(n))[2:])

outputs:

the following numbers are represented exactly the same in hex and decimal, omitting the last 21 digits of the decimal representation:

(dec) 0
(hex) 0

(dec) 10964973879145266684597918386961206640359744239118799335560543882943204057285999161085137407678295834996206085978967677028758
(hex) 10964973879145266684597918386961206640359744239118799335560543882943204057285999161085137407678295834996

(dec) 10965042548987794527084057351766268905929738560121836183995663823085815102408704908398080417506152437998396385865902388902296
(hex) 10965042548987794527084057351766268905929738560121836183995663823085815102408704908398080417506152437998

(dec) 11382975651657610360011724373059527023679401235446000875434984276671144440904563609247580929003959820277226372565581487538807
(hex) 11382975651657610360011724373059527023679401235446000875434984276671144440904563609247580929003959820277

(dec) 11383044321503994265174950355726300568630049590682850168652076962700460784689758874865273083169197842932705865806646564104498
(hex) 11383044321503994265174950355726300568630049590682850168652076962700460784689758874865273083169197842932

(dec) 11403774832697699927191683625580629545730840588452432470080875397274364900728637535263415299444961605674432192938509636490868
(hex) 11403774832697699927191683625580629545730840588452432470080875397274364900728637535263415299444961605674

(dec) 22786823350482228205608199978099471169330070448099877920884203755897679528961138686897878221599372454029885357802030895546409
(hex) 22786823350482228205608199978099471169330070448099877920884203755897679528961138686897878221599372454029

(dec) 22807622531522543610094414106106772108649683164642972183286269214619099352157014522058098996385254903281545695887189603267201
(hex) 22807622531522543610094414106106772108649683164642972183286269214619099352157014522058098996385254903281

(dec) 23225624303976723017196220515917404099608854985718038196616317054667018854359591688735436052791332652478513355408150356108408
(hex) 23225624303976723017196220515917404099608854985718038196616317054667018854359591688735436052791332652478

(dec) 34629467806524663910488411411813679561429784816827345905892170553651646560885008408033429786692704516617255059441377587848727
(hex) 34629467806524663910488411411813679561429784816827345905892170553651646560885008408033429786692704516617

(dec) 34630614434901308852464200036192701310784464271605203972278835294765396501224597514208949899168821013783738303866386899875715
(hex) 34630614434901308852464200036192701310784464271605203972278835294765396501224597514208949899168821013783

(dec) 35047469578049837366880709740625417027160304672000058413742228775833471575947576436574766395836776928100142757473522419925248
(hex) 35047469578049837366880709740625417027160304672000058413742228775833471575947576436574766395836776928100

(dec) 46452459709903429153073283753038447777798210559040188704150600559955356774538872177279968790528754691766851932291804282034022
(hex) 46452459709903429153073283753038447777798210559040188704150600559955356774538872177279968790528754691766

(dec) 57856307408728032899122821481744958592677162176215705623596847999672634661589955685836313952596116104916212444885882411960598
(hex) 57856307408728032899122821481744958592677162176215705623596847999672634661589955685836313952596116104916

(dec) 58274309180311384671530417444881588845667623071694823539992371381096007813431725768328081725978996158096888392730430747803798
(hex) 58274309180311384671530417444881588845667623071694823539992371381096007813431725768328081725978996158096

(dec) 69678152925760181390564134659968588468637327084560080449901460622205042762612707757129557846642035594344508706235255466050372
(hex) 69678152925760181390564134659968588468637327084560080449901460622205042762612707757129557846642035594344

(dec) 69700094553935846709056452304209818063563632357808257330729205642171418398171600992212697023360366697360024549290701595702112
(hex) 69700094553935846709056452304209818063563632357808257330729205642171418398171600992212697023360366697360

This is the comprehensive list of numbers satisfying condition #1 of the puzzle, #2 asks for one of these which are prime, so lets do a very simplistic prime test on these:

number_set=set(number_list)
not_prime_set=set()

import time
for n in number_set:
	t0=time.time()
	for x in range(2,n):
		if n%x ==0:
			not_prime_set.add(n)
			print(n,"is not prime because it's divisble by",x)
			break
		if time.time()-t0>100:
			print(n,"may be prime, did not find any factors within 100 seconds")
			break

print("the remaining numbers to check for primality are:", number_set - not_prime_set)

outputs:

0 is not prime because 0 isn't prime
57856307408728032899122821481744958592677162176215705623596847999672634661589955685836313952596116104916212444885882411960598 is not prime because it's divisble by 2
35047469578049837366880709740625417027160304672000058413742228775833471575947576436574766395836776928100142757473522419925248 is not prime because it's divisble by 2
46452459709903429153073283753038447777798210559040188704150600559955356774538872177279968790528754691766851932291804282034022 is not prime because it's divisble by 2
58274309180311384671530417444881588845667623071694823539992371381096007813431725768328081725978996158096888392730430747803798 is not prime because it's divisble by 2
23225624303976723017196220515917404099608854985718038196616317054667018854359591688735436052791332652478513355408150356108408 is not prime because it's divisble by 2
11382975651657610360011724373059527023679401235446000875434984276671144440904563609247580929003959820277226372565581487538807 is not prime because it's divisble by 3
69678152925760181390564134659968588468637327084560080449901460622205042762612707757129557846642035594344508706235255466050372 is not prime because it's divisble by 2
10965042548987794527084057351766268905929738560121836183995663823085815102408704908398080417506152437998396385865902388902296 is not prime because it's divisble by 2
11403774832697699927191683625580629545730840588452432470080875397274364900728637535263415299444961605674432192938509636490868 is not prime because it's divisble by 2
22807622531522543610094414106106772108649683164642972183286269214619099352157014522058098996385254903281545695887189603267201 may be prime, did not find any factors within 100 seconds
34629467806524663910488411411813679561429784816827345905892170553651646560885008408033429786692704516617255059441377587848727 is not prime because it's divisble by 3
69700094553935846709056452304209818063563632357808257330729205642171418398171600992212697023360366697360024549290701595702112 is not prime because it's divisble by 2
22786823350482228205608199978099471169330070448099877920884203755897679528961138686897878221599372454029885357802030895546409 is not prime because it's divisble by 7
10964973879145266684597918386961206640359744239118799335560543882943204057285999161085137407678295834996206085978967677028758 is not prime because it's divisble by 2
34630614434901308852464200036192701310784464271605203972278835294765396501224597514208949899168821013783738303866386899875715 is not prime because it's divisble by 3
11383044321503994265174950355726300568630049590682850168652076962700460784689758874865273083169197842932705865806646564104498 is not prime because it's divisble by 2
the remaining numbers to check for primality are: {22807622531522543610094414106106772108649683164642972183286269214619099352157014522058098996385254903281545695887189603267201}

So the only number of these which could possibly be prime is:

22807622531522543610094414106106772108649683164642972183286269214619099352157014522058098996385254903281545695887189603267201

I will save this non-trivial primality test for another time, but we can already say that if the puzzle has a solution, this is it.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: