The prime number 4535653, when translated to base 16, gives the hexadecimal number 0×453565, 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

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:

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

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)

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:

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 = +576895500643977583230644928524336637254474927428499508554380724390492659780981533203027367035444557561459392400373732868096

~=+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 fine 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 fine 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.

I settled on the HP ZR24w, as it was an IPS panel with good colors and viewing angles (IPS panel), had very little input lag, could rotate for 16:10 or 10:16 use, and wasn’t ridiculously priced like most IPS panels.

on HP’s page they are boasting a lot of energy saving stuff like an 85% power supply.  But forgive me for not really trusting their energy-efficient marketing, so I started comparing some LCD power consumption and found some striking differences.  Take a look at the little table I constructed:

other sources:

energystar, cnet, apple

What a wide range of power consumption, even at the same brightness.  There are no sanely-priced efficient IPS-panel 24-inch displays.  On this data it seems LEDs use less energy (no surprise), but maybe IPS panels need more power than tn?  I say that because the apple display is LED and IPS and still guzzles watts (oddly even more than the dell IPS ccfl display).

We are asking for the exact answer in two cases:

1. In the worst case, i.e., what is the smallest number X for which we can guarantee finding it in no more than X questions.
2. On average, i.e., assuming that the number was chosen in uniform distribution from 2 to 166 and we want to minimize the expected number of questions.

This problem was IBM’s Ponder This puzzle of November 2009.

I’m going to write my solution in English, along with code (both python and java) so anyone knowing any one of the 3 languages should be able to follow along.

For both #1 and #2 there are some relevant thoughts:

the smallest integer dividers (above 1) of all integers (above 1) are prime, so the divisor we are looking for will be prime, specifically only a few prime numbers that will be relevant between 2 and 166 (inclusively):

to find out about these primes, I wrote a little code:

Python (3.1)  :

prime_list = []
maxx = 166
for n in range(2,maxx+1):
    isprime = True
    for p in prime_list:
        if n % p is 0;
            isprime = False;
            break;
    if isprime == True:
        prime_list.append(n)
print("the primes less than",maxx+1,"are:")
print(prime_list)
print("there are ", len(prime_list), "of them")

OR Java :

import java.util.ArrayList;
public class primes {
	public static ArrayList<Integer> prime_list = new ArrayList<Integer>();
	public static void main(String args[]){
		int maxx = 166;
		boolean isPrime;
		for(int n=2; n <= maxx; n++){
			isPrime = true;
			for(int p : prime_list){
				if(n % p == 0){
					isPrime = false;
					break;
				}
			}
			if(isPrime){
				prime_list.add(n);
			}
		}
		System.out.println("the primes less than"+ maxx+1+ " are:");
		System.out.println(prime_list);
		System.out.println("there are " + prime_list.size() + " of them");
	}
}

Both the Python and the Java version of the logic will output the following:

the primes less than 167 are:
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163]
there are  38 of them

these 38 primes are the only possible ‘smallest integer dividers’ which we are trying to determine with our questions.

