### Random Post

### Recent Posts

### Recent Comments

### Archives

### Categories

- article (11)
- enigma (1,367)
- misc (4)
- project euler (2)
- puzzle (90)
- puzzle# (48)
- site news (58)
- tantalizer (94)
- teaser (7)

### Site Stats

- 233,130 hits

Programming Enigma Puzzles

7 March 2012

Posted by on **From New Scientist #2855, 10th March 2012** [link]

The numbers 38 and 77 are each the product of two primes; furthermore their difference (39) and their sum (115) are also each the product of two primes, and the eight primes involved are all different.

There is one other pair of two-digit positive integers for which all this is true. What are those two integers?

[enigma1688]

%d bloggers like this:

The following Python program runs in 38ms.

Solution:The other pair of 2-digit integers is 39 and 94.Here’s a solution using the Prime Sieve, that I’ve recently added to the

enigma.pymodule:Here is my version:

Wow, how compact these Python codes are.

I tackled the problem using Microsoft Visual C# which I am learning.

Here is a link to my own comparitvely amateurish coding of the solution to Enigma 1688 written for Visual C# 2008 Express (& C# 2010 Express):

http://homepage.ntlworld.com/p.caine1/1688.html

One of the things I like about Python is its compactness. Of course my solution uses routines from my own

enigma.pylibrary for generating primes, so that makes it a bit smaller (although Brian fitted a 2 line prime sieve into his solution). Python also has a nice standard library that includes lots of useful stuff for solving these puzzles.My algorithm is also a bit less complicated than yours (for example, I didn’t look for products of different parity), but my code ran in 38ms, so I didn’t bother tweaking the algorithm further.

When I was asked to help to solve the Enigma 1688 puzzle I didn’t know where to begin, hence the use of Excel.Looking at the distribution of products of the primes in the cells I saw the different parities.

Now Odd+(or-)Odd both give Even numbers, so there would be a repeat of the prime factor 2. Therefore just one of the numbers must be even. I thought then that any “algorithm” would include parity

Even so the number of cases to examine still seemed daunting. Thats when I decided to code the problem and naturally included the parity aspect.I learned a lot about Visual C# during the coding process.

I checked (extending my knowledge of C# again!) and my code ran in 8 ms to 14 ms (more with printing)

I only tried the timing on four occasions {8,9,14 & 9ms}. I employed the Microsoft StopWatch function

.

Here is a sample of the new code ouput:

********************************************************************

Operations timed using the system’s high-resolution performance counter.

Timer frequency in ticks per second = 14318180

Timer is accurate within 69 nanoseconds

39,38,77,115

//Other solution

Time in milliseconds =9

********************************************************************.

The Timer accuracy was a huge surprise to me.

The run time however is not of particular interest to me, after all the code results are immediate.

At this time I have no idea of how to improve my code (other than tidy it).

My main interest is in learning C# and it was a bonus getting the solution to this puzzle.

Timings for different codes (Python,C# etc) must, at least, be processor dependent.

Here’s my Python code with the list of numbers split into even and odd candidates, and then the candidate pairs are constructed by choosing one number from each list. It cuts down the candidate pairs considered by around half, from 406 (= C(13 + 16, 2)) to 208 (= 13 x 16). Although this has a negligible effect on the runtime of the program for this particular puzzle, if there were a much larger set of candidate numbers it would run noticeably faster.

I edited my code to remove the use of parity as part of the algorithm.

My new code 1s now 198 lines long, poor in comparison with your Python code

I moved the code to my notebook(circa 2006). Here is the result

********************************

Operations timed using the system’s high-resolution performance counter.

Timer frequency in ticks per second = 3579545

Timer is accurate within 279 nanoseconds

39,38,77,115

//Other solution

//Other solution with reorder of items 2 and 3.

39,77,38,115

Time in milliseconds =43

********************************

This result is now comparible with your run time of 38 milliseconds.

One thing is sure, after teaching myself C#, I’ll be learning Python!