### Random Post

### Recent Posts

### Recent Comments

### Archives

### Categories

- article (11)
- enigma (1,158)
- misc (2)
- project euler (2)
- puzzle (40)
- site news (44)
- tantalizer (42)
- teaser (3)

### Site Stats

- 177,972 hits

Advertisements

Programming Enigma Puzzles

11 September 2013

Posted by on **From New Scientist #2934, 14th September 2013** [link]

I have listed in random order five positive integers, four of two digits and one of one digit. They use each of the digits 1 to 9. None of the two-digit integers has any factor greater than 1 in common with any other of the two-digit integers. The first of the integers in my list is a triangular number. The sum of the first two, the sum of the first three, the sum of the first four and the sum of all five are also triangular numbers.

What are my integers in the order in which I have listed them?

[enigma1766]

Advertisements

%d bloggers like this:

I’m glad to see the puzzles are becoming a little more challenging. The difficulty here is keeping track of all the conditions. This recursive Python program runs in 39ms.

Solution:The list of integers is: 6, 49, 23, 58, 17.Pretty similar to Jims version.

Execution time is better than its previous version.

This non-recursive version is a lot slower than the recursive solutions.

if speed or time does matter too much, I did write this in C++,

No particular point here, just some musings on the timing of code…

Compiling this C++ code and running the same timing procedure that I run on my Python programs on the resulting program reports that it takes 8ms to run (about 5 times faster than my Python program). However I expect the vast majority of this time is taken up with the housekeeping that the operating system does to run the process, rather than the time taken to actually solve the problem.

But, you could argue that Python program is being unfairly disadvantaged by this comparison, as we’re measuring the execution time of a piece of compiled native code, not the program as it was originally written. If I measure the time taken to compile the C++ program to native code (using the default compiler settings), that comes to 193ms, giving an overall time of 201ms. So we could equally say that the Python code is 5 times

fasterthan the C++ code, if the time taken to compile the code is taken into account.What I am trying to say this, if the speed is important to us, the execution speed sure, I am talking about that, then no need to use C++

The code is not so optimum, it can be speeded up assembly routines inline, and or cpu registers

I have not written that to be compared with Python, I guess no need to make a comparison

I agree that Python is easy to use, whereas programming in C++ requires more knowledge I guess

No need use Python, I was going to say instead no need to use C++, sorry

I just saw this and I think it might be useful to clarify that an exhaustive computer search is probably as time consuming to construct as a solution as below (I did use Excel to make the first table). I have on the x- and y-axes, the triangular numbers up to 496 – I stopped when the differences became mostly 3 -digit numbers. The body of the matrix is the difference between the top row of the matrix (the triangular numbers) and the left side column (the triangular numbers again). I don’t need to consider more than the top right triangle of the matrix, not interested in 0 or negative numbers for differences

I can’t paste the table here, but here is how it looks for a few rows and columns

etc

Now from the body of the matrix, eliminate differences with

– repeated digits

– anything with 0 in it

– anything where the left side is a single digit number and the difference is also a single digit number (since there is only one single digit number)

Now, we would have the first number be a two digit number and the second could be one digit. Or the first number could be one digit and the second could be two digit. A moment’s inspection reveals that you can’t have a situation where the third or higher number is one digit – it doesn’t work.

In the first case, the choices are

Number 1=> 10 15 21 28 36

Number 2=> 5 6 7 8 9

The pair 1(10,5) doesn’t work – 10 has a zero in it.

The pairs (15,6), (21,7), (36,9) are not co-prime

The pair (28,8) has 8 repeated

So, the first number has to be a single digit number.

There are 18 possibilities.

10 are eliminated either because digits repeat (you have to have 1,..9, no repeats) or they are not co-prime

The only one that survives is 6,49,23,58,17

It looks like the tabs just vanished in the table after I saved the comment down… Hmm. Let me know if the argument is not clear.

The whitespace was retained, so I was able to surround the table with

<pre> ... </pre>tags to bring back the formatting.ah, thanks! I looked at the change on my iPhone when I noticed your message – It didn’t look good on my iPhone, though why anyone would want to look at a coding-based web page on an iPhone, I don’t know!

I found a solution in MiniZinc with the first permutation I tried of the five integers.

However, this is not a rigorous solution, as it does not check all the permutations of the five integers – this enigma was a bit tricky in MiniZinc.