Worst Case (part #1 of the Puzzle)  seems like the easier problem to solve, so lets do it.

In the worst case, i.e., what is the smallest number X for which we can guarantee finding it in no more than X questions.

well there are 38 possible solutions, and we only care about worst case, so lets gather half of them and ask (Question 1) if the smallest integer divisor (>1) is in that group. 

if the answer is yes, then we have narrowed it down to 19, if the answer is 19 then we have narrowed it down to the other 19, either way we are left with 19.

Now take that 19 and group roughly half of them together (10) and ask (Question 2) if the smallest integer divisor (>1) is in that group.

if the answer is yes, then we have narrowed it down to 10, if the answer is no, then we have narrowed it down to 9.

Now take that 10 (or 9) and group together about half (5) and ask (Question 3) if the smallest integer divisor (>1) is in that group.

If the answer isyes, then we have narrowed it down to 5, otherwise we have also narrowed it down to 5 or 4 (depending if we had 10 or 9).

Now take those 5 or 4 and take roughly half (2) and ask (Question 4) if the smallest integer divisor is one of the two.

If the answer is yes, then we have narrowed it down to 2, otherwise we have narrowed it down to 3 or 2 (depending if we had 5 or 4)

Now take those 3 or 2 and take the first integer, and ask (Question 5) if that’s the greatest integer divisor (>1).

If yes, then we are done, that’s the number, if not and we started with 2, we are also done (the other is the number), if we had 3 then we have to ask one more question.

Take the 2 remaining and ask (Question 6 (not always required)) if that’s the greatest integer divisor (>1).

If yes, then we are done, that’s the number, if not then the other number is it.

So this method has a worst case of 6, a best case of 5, what about the average case?

here’s the code so far in Python 3.1:

prime_list = []
maxx = 166
for n in range(2,maxx+1):
    isprime = True
    for p in prime_list:
        if n % p is 0;
            isprime = False;
            break;
    if isprime == True:
        prime_list.append(n)
print("the primes less than",maxx+1,"are:")
print(prime_list)
print("there are ", len(prime_list), "of them")
def smallestPrimeFactor(n):
	for p in prime_list:
		if n/p == int(n/p):
			return p
question_history=[]
for n in range(2,maxx+1):
	prime_sublist = prime_list
	question_count=0
	while True:
		question_count+=1
		if smallestPrimeFactor(n) in prime_sublist[0:int(len(prime_sublist)/2)]:
			prime_sublist = prime_sublist[0:int(len(prime_sublist)/2)]
		else:
			prime_sublist = prime_sublist[int(len(prime_sublist)/2):]
		if len(prime_sublist)==1:
			print( "number =", n, " smallest factor (>1) =", prime_sublist[0], " questions asked =", question_count)
			question_history.append(question_count)
			break
print( "worst case   =", max(question_history) )
print( "best case    =", min(question_history) )
print( "average case =", sum(question_history) / (maxx-1) )

OR the program so far in Java:

import java.util.ArrayList;
import java.util.List;
public class primes {
	public static ArrayList<Integer> prime_list = new ArrayList<Integer>();
	public static void main(String args[]){
		int maxx = 166;
		boolean isPrime;
		for(int n=2; n <= maxx; n++){
			isPrime = true;
			for(int p : prime_list){
				if(n % p == 0){
					isPrime = false;
					break;
				}
			}
			if(isPrime){
				prime_list.add(n);
			}
		}
		System.out.println("the primes less than 167 are:");
		System.out.println(prime_list);
		System.out.println("there are " + prime_list.size() + " of them");
		int max_questions = -1;
		int min_questions = -1;
		int questions_sum = 0;
		for(int n=2; n <= maxx; n++){
			List<Integer> prime_sublist = prime_list;
			int question_count = 0;
			while(true){
				question_count++;
				if(prime_sublist.subList(0,prime_sublist.size()/2).contains(smallestPrimeFactor(n))){
					prime_sublist = prime_sublist.subList(0,prime_sublist.size()/2);
				}else{
					prime_sublist = prime_sublist.subList(prime_sublist.size()/2,prime_sublist.size());
				}
				if(prime_sublist.size() == 1){
					System.out.println("number = " + n + "  smallest factor (>1) = " + prime_sublist.get(0) + "  questions asked = " + question_count);
					if(question_count > max_questions){
						max_questions = question_count;
					}
					if(question_count < min_questions || min_questions == -1){
						min_questions = question_count;
					}
					questions_sum += question_count;
					break;
				}
			}
		}
		System.out.println("worst case   = "+max_questions);
		System.out.println("best case    = "+min_questions);
		System.out.println("average case = "+(float) questions_sum/(maxx-1));
	}
	public static int smallestPrimeFactor(int n){
		for(int p: prime_list){
			if((n / p) == (float)n / p){
				return p;
			}
		}
		return 0;
	}
}

The output for either of these programs is this:

the primes less than 167 are:
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163]
there are 38 of them
number = 2  smallest factor (>1) = 2  questions asked = 5
number = 3  smallest factor (>1) = 3  questions asked = 5
number = 4  smallest factor (>1) = 2  questions asked = 5
number = 5  smallest factor (>1) = 5  questions asked = 5
number = 6  smallest factor (>1) = 2  questions asked = 5
number = 7  smallest factor (>1) = 7  questions asked = 5
number = 8  smallest factor (>1) = 2  questions asked = 5
number = 9  smallest factor (>1) = 3  questions asked = 5
number = 10  smallest factor (>1) = 2  questions asked = 5
number = 11  smallest factor (>1) = 11  questions asked = 5
number = 12  smallest factor (>1) = 2  questions asked = 5
number = 13  smallest factor (>1) = 13  questions asked = 5
number = 14  smallest factor (>1) = 2  questions asked = 5
number = 15  smallest factor (>1) = 3  questions asked = 5
number = 16  smallest factor (>1) = 2  questions asked = 5
number = 17  smallest factor (>1) = 17  questions asked = 5
number = 18  smallest factor (>1) = 2  questions asked = 5
number = 19  smallest factor (>1) = 19  questions asked = 6
number = 20  smallest factor (>1) = 2  questions asked = 5
number = 21  smallest factor (>1) = 3  questions asked = 5
number = 22  smallest factor (>1) = 2  questions asked = 5
number = 23  smallest factor (>1) = 23  questions asked = 6
number = 24  smallest factor (>1) = 2  questions asked = 5
number = 25  smallest factor (>1) = 5  questions asked = 5
number = 26  smallest factor (>1) = 2  questions asked = 5
number = 27  smallest factor (>1) = 3  questions asked = 5
number = 28  smallest factor (>1) = 2  questions asked = 5
number = 29  smallest factor (>1) = 29  questions asked = 5
number = 30  smallest factor (>1) = 2  questions asked = 5
number = 31  smallest factor (>1) = 31  questions asked = 5
number = 32  smallest factor (>1) = 2  questions asked = 5
number = 33  smallest factor (>1) = 3  questions asked = 5
number = 34  smallest factor (>1) = 2  questions asked = 5
number = 35  smallest factor (>1) = 5  questions asked = 5
number = 36  smallest factor (>1) = 2  questions asked = 5
number = 37  smallest factor (>1) = 37  questions asked = 5
number = 38  smallest factor (>1) = 2  questions asked = 5
number = 39  smallest factor (>1) = 3  questions asked = 5
number = 40  smallest factor (>1) = 2  questions asked = 5
number = 41  smallest factor (>1) = 41  questions asked = 6
number = 42  smallest factor (>1) = 2  questions asked = 5
number = 43  smallest factor (>1) = 43  questions asked = 6
number = 44  smallest factor (>1) = 2  questions asked = 5
number = 45  smallest factor (>1) = 3  questions asked = 5
number = 46  smallest factor (>1) = 2  questions asked = 5
number = 47  smallest factor (>1) = 47  questions asked = 5
number = 48  smallest factor (>1) = 2  questions asked = 5
number = 49  smallest factor (>1) = 7  questions asked = 5
number = 50  smallest factor (>1) = 2  questions asked = 5
number = 51  smallest factor (>1) = 3  questions asked = 5
number = 52  smallest factor (>1) = 2  questions asked = 5
number = 53  smallest factor (>1) = 53  questions asked = 5
number = 54  smallest factor (>1) = 2  questions asked = 5
number = 55  smallest factor (>1) = 5  questions asked = 5
number = 56  smallest factor (>1) = 2  questions asked = 5
number = 57  smallest factor (>1) = 3  questions asked = 5
number = 58  smallest factor (>1) = 2  questions asked = 5
number = 59  smallest factor (>1) = 59  questions asked = 5
number = 60  smallest factor (>1) = 2  questions asked = 5
number = 61  smallest factor (>1) = 61  questions asked = 6
number = 62  smallest factor (>1) = 2  questions asked = 5
number = 63  smallest factor (>1) = 3  questions asked = 5
number = 64  smallest factor (>1) = 2  questions asked = 5
number = 65  smallest factor (>1) = 5  questions asked = 5
number = 66  smallest factor (>1) = 2  questions asked = 5
number = 67  smallest factor (>1) = 67  questions asked = 6
number = 68  smallest factor (>1) = 2  questions asked = 5
number = 69  smallest factor (>1) = 3  questions asked = 5
number = 70  smallest factor (>1) = 2  questions asked = 5
number = 71  smallest factor (>1) = 71  questions asked = 5
number = 72  smallest factor (>1) = 2  questions asked = 5
number = 73  smallest factor (>1) = 73  questions asked = 5
number = 74  smallest factor (>1) = 2  questions asked = 5
number = 75  smallest factor (>1) = 3  questions asked = 5
number = 76  smallest factor (>1) = 2  questions asked = 5
number = 77  smallest factor (>1) = 7  questions asked = 5
number = 78  smallest factor (>1) = 2  questions asked = 5
number = 79  smallest factor (>1) = 79  questions asked = 5
number = 80  smallest factor (>1) = 2  questions asked = 5
number = 81  smallest factor (>1) = 3  questions asked = 5
number = 82  smallest factor (>1) = 2  questions asked = 5
number = 83  smallest factor (>1) = 83  questions asked = 5
number = 84  smallest factor (>1) = 2  questions asked = 5
number = 85  smallest factor (>1) = 5  questions asked = 5
number = 86  smallest factor (>1) = 2  questions asked = 5
number = 87  smallest factor (>1) = 3  questions asked = 5
number = 88  smallest factor (>1) = 2  questions asked = 5
number = 89  smallest factor (>1) = 89  questions asked = 5
number = 90  smallest factor (>1) = 2  questions asked = 5
number = 91  smallest factor (>1) = 7  questions asked = 5
number = 92  smallest factor (>1) = 2  questions asked = 5
number = 93  smallest factor (>1) = 3  questions asked = 5
number = 94  smallest factor (>1) = 2  questions asked = 5
number = 95  smallest factor (>1) = 5  questions asked = 5
number = 96  smallest factor (>1) = 2  questions asked = 5
number = 97  smallest factor (>1) = 97  questions asked = 5
number = 98  smallest factor (>1) = 2  questions asked = 5
number = 99  smallest factor (>1) = 3  questions asked = 5
number = 100  smallest factor (>1) = 2  questions asked = 5
number = 101  smallest factor (>1) = 101  questions asked = 5
number = 102  smallest factor (>1) = 2  questions asked = 5
number = 103  smallest factor (>1) = 103  questions asked = 6
number = 104  smallest factor (>1) = 2  questions asked = 5
number = 105  smallest factor (>1) = 3  questions asked = 5
number = 106  smallest factor (>1) = 2  questions asked = 5
number = 107  smallest factor (>1) = 107  questions asked = 6
number = 108  smallest factor (>1) = 2  questions asked = 5
number = 109  smallest factor (>1) = 109  questions asked = 5
number = 110  smallest factor (>1) = 2  questions asked = 5
number = 111  smallest factor (>1) = 3  questions asked = 5
number = 112  smallest factor (>1) = 2  questions asked = 5
number = 113  smallest factor (>1) = 113  questions asked = 5
number = 114  smallest factor (>1) = 2  questions asked = 5
number = 115  smallest factor (>1) = 5  questions asked = 5
number = 116  smallest factor (>1) = 2  questions asked = 5
number = 117  smallest factor (>1) = 3  questions asked = 5
number = 118  smallest factor (>1) = 2  questions asked = 5
number = 119  smallest factor (>1) = 7  questions asked = 5
number = 120  smallest factor (>1) = 2  questions asked = 5
number = 121  smallest factor (>1) = 11  questions asked = 5
number = 122  smallest factor (>1) = 2  questions asked = 5
number = 123  smallest factor (>1) = 3  questions asked = 5
number = 124  smallest factor (>1) = 2  questions asked = 5
number = 125  smallest factor (>1) = 5  questions asked = 5
number = 126  smallest factor (>1) = 2  questions asked = 5
number = 127  smallest factor (>1) = 127  questions asked = 5
number = 128  smallest factor (>1) = 2  questions asked = 5
number = 129  smallest factor (>1) = 3  questions asked = 5
number = 130  smallest factor (>1) = 2  questions asked = 5
number = 131  smallest factor (>1) = 131  questions asked = 6
number = 132  smallest factor (>1) = 2  questions asked = 5
number = 133  smallest factor (>1) = 7  questions asked = 5
number = 134  smallest factor (>1) = 2  questions asked = 5
number = 135  smallest factor (>1) = 3  questions asked = 5
number = 136  smallest factor (>1) = 2  questions asked = 5
number = 137  smallest factor (>1) = 137  questions asked = 6
number = 138  smallest factor (>1) = 2  questions asked = 5
number = 139  smallest factor (>1) = 139  questions asked = 5
number = 140  smallest factor (>1) = 2  questions asked = 5
number = 141  smallest factor (>1) = 3  questions asked = 5
number = 142  smallest factor (>1) = 2  questions asked = 5
number = 143  smallest factor (>1) = 11  questions asked = 5
number = 144  smallest factor (>1) = 2  questions asked = 5
number = 145  smallest factor (>1) = 5  questions asked = 5
number = 146  smallest factor (>1) = 2  questions asked = 5
number = 147  smallest factor (>1) = 3  questions asked = 5
number = 148  smallest factor (>1) = 2  questions asked = 5
number = 149  smallest factor (>1) = 149  questions asked = 5
number = 150  smallest factor (>1) = 2  questions asked = 5
number = 151  smallest factor (>1) = 151  questions asked = 5
number = 152  smallest factor (>1) = 2  questions asked = 5
number = 153  smallest factor (>1) = 3  questions asked = 5
number = 154  smallest factor (>1) = 2  questions asked = 5
number = 155  smallest factor (>1) = 5  questions asked = 5
number = 156  smallest factor (>1) = 2  questions asked = 5
number = 157  smallest factor (>1) = 157  questions asked = 6
number = 158  smallest factor (>1) = 2  questions asked = 5
number = 159  smallest factor (>1) = 3  questions asked = 5
number = 160  smallest factor (>1) = 2  questions asked = 5
number = 161  smallest factor (>1) = 7  questions asked = 5
number = 162  smallest factor (>1) = 2  questions asked = 5
number = 163  smallest factor (>1) = 163  questions asked = 6
number = 164  smallest factor (>1) = 2  questions asked = 5
number = 165  smallest factor (>1) = 3  questions asked = 5
number = 166  smallest factor (>1) = 2  questions asked = 5
worst case   = 6
best case    = 5
average case = 5.072727

