Enigmatic Code

Programming Enigma Puzzles

Enigma 1727: Common factors

From New Scientist #2894, 8th December 2012 [link]

I have in mind three consecutive two-figure numbers and I have calculated their sum and their product. I have then listed those positive integers which divide exactly into both that sum and product. It turns out that there are just six numbers in that list and that the sum of the six numbers is odd.

What are the three consecutive two-figure numbers?

[enigma1727]

Advertisements

32 responses to “Enigma 1727: Common factors

  1. Jim Randell 5 December 2012 at 6:22 pm

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

    from enigma import irange, divisors, printf
    
    for n in irange(10, 97):
      # calcuate the sum and product
      s = n + (n + 1) + (n + 2)
      p = n * (n + 1) * (n + 2)
      # common divisors of the sum and product (s < p)
      d = list(x for x in divisors(s) if p % x == 0)
      # there should be 6 of them
      if len(d) != 6: continue
      sd = sum(d)
      # and their sum should be odd
      if sd % 2 == 0: continue
    
      printf("n={n} s={s} p={p} d={d} sd={sd}")
    

    Solution: The three two-digit numbers are 17, 18 and 19.

  2. Brian Gladman 5 December 2012 at 8:58 pm

    Hardly worth an alternative but here is one:

    for i in range(10, 98):
      # the sum and the product of i, (i + 1) and (i + 2)
      s, p = 3 * (i + 1), i * (i + 1) * (i + 2)
      # list numbers that are factors of both
      d = [f for f in range(1, s + 1) if not (s % f or p % f)]
      # look for six common factors with an odd sum
      if len(d) == 6 and sum(d) & 1:
        print(i, i + 1, i + 2)
    
    • Brian Gladman 10 September 2013 at 9:14 am

      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:

      from enigma import timer
      
      timer.start()
      
      for i in range(10, 98):
        # the sum and the product of i, (i + 1) and (i + 2)
        a = i + 1
        s, p = a + a + a, i * a * (a + 1)
        # list numbers that are factors of both
        d = [f for f in range(2, s // 2 + 1) if s % f == 0 and p % f == 0]
        # look for six common factors with an odd sum
        if len(d) == 6 and sum(d) & 1:
          print(i, i + 1, i + 2)
          
      timer.stop()
      

      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]

      • saracogluahmet 10 September 2013 at 9:34 am

        Spend hours, ha ha, five minutes look 🙂

      • saracogluahmet 10 September 2013 at 9:36 am
        for i in range(10, 98):
          # the sum and the product of i, (i + 1) and (i + 2)
          a=i+1
          s, p = a+a+a, i * a * (i + 2)
          # list numbers that are factors of both
          d = [f for f in range(2, s//2 + 1) if not (s % f or p % f)]
          # look for six common factors with an odd sum
          if len(d) == 5 and sum(d) & 1==0:
            print(i, a, i + 2)
        
        • saracogluahmet 10 September 2013 at 4:42 pm

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

          for i in range(10, 98):
            # the sum and the product of i, (i + 1) and (i + 2)
            a=i+1
            s, p = a+a+a, i * a * (i + 2)
            # list numbers that are factors of both
            d = [f for f in range(2, s//2 + 1) if not (s % f or p % f)]
            # look for six common factors with an odd sum
          
          
            if (p%s==0):
              d.append(s)
          
            if len(d) == 5 and sum(d) & 1==0:
              print(i, a, i + 2)
          
          • Jim Randell 10 September 2013 at 6:11 pm

            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 in enigma.py does to make its list of divisors. So you could use:

            d = list(f for f in divisors(s) if p % f == 0)
            

            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.

            • Brian Gladman 11 September 2013 at 4:20 pm

              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:

              from itertools import combinations
              from enigma import divisors, Timer
              
              t1 = Timer("Brian's Optimisations")
              t1.start()
              
              # Let the numbers be n - 1, n and n + 1 with the sum and 
              # product 3.n and (n - 1).n.(n + 1). We need exactly six
              # shared divisors. If n was prime 3.n would have at most
              # 4 divisors so it must be composite.  But if n had 3 or
              # more distinct prime factors, the sum and product would
              # then share at least eight divisors.   So n must be the
              # product of exactly two distinct primes.  But if either 
              # prime had a multiplicity more than two, there would be
              # eight or more shared divisors.  So n is the product of
              # two distinct primes with multiplicities of 1 or 2.
              
              for p, q in combinations((2, 3, 5, 7), 2):
                for t in (1, p, q):
                  n = p * q * t
                  if 10 <= n < 100:
                    # the sum and the product of (n - 1), n and (n + 1)
                    s, p = 3 * n, (n - 1) * n * (n + 1)
                    # list numbers that are factors of both
                    d = [f for f in range(1, s + 1) if not (s % f or p % f)]
                    # look for six common factors with an odd sum
                    if len(d) == 6 and sum(d) & 1:
                      print(n - 1, n, n + 1)
              
              t1.stop()
              t2 = Timer("Ahmet's Optimisations")
              
              for i in range(10, 98):
                # the sum and the product of i, (i + 1) and (i + 2)
                a=i+1
                s, p = a+a+a, i * a * (i + 2)
                # list numbers that are factors of both
                d = [f for f in range(2, s//2 + 1) if not (s % f or p % f)]
                # look for six common factors with an odd sum 
               
                if (p%s==0):
                  d.append(s)
               
                if len(d) == 5 and sum(d) & 1==0:
                  print(i, a, i + 2)
              
              t2.stop()
              

              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.

              • saracogluahmet 11 September 2013 at 4:31 pm

                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.

              • Brian Gladman 11 September 2013 at 4:43 pm

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

                from itertools import combinations
                from enigma import divisors, Timer
                
                t1 = Timer("Brian's Optimisations")
                t1.start()
                
                # Let the numbers be n - 1, n and n + 1 with the sum and 
                # product 3.n and (n - 1).n.(n + 1). We need exactly six
                # shared divisors. If n was prime 3.n would have at most
                # 4 divisors so it must be composite.  But if n had 3 or
                # more distinct prime factors, the sum and product would
                # then share at least eight divisors.   So n must be the
                # product of exactly two distinct primes.  But if either 
                # prime had a multiplicity more than two, there would be
                # eight or more shared divisors.  So n is the procuct of
                # two distinct primes with multiplicities of 1 or 2.
                
                for a, b in combinations((2, 3, 5, 7), 2):
                  for t in (1, a, b):
                    n = a * b * t
                    if 10 <= n < 100:
                      # the sum and the product of (n - 1), n and (n + 1)
                      s, p = 3 * n, (n - 1) * n * (n + 1)
                      # list numbers that are factors of both
                      d = [f for f in range(1, s + 1) if not (s % f or p % f)]
                      # look for six common factors with an odd sum
                      if len(d) == 6 and sum(d) & 1:
                        print(n - 1, n, n + 1)
                
                t1.stop()
                t2 = Timer("Ahmet's Optimisations")
                
                for i in range(10, 98):
                  # the sum and the product of i, (i + 1) and (i + 2)
                  a=i+1
                  s, p = a+a+a, i * a * (i + 2)
                  # list numbers that are factors of both
                  d = [f for f in range(2, s//2 + 1) if not (s % f or p % f)]
                  # look for six common factors with an odd sum 
                 
                  if (p%s==0):
                    d.append(s)
                 
                  if len(d) == 5 and sum(d) & 1==0:
                    print(i, a, i + 2)
                
                t2.stop()
                

                >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.

      • saracogluahmet 10 September 2013 at 9:39 am

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

        [deleted]

        • Jim Randell 10 September 2013 at 10:38 am

          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…

          • saracogluahmet 10 September 2013 at 10:48 am

            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

            • Jim Randell 10 September 2013 at 11:27 am

              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 and s 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.

      • saracogluahmet 10 September 2013 at 9:44 am

        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]

    • Jim Randell 10 September 2013 at 2:59 pm

      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.

  3. Richard Spence 7 September 2013 at 9:31 pm

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

    import Data.List
    
    factors :: Int -> [Int]
    factors i = [x | x  Bool
    test x = test1 [x..x+2] where
      test1 a = test2 (sum a) (product a) where
        test2 s p = test3 (intersect (factors s) (factors p)) where
          test3 f = ((length f) == 6) && ((sum f) `mod` 2 == 1)
    
    answer :: [Int]
    answer = [x | x <- [10..97], test x]
    
    main :: IO ()
    main = do
      putStrLn (show answer)
    
    • Jim Randell 8 September 2013 at 11:56 pm

      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 factors made it into the comment correctly. I’m happy to fix-up the comment if you let me have a corrected version.

  4. Paul 13 March 2014 at 3:46 pm

    Here is a Mathematica version

    Do[b=Total[c=Intersection[Divisors[3 (1+i)],Divisors[2 i+3 i^2+i^3]]];
    If[Length[c]==6&&OddQ[b],Print[{i,i+1,i+2}];Break[]],{i,10,99}]//Timing
    {17,18,19},{0., Null}
    

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

    Paul.

    • Jim Randell 14 March 2014 at 4:50 pm

      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:

      % wolfram
      Wolfram Language (Raspberry Pi Pilot Release)
      Copyright 1988-2014 Wolfram Research
      Information & help: wolfram.com/raspi
      
      In[1]:= Timing[ Do[b=Total[c=Intersection[Divisors[3 (1+i)],Divisors[2 i+3 i^2+i^3]]];
      If[Length[c]==6&&OddQ[b],Print[{i,i+1,i+2}]],{i,10,99}] ]
      {17, 18, 19}
      
      Out[1]= {0.15000, Null}
      
      In[2]:= Timing[<< enigma1727.m]                                                                                                     
      {17, 18, 19}
      
      Out[2]= {0.160000, Null}
      

      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!

      % time wolfram -script enigma1727.m
      {17, 18, 19}
      wolfram -script enigma1727.m  11.00s user 0.67s system 97% cpu 11.980 total
      
  5. Paul 15 March 2014 at 12:35 am

    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.

     a=Prime[Range[1000000]];
    

    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.

  6. arthurvause 15 March 2014 at 9:16 am

    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

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: