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

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.
	tle="english_v" border="0" alt="english_v" src="http://www.alternativerecursion.info/wp-content/uploads/2009/05/english-v1.png" width="495" height="367" />
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")