### Random Post

### Recent Posts

- Enigma 1109: All square in games
- Enigma 402: A DIY puzzle
- Puzzle 71: All wrong, all wrong
- Enigma 1110: Dots and lines
- Enigma 400: Potential difficulties
- Tantalizer 479: Cat and five tales
- Enigma 1111: Base-age
- Enigma 399: Time, gentlemen, please
- Tantalizer 480: Pitter patter
- Enigma 1112: Patio zones

### Recent Comments

Jim Randell on Enigma 1653: Cut-free | |

Jim Randell on Enigma 1109: All square in… | |

Jim Randell on Enigma 402: A DIY puzzle | |

geoffrounce on Puzzle 71: All wrong, all… | |

Jim Randell on Puzzle 71: All wrong, all… |

### Archives

### Categories

- article (11)
- enigma (1,080)
- misc (2)
- project euler (2)
- puzzle (21)
- site news (42)
- tantalizer (21)
- teaser (3)

### Site Stats

- 157,134 hits

A very straightforward programmed solution gives the answer. This Python program runs in 42ms.

Solution:The three two-digit numbers are 17, 18 and 19.Hardly worth an alternative but here is one:

Instead s=3*a, s=a+a+a should be used, integer addition is always faster than integer multiplication

And in the second loop, your loop end is s+1, no need to go s+1, just s//2+1

This small code is not optimum, there are more indeed

Your second loop starts from 1, really necassary to start from 1, obviously not, still not optimum

Not” and “or” used in your if clause, and” is so simple, and it works, you have used not, this one means one more operation.

And one crucial thing, s and p are both divisible by i+1, then why do you not use this fact? it needs optimization,

Not always. In fact in this specific case the repeated addition is slightly slower than the multipication:

OUr self professed algorithms expert has just spent hours ‘optimising’ my code, the original of which (when timed with Jim’s enigma code) gives:

C:\temp>brg.py

17 18 19

[timing] elapsed time: 0.0019237s (1.92ms)

His recommended optimisations result in the code:

which now gives:

C:\temp>brg.py

13 14 15

21 22 23

25 26 27

33 34 35

37 38 39

45 46 47

57 58 59

61 62 63

73 74 75

81 82 83

85 86 87

93 94 95

[timing] elapsed time: 0.0029311s (2.93ms)

So our resident ‘expert’ has just spent hours of his time ‘optimising’ my program in an amusing attempt to prove he knows more about programming and algorithms than me only to produce a result that is not only a lot slower but is now incorrect!

[deleted]Spend hours, ha ha, five minutes look 🙂

This is Brian’s code optimisation, I forgot to check p whether dividible by s or not

Of course if we continue along these lines we would end up only looking for divisors f up to sqrt(s), and also checking to see if s//f is also a divisor of p (where f is not equal to sqrt(s)).

This is in fact what the

divisors()function inenigma.pydoes to make its list of divisors. So you could use:Or to squeeze a bit more performance out of it you could rip the guts out of

divisors()and include it in the loop, to save on a function call, and exit early if more than 6 divisors are found.Although it seems like a lot of bother to go to for code that runs in a tiny fraction of a second anyway.

I agree with Jim that it makes no practical sense to spend a lot of time optimising a program that runs in 2 milliseconds.

But if I really need to do this, we should not worry too much about the inner section when there is much more to be gained by cutting down the numer of times the outer loop runs:

which gives:

>test.py

17 18 19

[Ahmet’s Optimisations] elapsed time: 0.0011840s (1.18ms)

[Brian’s Optimisations] elapsed time: 0.0000652s (65.17us)

which is 18 times faster.

Hi Brian,

Anybody can write the fastest code when you are given time, I did optimize it with a 5 minute look,

the point is to be able to see things at once, for example, your loop starts from 1 in the previous code, and no need for that,.

I am talking about a general approach, the loop ending not 98, as I said it several times.

Sadly,that optimistic! (fortunately it seems we are each allowed one mistake Ahmet).:

>test.py

17 18 19

17 18 19

[Ahmet’s Optimisations] elapsed time: 0.0010726s (1.07ms)

[Brian’s Optimisations] elapsed time: 0.0003535s (353.46us)

which is a factor of close to three faster.

Congratulations! :))

Sadly adding both optimisations doesn’t get much more speed:

>test.py

17 18 19

[All] elapsed time: 0.0003422s (342.23us)

the important thing is this: s//2, it cuts the search place into 2.

[deleted]I think it is incorrect to only consider divisors up to s//2. You also need to consider s itself.

