Prime number puzzle
 

my kid brought home a prime number puzzle that i'm trying
to work out using excel....we have 5,7,11,13,17,19,23 in
the form of an H such that the 2 columns and the 2
diagonals add up to the same prime number....i was
thinking of writing a VB program to solve this but i'm not
sure how to randomly generate this set of prime numbers,
any ideas.....thx

If you list the prime numbers in a column, you can randomly retrieve
them with this technique:

http://www.mcgimpsey.com/excel/randint.html


In article ,
"johnT" wrote:

my kid brought home a prime number puzzle that i'm trying
to work out using excel....we have 5,7,11,13,17,19,23 in
the form of an H such that the 2 columns and the 2
diagonals add up to the same prime number....i was
thinking of writing a VB program to solve this but i'm not
sure how to randomly generate this set of prime numbers,
any ideas.....thx

With a Capital "H", and only 7 numbers, I assume your array index is
numbered like this.

1,_,5
2,4,6
3,_,7

I don't show a solution if you include adding the horizontal line indexed as
2,4,&6
I only show 4 solutions.

{5,19,17,13,11,7,23},
{11,7,23,13,5,19,17},
{17,19,5,13,23,7,11},
{23,7,11,13,17,19,5}

where index 1+2+3 = 5+6+7 = 1+4+7 = 3+4+5

HTH
--
Dana DeLouis
Win XP & Office 2003


"johnT" wrote in message
...
my kid brought home a prime number puzzle that i'm trying
to work out using excel....we have 5,7,11,13,17,19,23 in
the form of an H such that the 2 columns and the 2
diagonals add up to the same prime number....i was
thinking of writing a VB program to solve this but i'm not
sure how to randomly generate this set of prime numbers,
any ideas.....thx

johnT wrote:
my kid brought home a prime number puzzle that i'm trying
to work out using excel....we have 5,7,11,13,17,19,23 in
the form of an H such that the 2 columns and the 2
diagonals add up to the same prime number....i was
thinking of writing a VB program to solve this but i'm not
sure how to randomly generate this set of prime numbers

Why do you want to select randomly?

The best way to solve the problem is an exhaustive
enumeration of the permutations.

If "H" is represented by a 7-element array or 7 variables,
where {h1, h2, h3} and {h5, h6, h7} are the left and right
sides and h4 is the crossbar, find all arrangements of the
above prime numbers such that h1+h2+h3 = h5+h6+h7
= h1+h4+h7 = h5+h4+h3, and the sum is a prime number.

Your child(!) should first determine how many possible
permutations there are. The answer is 7! = 7*6*5*4*3*2*1
= 5040.

But your child can reduce the number of trial solutions at
least in half (2520) by using good strategy, namely by
first looking for the diagonals that meet the condition.

And in fact, by applying some simply heuristics, your child
could reduce the number of trials solutions to 840.

The heuristics are exactly how we might solve the problem
exhaustively manually. After generating 4 of the diagonal
elements (h1, h3, h4, h5), we can quickly compute the
necessary remaining elements (h7, h2 and h6) based on the
sum h3+h4+h5 and determine if they are among the unused set
of prime numbers.

A random approach __might__ find __one__ solution in fewer
trial. But there is no guarantee of that, especially if
your random algorithm fails to exclude duplicates. It is
not a good approach to teach your child.

Of course, a manual approach could reduce the number of
trial solutions even further by selecting one diagonal set
and excluding any set where the sum is not a prime number.

In that case, your child could compute the number of sets
of 3 prime numbers ("7 choose 3" = 7! / (7-3)! / 3! = 35),
easily generate them and exclude the ones whose sum is not
prime, then place the permutations of the remaining sets
(21) in the "H" formation.

In fact, since the solution requires 4 such sets of 3 with
the same sum, there are only two groups of 4 to consider:
one group that sums to 41, and one group that sums to 47.
This approach, which is difficult for computer programs,
reduces the number of trial solutions from 5040 to less
than 8.

I suspect that is what the assignment is all about:
finding strategies that make the solution tractable, with
or without the use of a computer.