So for this algorithm (let’s call it the worst-case algorithm), we found the possible solution set of 38 primes, then we divided it in half and asked which half iteratively until we were had a set of 1, and that’s the solution.

This is an intuitive way to have the best worst-case in terms of number of questions.

Dividing the set in half for each question is the most amount of progress we can make, getting rid of half the dataset each question.

And that’s the goal, getting to the solution in the least amount of questions in the worst case…

Puzzle part 2:

On average, i.e., assuming that the number was chosen in uniform distribution from 2 to 166 and we want to minimize the expected number of questions.

In the average case, our worst-case method is not very productive, look at the first question:

well there are 38 possible solutions, and we only care about worst case, so lets gather half of them and ask (Question 1) if the smallest integer divisor (>1) is in that group. 

so dividing the set in two we have [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67] and [71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163]

but since 2 is the solution more than half the time, and 3 being the 2nd most likely, you can see that we really aren’t asking a 50/50 question.  In this case we are asking a 146/19 question, in the average case we aren’t really making a lot of progress with that.

Le’t’s figure out the probabilty of the relevant primes in this dataset:

Python 3.1:

prime_count={p:0 for p in prime_list}
for n in range(2,maxx+1):
	prime_count[smallestPrimeFactor(n)]+=1
n=0
for p in prime_list:
	n+=1
	print("prime#",n,"prime =",p," # of times it is the solution =", prime_count[p])

OR in java:

Hashtable<Integer,Integer> prime_count = new Hashtable<Integer,Integer>();
for(int p:prime_list){
	prime_count.put(p,0);
}
for(int n=2;n<= maxx;n++){
	prime_count.put(smallestPrimeFactor(n),prime_count.get(smallestPrimeFactor(n))+1);
}
int n = 0;
for(int p: prime_list){
	n++;
	System.out.println("prime#" + n + " prime = " + p + " # of times it is the solution = " + prime_count.get(p));
}

Both programs output this:

prime#01 prime = 2    # of times it is the solution = 83
prime#02 prime = 3    # of times it is the solution = 28
prime#03 prime = 5    # of times it is the solution = 11
prime#04 prime = 7    # of times it is the solution = 7
prime#05 prime = 11   # of times it is the solution = 3
prime#06 prime = 13   # of times it is the solution = 1
prime#07 prime = 17   # of times it is the solution = 1
prime#08 prime = 19   # of times it is the solution = 1
prime#09 prime = 23   # of times it is the solution = 1
prime#10 prime = 29   # of times it is the solution = 1
prime#11 prime = 31   # of times it is the solution = 1
prime#12 prime = 37   # of times it is the solution = 1
prime#13 prime = 41   # of times it is the solution = 1
prime#14 prime = 43   # of times it is the solution = 1
prime#15 prime = 47   # of times it is the solution = 1
prime#16 prime = 53   # of times it is the solution = 1
prime#17 prime = 59   # of times it is the solution = 1
prime#18 prime = 61   # of times it is the solution = 1
prime#19 prime = 67   # of times it is the solution = 1
prime#20 prime = 71   # of times it is the solution = 1
prime#21 prime = 73   # of times it is the solution = 1
prime#22 prime = 79   # of times it is the solution = 1
prime#23 prime = 83   # of times it is the solution = 1
prime#24 prime = 89   # of times it is the solution = 1
prime#25 prime = 97   # of times it is the solution = 1
prime#26 prime = 101  # of times it is the solution = 1
prime#27 prime = 103  # of times it is the solution = 1
prime#28 prime = 107  # of times it is the solution = 1
prime#29 prime = 109  # of times it is the solution = 1
prime#30 prime = 113  # of times it is the solution = 1
prime#31 prime = 127  # of times it is the solution = 1
prime#32 prime = 131  # of times it is the solution = 1
prime#33 prime = 137  # of times it is the solution = 1
prime#34 prime = 139  # of times it is the solution = 1
prime#35 prime = 149  # of times it is the solution = 1
prime#36 prime = 151  # of times it is the solution = 1
prime#37 prime = 157  # of times it is the solution = 1
prime#38 prime = 163  # of times it is the solution = 1

To develop the best average-case algorithm we need to evenly divide the solution set in 2 for each question, but not even in the number of primes in each set, but even in probability.  We will try to get the sum of the number of times the prime is a solution to be the same in each half.  Effectively choosing the division so that the question will be a 50/50 question.

Question 1 is easy (since 2 is the solution to just over half the numbers):

the set will be split into [2] and [ 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163]

this is a 83/82 question, nearly 50/50…

there is probability = 83/165 that the answer to this question will pinpoint the solution at 2.

Question 2 (if necessary): We now must divide the remaining into two nearly* equally probable sets:

so we can split the remaining up into sets like this:

[3,5,7] vs [11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163]

with weightings 28+11+7 vs 3+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1

so that’s 46 vs. 36

It’s very important to note that you can get more balanced groupings, for example grouping 3 (with occurrence score of 28) with 13 of the larger primes (each with 1 occurrence), yielding 42 vs. 42…

The problem with that is you will have a group with a 28 and 13 1’s, so the next matchup if that group is selected will be very imbalanced.

Since we cannot divide up the probability beyond per prime, we should need to consider these cases and not go for perfectly half every time, but instead find the best division for all the possible subsets that will be dealt with in later questions, that will give us the best average case.  This is a very significant and interesting puzzle in itself, It’s almost a shame that a little luck and a naive approach to this can still yield the optimal solution for this dataset, but in a different dataset, this problem could not be glossed over.

Here is the algorithm to optimally construct the tree, with the English description following…

Python:

keys = []
values = []
for p in sorted(prime_count):
	keys.append([p])
	values.append(prime_count[p])