For example if n = 10, s = 10 + 11 + 12 = 33, p = 10 × 11 × 12 = 1320. And common divisors of s and p are (1, 3, 11, 33). So if you only look for divisors up to 16 you are missing 33. If the program had asked for a sequence where there were four common divisors of the sum and the product, the “optimised” code would only find 3 (it would calculate 3 and 11 and assume 1).

This is a good example of making what is apparently a small optimisation, but by reducing the clarity of the code we have introduced a slightly non-obvious bug into it, which is not apparent in solving the original problem, but if the code were adapted to solve a similar but different problem we may get incorrect results. This is why I value clarity in my solutions above raw speed. (And let’s face it – if we were really concerned about minimising execution time, we wouldn’t be using Python).

As a side note, let’s keep the comments here focussed on the civil discussion of the the problem at hand. I’ve got an administrators hat around here somewhere…

Hi Jim,

[deleted]Anyway, sure, s is to be considered itself, but, s//2 is playing very important role, it is obviously clear, no need to search something where it is impossible to be found, s can not divide numbers between s//2+1 and s-1, this is very clear

Ahmet, the point about keeping comments civil and focussed on discussion of Enigma problems was not specifically aimed at you. It is a general comment for all contributors to the site. Sorry if I didn’t make that clear.

But I also think my point about simple optimisations introducing subtle bugs stands. While it might be “very clear” that we don’t need to consider divisors between s//2 + 1 and s – 1, the code you posted above strips out these

ands itself, so must be considered flawed, even through at first glance it seems a reasonable optimisation, and indeed produces the correct result. We can, of course, fix up such corner cases in the code, but in the end the optimised code, when correct, will be harder to explain and re-use than the original.Jim,

What about Brian’s miller rabin text, is it related to here?

I’ve removed the comments about implementation of the Miller-Rabin algorithm, and also some sections of other comments that weren’t contributing to the discussion.

I hope this incident will not detract from everyone’s enjoyment of programming Enigma puzzles.

You just have thought when the loop has ended at 98, you must think a general solution, if that was 100000, your solution down, this is so simple.

[deleted]Sorry, but I’ve had to remove some of the comments from this thread, as they weren’t directly related to the discussion of Enigma 1727. There are also some comments which I have trimmed to allow them to remain, but if you would rather I removed them instead you can let me know.

And again, in Haskell. (I just found an old NewScientist …)

Thanks for posting your code. I’m not too familiar with Haskell – although I’ve just downloaded the Haskell Platform so I can learn more about it. It doesn’t look like the definition of

factorsmade it into the comment correctly. I’m happy to fix-up the comment if you let me have a corrected version.Here is a Mathematica version

The {0.,Null} just indicates it was too quick to get a time for completion.

Paul.

Hi Paul. Welcome to Enigmatic Code!

Thanks for posting your Mathematica solutions.

I’ve been meaning to find out more about Mathematica, and since it became available for free on the Raspberry Pi I now have access to a copy. Maybe this will push me to find out a bit more.

On my Rasberry Pi if I evaluate your expression (without the

Break[]) it reports a runtime of 0.15s:Although if I put the expression into a file and run it from the command line, then it takes about 12s, so there’s quite a start-up penalty for using Mathematica as a scripting language!

If I remove the

Break[]it runs in{0.015600, Null}. However, once it has run MMA remembers it and if I was to run it again during any session it will be almost instant, within reason, as in don’t overwrite variables.If you were to run this as a scripting language I would say go and make a cup of tea and come back given those timings.

That takes 1.65 seconds to set the first million primes to ‘a’. If you were to type

a[[12345]]once it has run it will give you the 12345th prime, it should be 132241.btw I love these kind of problems and so glad I found you, you just got to love Google.

I intended to do some preliminary analysis to produce some simple code, but ended up with a complete analysis:

Consecutive numbers n-1, n, n+1, have sum S=3n and product P=n(n^2-1)

So all divisors of n divide both S and P. n^2-1 and n are coprime so no divisors of n are divisors of n^2-1.

There are three cases:

A) n has 5 divisors and 3 is a divisor of n^2-1. For n to have 5 divisors, n= p^4 for prime p, i.e. n= 16 or 81.

n=81 is ruled out as 3 does not then divide n^2-1

n=16 is ruled out as the sum of the six common divisors is then even.

B) n has 6 divisors, n= p^5 for prime p, i.e. n=32,

n=32 is ruled out as then 3 divides S, giving more than 6 common divisors of S and P

C) n has 6 divisors, n=p^2q for primes p,q, one of which is 3.

One of p,q must be 2, as two odd primes produce an even sum of divisors.

So n= 2^2×3 =12 or 3^2×2 =18.

n=12 produces an even sum of divisors, so n=18, and the consecutive numbers are 17,18,19