print(keys)
print(values
while len(keys) > 2:
	min1_value = min(values)
	min1_index = values.index(min1_value)
	min1_key = keys[min1_index]
	del values[min1_index]
	del keys[min1_index]
	min2_value=min(values)
	min2_index = values.index(min2_value)
	min2_key = keys[min2_index]
	del keys[min2_index]
	del values[min2_index]
	keys.append(min1_key + min2_key)
	values.append(min1_value + min2_value)
	print()
	print(keys)
	print(values)

OR Java:

for(int p:prime_list){
	HashSet<Integer> temp = new HashSet<Integer>();
	temp.add(p);
	keys.add(temp);
	values.add(prime_count.get(p));
}
ArrayList<HashSet<Integer>> in_sets = new ArrayList<HashSet<Integer>>();
ArrayList<HashSet<Integer>> out_sets = new ArrayList<HashSet<Integer>>();
while(keys.size()>1){
	int tmp_index = 0;
	int min1_v = 0;
	int min2_v = 0;
	int min1_i = 0;
	int min2_i = 0;
	HashSet<Integer> min1_k = new HashSet<Integer>();
	HashSet<Integer> min2_k = new HashSet<Integer>();
	HashSet<Integer> min_union_k = new HashSet<Integer>();
	for(int v:values){
		if(tmp_index == 0 | v < min1_v){
			min2_v = min1_v;
			min2_k = min1_k;
			min2_i = min1_i;
			min1_v = v;
			min1_k = keys.get(tmp_index);
			min1_i = tmp_index;
		}else if(v < min2_v | tmp_index == 1){
			min2_v = v;
			min2_k = keys.get(tmp_index);
			min2_i = tmp_index;
		}
		tmp_index++;
	}
	min_union_k.addAll(min1_k);
	min_union_k.addAll(min2_k);
	values.remove(Math.max(min1_i, min2_i));
	values.remove(Math.min(min1_i, min2_i));
	keys.remove(Math.max(min1_i, min2_i));
	keys.remove(Math.min(min1_i, min2_i));
	values.add(min1_v+min2_v);
	keys.add(min_union_k);
	System.out.println();
	System.out.println(keys);
	System.out.println(values);
}

This code will incrementally merge the two smallest (in frequency score) sets of primes together, until there is just 2 sets,  keeping a record of this will provide us with an answer-key to how to optimally partition the possible primes when we want to ask a question to narrow down our options.

Here is the output, it starts with all the primes, each in their own set, and below each list is the corresponding frequency scores for each set, when two of the least-valued primes are merged, their scores are summed:

[[2], [3], [5], [7], [11], [13], [17], [19], [23], [29], [31], [37], [41], [43], [47], [53], [59], [61], [67], [71], [73], [79], [83], [89], [97], [101], [103], [107], [109], [113], [127], [131], [137], [139], [149], [151], [157], [163]]
[83, 28, 11, 7, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

[[2], [3], [5], [7], [11], [19], [23], [29], [31], [37], [41], [43], [47], [53], [59], [61], [67], [71], [73], [79], [83], [89], [97], [101], [103], [107], [109], [113], [127], [131], [137], [139], [149], [151], [157], [163], [13, 17]]
[83, 28, 11, 7, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2]

[[2], [3], [5], [7], [11], [29], [31], [37], [41], [43], [47], [53], [59], [61], [67], [71], [73], [79], [83], [89], [97], [101], [103], [107], [109], [113], [127], [131], [137], [139], [149], [151], [157], [163], [13, 17], [19, 23]]
[83, 28, 11, 7, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2]

[[2], [3], [5], [7], [11], [37], [41], [43], [47], [53], [59], [61], [67], [71], [73], [79], [83], [89], [97], [101], [103], [107], [109], [113], [127], [131], [137], [139], [149], [151], [157], [163], [13, 17], [19, 23], [29, 31]]
[83, 28, 11, 7, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2]

[[2], [3], [5], [7], [11], [43], [47], [53], [59], [61], [67], [71], [73], [79], [83], [89], [97], [101], [103], [107], [109], [113], [127], [131], [137], [139], [149], [151], [157], [163], [13, 17], [19, 23], [29, 31], [37, 41]]
[83, 28, 11, 7, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2]

[[2], [3], [5], [7], [11], [53], [59], [61], [67], [71], [73], [79], [83], [89], [97], [101], [103], [107], [109], [113], [127], [131], [137], [139], [149], [151], [157], [163], [13, 17], [19, 23], [29, 31], [37, 41], [43, 47]]
[83, 28, 11, 7, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2]

[[2], [3], [5], [7], [11], [61], [67], [71], [73], [79], [83], [89], [97], [101], [103], [107], [109], [113], [127], [131], [137], [139], [149], [151], [157], [163], [13, 17], [19, 23], [29, 31], [37, 41], [43, 47], [53, 59]]
[83, 28, 11, 7, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2]

[[2], [3], [5], [7], [11], [71], [73], [79], [83], [89], [97], [101], [103], [107], [109], [113], [127], [131], [137], [139], [149], [151], [157], [163], [13, 17], [19, 23], [29, 31], [37, 41], [43, 47], [53, 59], [61, 67]]
[83, 28, 11, 7, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2]

[[2], [3], [5], [7], [11], [79], [83], [89], [97], [101], [103], [107], [109], [113], [127], [131], [137], [139], [149], [151], [157], [163], [13, 17], [19, 23], [29, 31], [37, 41], [43, 47], [53, 59], [61, 67], [71, 73]]
[83, 28, 11, 7, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2]

[[2], [3], [5], [7], [11], [89], [97], [101], [103], [107], [109], [113], [127], [131], [137], [139], [149], [151], [157], [163], [13, 17], [19, 23], [29, 31], [37, 41], [43, 47], [53, 59], [61, 67], [71, 73], [79, 83]]
[83, 28, 11, 7, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2]

[[2], [3], [5], [7], [11], [101], [103], [107], [109], [113], [127], [131], [137], [139], [149], [151], [157], [163], [13, 17], [19, 23], [29, 31], [37, 41], [43, 47], [53, 59], [61, 67], [71, 73], [79, 83], [89, 97]]
[83, 28, 11, 7, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]

[[2], [3], [5], [7], [11], [107], [109], [113], [127], [131], [137], [139], [149], [151], [157], [163], [13, 17], [19, 23], [29, 31], [37, 41], [43, 47], [53, 59], [61, 67], [71, 73], [79, 83], [89, 97], [101, 103]]
[83, 28, 11, 7, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]

[[2], [3], [5], [7], [11], [113], [127], [131], [137], [139], [149], [151], [157], [163], [13, 17], [19, 23], [29, 31], [37, 41], [43, 47], [53, 59], [61, 67], [71, 73], [79, 83], [89, 97], [101, 103], [107, 109]]
[83, 28, 11, 7, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]

[[2], [3], [5], [7], [11], [131], [137], [139], [149], [151], [157], [163], [13, 17], [19, 23], [29, 31], [37, 41], [43, 47], [53, 59], [61, 67], [71, 73], [79, 83], [89, 97], [101, 103], [107, 109], [113, 127]]
[83, 28, 11, 7, 3, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]

[[2], [3], [5], [7], [11], [139], [149], [151], [157], [163], [13, 17], [19, 23], [29, 31], [37, 41], [43, 47], [53, 59], [61, 67], [71, 73], [79, 83], [89, 97], [101, 103], [107, 109], [113, 127], [131, 137]]
[83, 28, 11, 7, 3, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]

[[2], [3], [5], [7], [11], [151], [157], [163], [13, 17], [19, 23], [29, 31], [37, 41], [43, 47], [53, 59], [61, 67], [71, 73], [79, 83], [89, 97], [101, 103], [107, 109], [113, 127], [131, 137], [139, 149]]
[83, 28, 11, 7, 3, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]

[[2], [3], [5], [7], [11], [163], [13, 17], [19, 23], [29, 31], [37, 41], [43, 47], [53, 59], [61, 67], [71, 73], [79, 83], [89, 97], [101, 103], [107, 109], [113, 127], [131, 137], [139, 149], [151, 157]]
[83, 28, 11, 7, 3, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]

[[2], [3], [5], [7], [11], [19, 23], [29, 31], [37, 41], [43, 47], [53, 59], [61, 67], [71, 73], [79, 83], [89, 97], [101, 103], [107, 109], [113, 127], [131, 137], [139, 149], [151, 157], [163, 13, 17]]
[83, 28, 11, 7, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3]

[[2], [3], [5], [7], [11], [37, 41], [43, 47], [53, 59], [61, 67], [71, 73], [79, 83], [89, 97], [101, 103], [107, 109], [113, 127], [131, 137], [139, 149], [151, 157], [163, 13, 17], [19, 23, 29, 31]]
[83, 28, 11, 7, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 4]

[[2], [3], [5], [7], [11], [53, 59], [61, 67], [71, 73], [79, 83], [89, 97], [101, 103], [107, 109], [113, 127], [131, 137], [139, 149], [151, 157], [163, 13, 17], [19, 23, 29, 31], [37, 41, 43, 47]]
[83, 28, 11, 7, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 4, 4]

[[2], [3], [5], [7], [11], [71, 73], [79, 83], [89, 97], [101, 103], [107, 109], [113, 127], [131, 137], [139, 149], [151, 157], [163, 13, 17], [19, 23, 29, 31], [37, 41, 43, 47], [53, 59, 61, 67]]
[83, 28, 11, 7, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 4, 4, 4]

[[2], [3], [5], [7], [11], [89, 97], [101, 103], [107, 109], [113, 127], [131, 137], [139, 149], [151, 157], [163, 13, 17], [19, 23, 29, 31], [37, 41, 43, 47], [53, 59, 61, 67], [71, 73, 79, 83]]
[83, 28, 11, 7, 3, 2, 2, 2, 2, 2, 2, 2, 3, 4, 4, 4, 4]

[[2], [3], [5], [7], [11], [107, 109], [113, 127], [131, 137], [139, 149], [151, 157], [163, 13, 17], [19, 23, 29, 31], [37, 41, 43, 47], [53, 59, 61, 67], [71, 73, 79, 83], [89, 97, 101, 103]]
[83, 28, 11, 7, 3, 2, 2, 2, 2, 2, 3, 4, 4, 4, 4, 4]

[[2], [3], [5], [7], [11], [131, 137], [139, 149], [151, 157], [163, 13, 17], [19, 23, 29, 31], [37, 41, 43, 47], [53, 59, 61, 67], [71, 73, 79, 83], [89, 97, 101, 103], [107, 109, 113, 127]]
[83, 28, 11, 7, 3, 2, 2, 2, 3, 4, 4, 4, 4, 4, 4]

[[2], [3], [5], [7], [11], [151, 157], [163, 13, 17], [19, 23, 29, 31], [37, 41, 43, 47], [53, 59, 61, 67], [71, 73, 79, 83], [89, 97, 101, 103], [107, 109, 113, 127], [131, 137, 139, 149]]
[83, 28, 11, 7, 3, 2, 3, 4, 4, 4, 4, 4, 4, 4]

[[2], [3], [5], [7], [163, 13, 17], [19, 23, 29, 31], [37, 41, 43, 47], [53, 59, 61, 67], [71, 73, 79, 83], [89, 97, 101, 103], [107, 109, 113, 127], [131, 137, 139, 149], [151, 157, 11]]
[83, 28, 11, 7, 3, 4, 4, 4, 4, 4, 4, 4, 5]

[[2], [3], [5], [7], [37, 41, 43, 47], [53, 59, 61, 67], [71, 73, 79, 83], [89, 97, 101, 103], [107, 109, 113, 127], [131, 137, 139, 149], [151, 157, 11], [163, 13, 17, 19, 23, 29, 31]]
[83, 28, 11, 7, 4, 4, 4, 4, 4, 4, 5, 7]

[[2], [3], [5], [7], [71, 73, 79, 83], [89, 97, 101, 103], [107, 109, 113, 127], [131, 137, 139, 149], [151, 157, 11], [163, 13, 17, 19, 23, 29, 31], [37, 41, 43, 47, 53, 59, 61, 67]]
[83, 28, 11, 7, 4, 4, 4, 4, 5, 7, 8]

[[2], [3], [5], [7], [107, 109, 113, 127], [131, 137, 139, 149], [151, 157, 11], [163, 13, 17, 19, 23, 29, 31], [37, 41, 43, 47, 53, 59, 61, 67], [71, 73, 79, 83, 89, 97, 101, 103]]
[83, 28, 11, 7, 4, 4, 5, 7, 8, 8]

[[2], [3], [5], [7], [151, 157, 11], [163, 13, 17, 19, 23, 29, 31], [37, 41, 43, 47, 53, 59, 61, 67], [71, 73, 79, 83, 89, 97, 101, 103], [107, 109, 113, 127, 131, 137, 139, 149]]
[83, 28, 11, 7, 5, 7, 8, 8, 8]

[[2], [3], [5], [163, 13, 17, 19, 23, 29, 31], [37, 41, 43, 47, 53, 59, 61, 67], [71, 73, 79, 83, 89, 97, 101, 103], [107, 109, 113, 127, 131, 137, 139, 149], [151, 157, 11, 7]]
[83, 28, 11, 7, 8, 8, 8, 12]

[[2], [3], [5], [71, 73, 79, 83, 89, 97, 101, 103], [107, 109, 113, 127, 131, 137, 139, 149], [151, 157, 11, 7], [163, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67]]
[83, 28, 11, 8, 8, 12, 15]

[[2], [3], [5], [151, 157, 11, 7], [163, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67], [71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149]]
[83, 28, 11, 12, 15, 16]

[[2], [3], [163, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67], [71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149], [5, 151, 157, 11, 7]]
[83, 28, 15, 16, 23]

[[2], [3], [5, 151, 157, 11, 7], [163, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149]]
[83, 28, 23, 31]

[[2], [163, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149], [5, 151, 157, 11, 7, 3]]
[83, 31, 51]

[[2], [163, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 5, 151, 157, 11, 7, 3]]
[83, 82]

The ouptut shows the algorithm in action, essentially building the partition tree from the ground, in each pair of lists, the first is a list of groups of primes, the 2nd is the corresponding frequency value of each group.  The final code will record each merging, each step, as a guide to how to partition any remaining group.  It will map out the partition tree of the possible solutions in a fashion that is the optimal in average-case.

Question 3+

so we simply move the partition from left to right (in the ordered list of remaining possible least prime factors) until the left group has equal to or greater than half the total occurrences as solutions to the 165 numbers.

Here is the complete code implementing this average-case algorithm and applying it to each number over the range of this problem, computing average-case performance in the process.

The complete program in Python 3.1:

import time
t0=time.time()
prime_list = []
maxx = 166
for n in range(2, maxx+1):
    isprime = True
    for p in prime_list:
        if n % p is 0:
            isprime = False
            break
    if isprime == True:
        prime_list.append(n)
def smallestPrimeFactor(n):
	for p in prime_list:
		if n % p == 0:
			return p
prime_count={p : 0 for p in prime_list}
for n in range(2, maxx + 1):
	prime_count[smallestPrimeFactor(n)] += 1
keys = []
values = []
in_sets = []
out_sets = []
for p in sorted(prime_count):
	keys.append([p])
	values.append(prime_count[p])
while len(keys) > 1:
	min1_value = min(values)
	min1_index = values.index(min1_value)
	min1_key = keys[min1_index]
	del values[min1_index]
	del keys[min1_index]
	min2_value = min(values)
	min2_index = values.index(min2_value)
	min2_key = keys[min2_index]
	del keys[min2_index]
	del values[min2_index]
	in_sets.append(set(min1_key + min2_key))
	out_sets.append(set(min1_key))
	keys.append(min1_key + min2_key)
	values.append(min1_value + min2_value)
#now that we have a partition answer-key (mapping of in_sets to out_sets)
#let's increment through the entire range of integers and compute the algorithm's performance
print("done with partition answer-key, time elapsed =", int(1000*(time.time()-t0)), "ms")
question_history = []
for n in range(2, maxx + 1):
	prime_subset = set(prime_list)
	question_count = 0
	while True:
		question_count += 1
		checkset = out_sets[in_sets.index(prime_subset)]
		if smallestPrimeFactor(n) in checkset:
			prime_subset = checkset
		else:
			prime_subset = prime_subset-checkset
		if len(prime_subset) == 1:
			print( "number =", n, " smallest factor (>1) =", list(prime_subset)[0], " questions asked =", question_count)
			question_history.append(question_count)
			break
print( "worst case   =", max(question_history), "questions" )
print( "best case    =", min(question_history), "questoins" )
print( "average case =", sum(question_history), "/", (maxx-1), "~=",sum(question_history)/(maxx-1), "questions" )
print( "time elapsed =", int((time.time() - t0)*1000),"ms")

Alternatively, the complete Java program:

import java.util.*;
import java.lang.Math;
public class primes {
	public static ArrayList<Integer> prime_list = new ArrayList<Integer>();
	public static void main(String args[]){
		Long t0 = System.currentTimeMillis();
		int maxx = 166;
		boolean isPrime;
		for(int n=2; n <= maxx; n++){
			isPrime = true;
			for(int p : prime_list){
				if(n % p == 0){
					isPrime = false;
					break;
				}
			}
			if(isPrime){
				prime_list.add(n);
			}
		}
		Hashtable<Integer,Integer> prime_count = new Hashtable<Integer,Integer>();
		ArrayList<Integer> values = new ArrayList<Integer>();
		ArrayList<HashSet<Integer>> keys = new ArrayList<HashSet<Integer>>();
		HashSet<Integer> prime_set = new HashSet<Integer>();
		for(int p:prime_list){
			prime_count.put(p,0);
			prime_set.add(p);
		}
		for(int n=2; n <= maxx; n++){
			prime_count.put(smallestPrimeFactor(n),prime_count.get(smallestPrimeFactor(n))+1);
		}
		for(int p:prime_list){
			HashSet<Integer> temp = new HashSet<Integer>();
			temp.add(p);
			keys.add(temp);
			values.add(prime_count.get(p));
		}
		ArrayList<HashSet<Integer>> in_sets = new ArrayList<HashSet<Integer>>();
		ArrayList<HashSet<Integer>> out_sets = new ArrayList<HashSet<Integer>>();
		while(keys.size()>1){
			int tmp_index = 0;
			int min1_v = 0;
			int min2_v = 0;
			int min1_i = 0;
			int min2_i = 0;
			HashSet<Integer> min1_k = new HashSet<Integer>();
			HashSet<Integer> min2_k = new HashSet<Integer>();
			HashSet<Integer> min_union_k = new HashSet<Integer>();
			for(int v:values){
				if(tmp_index == 0 | v < min1_v){
					min2_v = min1_v;
					min2_k = min1_k;
					min2_i = min1_i;
					min1_v = v;
					min1_k = keys.get(tmp_index);
					min1_i = tmp_index;
				}else if(v < min2_v | tmp_index == 1){
					min2_v = v;
					min2_k = keys.get(tmp_index);
					min2_i = tmp_index;
				}
				tmp_index++;
			}
			min_union_k.addAll(min1_k);
			min_union_k.addAll(min2_k);
			in_sets.add(min_union_k);
			out_sets.add(min2_k);
			values.remove(Math.max(min1_i, min2_i));
			values.remove(Math.min(min1_i, min2_i));
			keys.remove(Math.max(min1_i, min2_i));
			keys.remove(Math.min(min1_i, min2_i));
			values.add(min1_v+min2_v);
			keys.add(min_union_k);
		}
		//now that we have a partition answer-key (mapping of in_sets to out_sets)
		//let's increment through the entire range of integers and compute the algorithm's performance
		System.out.println("done with partition answer-key, time elapsed = " + (System.currentTimeMillis()-t0) + " ms");
		int max_questions = -1;
		int min_questions = -1;
		int questions_sum = 0;
		for(int n=2; n <= maxx; n++){
			HashSet<Integer> prime_subset = new HashSet<Integer>();
			prime_subset.addAll(prime_set);
			int question_count = 0;
			int index = -1;
			while(true){
				question_count++;
				index = in_sets.indexOf(prime_subset);
				if( out_sets.get(index).contains(smallestPrimeFactor(n))){
					prime_subset.clear();
					prime_subset.addAll(out_sets.get(index));
				}else{
					prime_subset.removeAll(out_sets.get(index));
				}
				if(prime_subset.size() == 1){
					System.out.println("number = " + n + "  smallest factor (>1) = " + prime_subset.toArray()[0] + "  questions asked = " + question_count);
					if(question_count > max_questions){
						max_questions = question_count;
					}
					if(question_count < min_questions || min_questions == -1){
						min_questions = question_count;
					}
					questions_sum += question_count;
					break;
				}
			}
		}
		System.out.println("worst case   = " + max_questions + " questions");
		System.out.println("best case    = " + min_questions + " questions");
		System.out.println("average case = " + questions_sum + " / " + (maxx-1) + " ~= " + (float) questions_sum/(maxx-1) + " questions");
		System.out.println("time elapsed = " + (System.currentTimeMillis()-t0) + " ms");
	}
	public static int smallestPrimeFactor(int n){
		for(int p: prime_list){
			if(n % p == 0 ){
				return p;
			}
		}
		return 0;
	}
}

The code could be optimized for speed (particularly when obtaining the index in the partition list (in_sets) to use on out_sets, currently it’s dumb, but could be improved with some sort of hash-map).  With 166 integers, speed of execution was not an issue.

Both output:

done with partition answer-key, time elapsed = 0 ms
number = 2  smallest factor (>1) = 2  questions asked = 1
number = 3  smallest factor (>1) = 3  questions asked = 3
number = 4  smallest factor (>1) = 2  questions asked = 1
number = 5  smallest factor (>1) = 5  questions asked = 4
number = 6  smallest factor (>1) = 2  questions asked = 1
number = 7  smallest factor (>1) = 7  questions asked = 5
number = 8  smallest factor (>1) = 2  questions asked = 1
number = 9  smallest factor (>1) = 3  questions asked = 3
number = 10  smallest factor (>1) = 2  questions asked = 1
number = 11  smallest factor (>1) = 11  questions asked = 6
number = 12  smallest factor (>1) = 2  questions asked = 1
number = 13  smallest factor (>1) = 13  questions asked = 7
number = 14  smallest factor (>1) = 2  questions asked = 1
number = 15  smallest factor (>1) = 3  questions asked = 3
number = 16  smallest factor (>1) = 2  questions asked = 1
number = 17  smallest factor (>1) = 17  questions asked = 7
number = 18  smallest factor (>1) = 2  questions asked = 1
number = 19  smallest factor (>1) = 19  questions asked = 7
number = 20  smallest factor (>1) = 2  questions asked = 1
number = 21  smallest factor (>1) = 3  questions asked = 3
number = 22  smallest factor (>1) = 2  questions asked = 1
number = 23  smallest factor (>1) = 23  questions asked = 7
number = 24  smallest factor (>1) = 2  questions asked = 1
number = 25  smallest factor (>1) = 5  questions asked = 4
number = 26  smallest factor (>1) = 2  questions asked = 1
number = 27  smallest factor (>1) = 3  questions asked = 3
number = 28  smallest factor (>1) = 2  questions asked = 1
number = 29  smallest factor (>1) = 29  questions asked = 7
number = 30  smallest factor (>1) = 2  questions asked = 1
number = 31  smallest factor (>1) = 31  questions asked = 7
number = 32  smallest factor (>1) = 2  questions asked = 1
number = 33  smallest factor (>1) = 3  questions asked = 3
number = 34  smallest factor (>1) = 2  questions asked = 1
number = 35  smallest factor (>1) = 5  questions asked = 4
number = 36  smallest factor (>1) = 2  questions asked = 1
number = 37  smallest factor (>1) = 37  questions asked = 7
number = 38  smallest factor (>1) = 2  questions asked = 1
number = 39  smallest factor (>1) = 3  questions asked = 3
number = 40  smallest factor (>1) = 2  questions asked = 1
number = 41  smallest factor (>1) = 41  questions asked = 7
number = 42  smallest factor (>1) = 2  questions asked = 1
number = 43  smallest factor (>1) = 43  questions asked = 7
number = 44  smallest factor (>1) = 2  questions asked = 1
number = 45  smallest factor (>1) = 3  questions asked = 3
number = 46  smallest factor (>1) = 2  questions asked = 1
number = 47  smallest factor (>1) = 47  questions asked = 7
number = 48  smallest factor (>1) = 2  questions asked = 1
number = 49  smallest factor (>1) = 7  questions asked = 5
number = 50  smallest factor (>1) = 2  questions asked = 1
number = 51  smallest factor (>1) = 3  questions asked = 3
number = 52  smallest factor (>1) = 2  questions asked = 1
number = 53  smallest factor (>1) = 53  questions asked = 7
number = 54  smallest factor (>1) = 2  questions asked = 1
number = 55  smallest factor (>1) = 5  questions asked = 4
number = 56  smallest factor (>1) = 2  questions asked = 1
number = 57  smallest factor (>1) = 3  questions asked = 3
number = 58  smallest factor (>1) = 2  questions asked = 1
number = 59  smallest factor (>1) = 59  questions asked = 7
number = 60  smallest factor (>1) = 2  questions asked = 1
number = 61  smallest factor (>1) = 61  questions asked = 7
number = 62  smallest factor (>1) = 2  questions asked = 1
number = 63  smallest factor (>1) = 3  questions asked = 3
number = 64  smallest factor (>1) = 2  questions asked = 1
number = 65  smallest factor (>1) = 5  questions asked = 4
number = 66  smallest factor (>1) = 2  questions asked = 1
number = 67  smallest factor (>1) = 67  questions asked = 7
number = 68  smallest factor (>1) = 2  questions asked = 1
number = 69  smallest factor (>1) = 3  questions asked = 3
number = 70  smallest factor (>1) = 2  questions asked = 1
number = 71  smallest factor (>1) = 71  questions asked = 7
number = 72  smallest factor (>1) = 2  questions asked = 1
number = 73  smallest factor (>1) = 73  questions asked = 7
number = 74  smallest factor (>1) = 2  questions asked = 1
number = 75  smallest factor (>1) = 3  questions asked = 3
number = 76  smallest factor (>1) = 2  questions asked = 1
number = 77  smallest factor (>1) = 7  questions asked = 5
number = 78  smallest factor (>1) = 2  questions asked = 1
number = 79  smallest factor (>1) = 79  questions asked = 7
number = 80  smallest factor (>1) = 2  questions asked = 1
number = 81  smallest factor (>1) = 3  questions asked = 3
number = 82  smallest factor (>1) = 2  questions asked = 1
number = 83  smallest factor (>1) = 83  questions asked = 7
number = 84  smallest factor (>1) = 2  questions asked = 1
number = 85  smallest factor (>1) = 5  questions asked = 4
number = 86  smallest factor (>1) = 2  questions asked = 1
number = 87  smallest factor (>1) = 3  questions asked = 3
number = 88  smallest factor (>1) = 2  questions asked = 1
number = 89  smallest factor (>1) = 89  questions asked = 7
number = 90  smallest factor (>1) = 2  questions asked = 1
number = 91  smallest factor (>1) = 7  questions asked = 5
number = 92  smallest factor (>1) = 2  questions asked = 1
number = 93  smallest factor (>1) = 3  questions asked = 3
number = 94  smallest factor (>1) = 2  questions asked = 1
number = 95  smallest factor (>1) = 5  questions asked = 4
number = 96  smallest factor (>1) = 2  questions asked = 1
number = 97  smallest factor (>1) = 97  questions asked = 7
number = 98  smallest factor (>1) = 2  questions asked = 1
number = 99  smallest factor (>1) = 3  questions asked = 3
number = 100  smallest factor (>1) = 2  questions asked = 1
number = 101  smallest factor (>1) = 101  questions asked = 7
number = 102  smallest factor (>1) = 2  questions asked = 1
number = 103  smallest factor (>1) = 103  questions asked = 7
number = 104  smallest factor (>1) = 2  questions asked = 1
number = 105  smallest factor (>1) = 3  questions asked = 3
number = 106  smallest factor (>1) = 2  questions asked = 1
number = 107  smallest factor (>1) = 107  questions asked = 7
number = 108  smallest factor (>1) = 2  questions asked = 1
number = 109  smallest factor (>1) = 109  questions asked = 7
number = 110  smallest factor (>1) = 2  questions asked = 1
number = 111  smallest factor (>1) = 3  questions asked = 3
number = 112  smallest factor (>1) = 2  questions asked = 1
number = 113  smallest factor (>1) = 113  questions asked = 7
number = 114  smallest factor (>1) = 2  questions asked = 1
number = 115  smallest factor (>1) = 5  questions asked = 4
number = 116  smallest factor (>1) = 2  questions asked = 1
number = 117  smallest factor (>1) = 3  questions asked = 3
number = 118  smallest factor (>1) = 2  questions asked = 1
number = 119  smallest factor (>1) = 7  questions asked = 5
number = 120  smallest factor (>1) = 2  questions asked = 1
number = 121  smallest factor (>1) = 11  questions asked = 6
number = 122  smallest factor (>1) = 2  questions asked = 1
number = 123  smallest factor (>1) = 3  questions asked = 3
number = 124  smallest factor (>1) = 2  questions asked = 1
number = 125  smallest factor (>1) = 5  questions asked = 4
number = 126  smallest factor (>1) = 2  questions asked = 1
number = 127  smallest factor (>1) = 127  questions asked = 7
number = 128  smallest factor (>1) = 2  questions asked = 1
number = 129  smallest factor (>1) = 3  questions asked = 3
number = 130  smallest factor (>1) = 2  questions asked = 1
number = 131  smallest factor (>1) = 131  questions asked = 7
number = 132  smallest factor (>1) = 2  questions asked = 1
number = 133  smallest factor (>1) = 7  questions asked = 5
number = 134  smallest factor (>1) = 2  questions asked = 1
number = 135  smallest factor (>1) = 3  questions asked = 3
number = 136  smallest factor (>1) = 2  questions asked = 1
number = 137  smallest factor (>1) = 137  questions asked = 7
number = 138  smallest factor (>1) = 2  questions asked = 1
number = 139  smallest factor (>1) = 139  questions asked = 7
number = 140  smallest factor (>1) = 2  questions asked = 1
number = 141  smallest factor (>1) = 3  questions asked = 3
number = 142  smallest factor (>1) = 2  questions asked = 1
number = 143  smallest factor (>1) = 11  questions asked = 6
number = 144  smallest factor (>1) = 2  questions asked = 1
number = 145  smallest factor (>1) = 5  questions asked = 4
number = 146  smallest factor (>1) = 2  questions asked = 1
number = 147  smallest factor (>1) = 3  questions asked = 3
number = 148  smallest factor (>1) = 2  questions asked = 1
number = 149  smallest factor (>1) = 149  questions asked = 7
number = 150  smallest factor (>1) = 2  questions asked = 1
number = 151  smallest factor (>1) = 151  questions asked = 7
number = 152  smallest factor (>1) = 2  questions asked = 1
number = 153  smallest factor (>1) = 3  questions asked = 3
number = 154  smallest factor (>1) = 2  questions asked = 1
number = 155  smallest factor (>1) = 5  questions asked = 4
number = 156  smallest factor (>1) = 2  questions asked = 1
number = 157  smallest factor (>1) = 157  questions asked = 7
number = 158  smallest factor (>1) = 2  questions asked = 1
number = 159  smallest factor (>1) = 3  questions asked = 3
number = 160  smallest factor (>1) = 2  questions asked = 1
number = 161  smallest factor (>1) = 7  questions asked = 5
number = 162  smallest factor (>1) = 2  questions asked = 1
number = 163  smallest factor (>1) = 163  questions asked = 6
number = 164  smallest factor (>1) = 2  questions asked = 1
number = 165  smallest factor (>1) = 3  questions asked = 3
number = 166  smallest factor (>1) = 2  questions asked = 1
worst case   = 7 questions
best case    = 1 questions
average case = 494 / 165 ~= 2.99393939394 questions
time elapsed = 18 ms

Here we see that we can figure out the smallest positive integer divisor greater than 1 in under 3 questions on average with this methodology, even though the worst case is a little worse than our algorithm for part 1 of this puzzle.

I tried to keep the Java and Python code comparable (although not always asymptotically optimal) so we could have a rough comparison of performance. 

With 166 numbers, python does the job a little faster (18ms vs. 58ms), but for 16,600 numbers, Java is about 50% faster.  Java becomes an order of magnitude faster as we get to 166,000 numbers. 

This methodology impressively determines the smallest prime factor of any positive integer from 2 to 166,000 in ~4.04 questions on average (that’s over 15,000 primes)!

^source^

This data only counts people who have some income ^source^

^source^

^source^

Money and Education/Intelligence are essentially the ingredients to socio-economic class/success.

So given this data, it makes sense that a classist person would have significant preferences if the only known attribute is race.

Many may argue racism is inherent biologically as we evolved with the humanity that feels better around people looking similar to us, (which makes sense in a tribe in nature where you wouldn’t want to let your guard down with very different looking creatures that may not be friendly), data further below will make that a mute point for the purposes of this text. 

If we model a female as purely seeking social and economic status in a mate, her race preference would probably look something like this:

based on median income of males with income ^source^

or

based on mean income of males ^source^

Many may say yeah but woman aren’t seeking out economic security in a male these days… well lets have a look:

The following is actual response rate from females from a popular dating site with a sizable dataset:

Just to clarify this shows Asian woman respond at a higher rate to white men’s messages than Asian men’s messages.

The pie chart is a visualization for their racial preference when considering mates.

^source^

This data mostly matches our expected graphs based purely on income which supports the idea that females in this culture seek out mates by socio-economic status.  The exception is that Asian men seem to enjoy far less favor from all females than their academic and economic status would suggest. 

Here’s one bit of data that may explain it:

^source^

My angle hear suggests that while no reasonable person really has much of any reason to believe one race is “better” than another, racism persists in daily and social life primarily because of classism.  The way things are going in our culture, the fight against classism seems unwinnable, and maybe it shouldn’t be fought?

So I purchased some standard Crucial DDR3-1333  PC3-10600.

If you go to crucial’s website and you enter in a P55 motherboard, you will get this suggested memory:

CT2KIT25664BA1339

I ordered 2 4GB kits, each with with 2 2GB dimms.

The dimms all looked like this:

here is what CPUZ saw from the SPD of the dimm:

So, everything seemed fine until I started to get random reboots every couple days.

I tried every possible combination of the dimms, and I always got the same result; hard-reboots.

I felt the odds of all 4 dimms being faulty is roughly zero, so I decided it must be the motherboard, until I started reading these comments on newegg about my memory.  There are/was a very high percentage of people claiming the memory did not work on their P55 motherboard.

Then I started to see newegg stamp certain memory P55 Core i5/i7 compatible, which didn’t seem to make sense, because any memory that adheres to JEDEC spec for PC3-10600 should be compatible.¿?

I found Intel’s own Validation Results for DDR3-1333 on P55 here.

It lists Crucial’s CT25664BA1339, but specifically the CT25664BA1339.16FF.

Looking closer at my memory I found it to be CT25664BA1339.M16SFD.

for reference this dimm uses micron chips with markings: 9ND22 D9JNM

Crucial said the last string of this part number is for internal use only, and refers to which chip/set is being used on the dimm.  The crucial representative said it should make no difference with respect to P55 compatibility, and was perplexed why Intel would specifically approve the 16FF.  In fact as a consumer you cannot even see what the internal chipset number is before you buy online, but you can call and ask to order a specific one over the phone.

I did just that, and ordered a set of CT25664BA1339.16FF over the phone from crucial, they looked like this:

Notice the Micron label on the left?  I assume this means the dimm itself was manufactured by Micron, and resold by crucial.

(my other CT25664BA1339.M16SFD dimms don’t have a micron sticker.)

The CT25664BA1339.16FF dimm uses different micron chips marked: 9NF22 D9KPT

So the Crucial CT25664BA1339.16FF is in fact a Micron MT16JTF25664AZ-1G4F1 dimm.

CPU-Z’s information from the SPD agrees:

It is no surprise that both the Crucial CT25664BA1339.16FF and the Micron MT16JTF25664AZ-1G4F1 passed Intel’s validation tests, as they are the exact same dimm:

These new Micron dimms seem to run fine in my system without any problems.

I still don’t know why the P55 chipset/CPUs have problems with the non-16FF crucial dimms.  So I by no means really understand the root of the issue, but I thought others might find this interesting. 

The memory Crucial will send you for a P55 system may not be the memory you want. 

It also seems that many DDR3 kits that seem fine otherwise, do not work right with the P55.

Software>

Proof of concept www.wolframalpha.com shows a taste of the future of querying data.

Windows 7 which is a refined build of Windows Vista is the best Desktop OS.

Google Chrome 3 is by far the best consumer web browser.

Google Voice provides 1 number with voice, voicemail, and SMS capability.  Those can be forwarded to a mobile phone if desired.  There is a Google Voice application for android which lists text messages and voicemails for you to read/listen/delete/reply-to individually (it transcribes voicemails so you can read them before you choose to listen).  Using this application, SMS’s and voicemails are transmitted over DATA, so they do not count as a text messages in your plan.  The whole system has a web interface for you to send and view text messages, voicemails and call history.  It will also allow you to keep in touch with SMS/voicemail while you travel outside of your cell phone service coverage.

Storage>

Seagate has 500GB platters which it uses in products like:

• 3.5” 7200rpm 1TB @$90
• 3.5” 5900rpm 2TB @$200

Intel has launched their 2nd Generation MLC Solid State Disk using 34nm flash (as opposed to 50nm)

• 2.5” 80GB @$230
• 2.5” 160GB @$450

These new Intel drives support something called TRIM, which is also supported in Windows 7.  Without Trim, when a file is deleted, the TOC is updated to consider that area on the drive empty, the data isn’t actually wiped.  This is fine for rotating discs because the drive will simply over-write those bits when a new request is received.  On current SSDs there is a problem, because blocks must actually be erased before a write, so when a request to write data on the previously used space, it must first erase the area, then write, and this costs time.  TRIM tags the areas of the drive where the data was deleted, and the drive will (on its own time) erase those blocks of bits.  This means in some cases a block won’t need to be erased prior to write, since the drive actually erased it on its own time.

This is good, but you should know that if there is live data in the vicinity of a write, the SSD must still read the entire block into memory, erase the block, add the new data to the data in memory, then write the entire block.  The push should be for reducing the block sizes, to reduce the time-tax in random writes.  Intel AFAIK has the smallest block size around.  I’ll review this new Intel SSD soon.

Memory>

DDR3 has arrived at reasonable price points.

• Crucial 4GB (2x2GB) DDR3-1333 kit @$65
• Crucial 4GB (2x2GB) DDR2-800   kit @$53

what DDR3 desperately needs is higher density, supposedly reasonably priced 4GB dimms will arrive in the coming months with Samsung chips.

CPU/Platforms>

We are in a weird space now.

Last year Intel launched its revolutionary 45nm Nehalem CPU which features an integrated memory controller.  These chips launched with a very high-end and expensive x58 platform.  Due to the price of the platform and (at the time) expensive DDR3 memory, this platform never really hit the average or value conscious consumer.

Because of this, most computers sold are using a relatively old Penryn CPUs built on 45nm technology without an integrated memory controller.  These CPUs have been for sale since January 2008!  And the Penryn was just a die-shrink of the Conroe which was famously launched in the summer of 2006.  Great for 2006, but it’s been a long time.

In the coming weeks Intel will launch consumer-oriented Nehalem-based CPUs (Lynnfield).  They will be slightly improved, slightly cheapened versions of the current Core i7.  The new platform is the Intel P55 with a new socket (LGA1156) supporting the double channel memory controller (as opposed to 3x in the current i7).

These new chips are still 45nm.

That’s all well and good for high end consumer PCs and big and clunky laptops, but for thin-light mobile notebooks it doesn’t do that much, these are still 45nm, and they aren’t even attempting a Low or Ultra-Low Voltage variant.  And the normal voltage new chip will still require 3 separate chips to complete the platform (including video = GPU).

What’s interesting is around January intel is releasing the 32nm Family of processors with GPU (graphics processor) integrated in the CPU package! 

This reduces the number of major chips needed to 2 for the entire platform, and these chips will be lower power due to the die shrinks.

It’s called Westmere, and while desktop and clunky laptops will also get their own models, they don’t need it nearly as much.

here are some Westmere Desktop options available in January:

GPU performance on Westmere will be roughly double that of the modern x4500HD, it also ads some video decoding features.

Here’s the picture for the Ultra-Low-Voltage space (think Macbook /Air and smaller) dual cores. (~10W for CPU duties, ~8W for GPU)

Exciting times after Christmas for thin and light laptops like the Acer Timeline 13.3”, Dell adamo, MacBook Air, ThinkPad x301, etc.

So in the thin notebook segment there will be a massive improvement on the platform in about 6 months, what about Netbooks with the ATOM?

Currently the atoms are a bit too slow to be useful in a mini-notebook and use a bit too much power for small gadgets.

In the coming few months there will be new Atom processors, still using 45nm tech, but will have an Integrated Memory Controller, and an Integrated Graphics Processor, both on-die!

Drastic decrease in power usage for the platform, down to 2 chips instead of 3… should allow for fan-less designs.  The atom finally becomes modernized!  May be still slower than desired.  In 2010 we should see 32nm Atoms.

So huge improvements in the netbook space to come real soon!

I havn’t talked about AMD, currently they are not competitive in the low-power mobile space (in fact they don’t have any 45nm parts, so they can’t compete on energy efficiency).  But they have migrated to 45nm on the desktop and probably have the best integrated platform out there.  Speaking of the 785g chipset paired with a 45nm AMD CPU, if you need an inexpensive and quick desktop today, buy this.

AMD has this corner dominated until Intel releases Westmere after Christmas.

Mobile Phones:

currently only 3 worth mentioning:

• iPhone 3GS
• Palm Pre
• HTC/T-mobile G1 and myTouch 3G

The next 6 months will prove interesting as around 6 more Google Android mobile phones will be released on T-mobile, AT&T and Sprint.

The verbal does not have a similar flaw.

the results from everyone who is trying to get into a graduate program:

clearly there is a problem here where the most common score of all test-takers is the maximum.

let’s take a closer look at how this makes the GRE Quantitative even less useful for specific graduate programs:

quantitative:	verbal:
notice in the students pursuing a PhD in math, computer science or electrical engineering, the quantitative exam is too easy, too many students are binned together at the highest score simply cause the test is too easy for them.	interestingly the above fields have 2 humps in verbal, i imagine the first hump is from non-native English speakers going into these fields of study, the 2nd hump is likely the native English speakers.
With philosophy PhD students here we see a more desirable distribution, but still, the perfect is almost as frequent as the mode.	A relatively normal distribution, only 1 hump and the perfect is far from being the mode.
in the 4 areas of study above, the quantitative GRE exam does a good job at differentiating the the people.  The distributions are very normal, with the max and min score occurring far less than the mode.	Even in the fields of study which attract the most verbally talented people, the verbal GRE test doesn’t break down, it still yields relatively normal distributions where the mode is far more common than the max or min.

lets do a real basic analysis of what’s going on:

the actual distribution of quantitative ability probably looks something like this:

note: normal curves have no maximum or minimum value of ability, just like there is no maximum IQ value, its just insanely unlikely to have an IQ of , say , 500… but still possible.

With practical limitations like a finite time limit, I can understand the need for bounds on the scores.

When you set a maximum, everyone with an ability higher than the maximum shall now be bundled at that maximum value, so lets look at what that will look like with a max=800 and min=200:

here you see unnaturally high probability to achieve a 200 and an 800,  the combined probability to score higher than the maximum will be lumped into that one score.  This cannot be avoided, but the number of people who would naturally score higher than the max can be minimized as to not be too significant, like the verbal GRE does.

So Why is the Quantitative so much worse than the Verbal GRE??

well the Verbal GRE has a mean of 477, almost equidistant to the max and min, while the quantitative has a literal (but misleading) mean of 579, so the entire distribution is nudged closer to the maximum boundary,  its also a bit wider than the verbal (higher std dev)

see the massive data point at an 800 score?  its value is equal to the accumulated area under entire tail end of the curve (above 800).

which of course looks very similar to the actual GRE Quantitative distribution:

so this is a fundamental issue with the test and should be corrected.

It can be fixed by lowering the mean to ~500 by making all questions more difficult across the board.

for those interested, the plots were done in maple of testdist2, where:

and

testdist2 := (min, max, x, mean, stdv) -> piecewise(x = min, int(distr(y, mean, stdv), y = -infinity .. min), min < x and x < max, int(distr(y, mean, stdv), y = 10*floor((1/10)*x) .. 10*floor((1/10)*x)+10), x = max, int(distr(y, mean, stdv), y = max .. infinity), 0) ;

using a plot command like this:

mean1 := 579; stdv1 := 130; gremax := 800; gremin := 200; plot(testdist2(gremin, gremax, x, mean1, stdv1), x = gremin .. gremax, numpoints = 100, style = point, symbol = cross, symbolsize = 8, labels = [ability, `~probability`], title = "Normal Curve with mean of 579, std deviation of 130, score increment = 10")

Lawns are stupid: we destroy nature, what has been there far longer than Europeans on these lands, to try to grow a plant which will not survive without all sorts of chemicals, machinery and energy to protect it, to show others that we too adhere to the same cultural standard for "well-kept" land, at the sacrifice of nature and the environment.

I’ve said it before but these kind of ground keeping is an arms race of suburbia where we all lose.

Isn’t sustainable nature beautiful?
Who’s really impressed with a lawn of cut grass?

*>?

So I wanted to see how fast they are in the immensely popular javascript:

<–relative speed. (higher is better)—>

OS: windows 7 64-bit b7048
RAM: 4GB DDR2-800
CPU: intel 2-core 3Ghz Penryn w/6MB cache
HDD: Samsung F1 7200rpm
Chipset: intel G45

v8 is http://v8.googlecode.com/svn/data/benchmarks/v3/run.html

sunspider is http://www2.webkit.org/perf/sunspider-0.9/sunspider.html

dromaeo JS is http://dromaeo.com/?dromaeo

dromaeo DOM is http://dromaeo.com/?dom|jslib|cssquery

(ie and safari 3 were not able to complete the dromaeo DOM test suite w/default settings)

note:

the 64-bit firefox I tested is not official; http://www.mozilla-x86-64.com/

google chrome 2.0.269.0 is a dev/beta build.

opera, IE, chrome, firefox, k-meleon, safari are all 32-bit unless otherwise noted.