Enigmatic Code

Programming Enigma Puzzles

Enigma 1239: The next number…

From New Scientist #2395, 17th May 2003 [link]

Joe took a sheet of lined paper and asked me to write a whole number on the first line. This I did, writing a number that was less than a million and which consisted of the same digit repeated several times. After some elaborate calculations Joe wrote a number of the second line. After more calculations he wrote a number on the third line, and he continued like this until he had written a huge number on the eighth line. I asked him how he calculated each number. He explained, “If the number N is on one line then I work out the remainders when N is divided by 5 or 6. In some cases the first remainder was larger than the second and in those cases I wrote the square of N+1 on the next line. In the other cases the first remainder was smaller than the second and I wrote the cube of N+2 on the next line.”

What number did I write on the first line?

[enigma1239]

Advertisements

2 responses to “Enigma 1239: The next number…

  1. Jim Randell 21 April 2015 at 8:14 am

    This Python program runs in 32ms.

    from enigma import irange, Accumulator, printf
    
    # the transformation procedure
    def T(N, n):
      # count the residues
      r5 = r6 = 0
      for i in irange(1, n):
        r = (N % 5) - (N % 6)
        if r > 0:
          N = (N + 1) ** 2
          r5 += 1
        elif r < 0:
          N = (N + 2) ** 3
          r6 += 1
        else:
          return (0, 0, 0)
      return (N, r5, r6)
    
    # look for the largest result
    m = Accumulator(fn=max)
    
    # numbers consisting of 3 to 6 repeated digits
    for r in irange(3, 6):
      for d in irange(1, 9):
        N = int(str(d) * r)
        # apply the transformation 7 times (to get the 8th line)
        (s, r5, r6) = T(N, 7)
        if s and r5 > 1 and r6 > 1:
          printf("[{N} => {n} digits ({r5}, {r6})]", n=len(str(s)))
          m.accumulate_data(s, N)
    
    printf("max @ n={m.data}")
    

    Solution: The number on the first line is 5555.

    I found this to be a poorly worded puzzle, as I think the challenge should be to solve a well specified problem, rather than try to work out what the problem actually is. At first I thought there wasn’t enough information to arrive a unique answer, but if we take the following clarifications then we can arrive at a unique answer. First we take the statement “I work out the remainders when N is divided by 5 or 6” to mean “I work out the remainder when N is divided by 5 and the remainder when N is divided by 6″ (we call these two values the residues). We note that “in some cases the first remainder was larger than the second… in the other cases the first remainder was smaller than the second”. So what happens if the two residues are equal? We are not given a way to calculate the number that would be written down in this situation, so we can only assume that in the particular instance we are dealing with this never happens.

    This gives us a way to attack the problem. Of all the possible numbers composed of “several” (by which I’m assuming “more than two”) repeated digits, less than a million (so no more than 6 repeated digits), we are only interested in the ones where when the procedure followed is applied seven times (to give a total of eight numbers on the paper), none of the numbers have the same residue modulo 5 as modulo 6.

    Assuming that “the square of N+1” is interpreted as (N+1)², and “the cube of N+2” as (N+2)³, we find that there is in fact only one possible initial number for which this is the case. (The program is written to select the largest final number from all the possibilities found, as we are just told that the final number is “huge”. Although it turns out there is only a single candidate number anyway). I also assumed that “in some cases the first remainder was larger than the second” implied that there must be multiple occurrences when this was the case, and likewise “in the other cases” implies that there must also be multiple occurrences when the first remainder is smaller than the second, so my program takes this into account, and the single possibility does indeed satisfy this condition.

    However the “huge” number we end up with is 1618 digits, so even if Joe managed to squeeze each digit into a millimetre wide space the sheet of paper would have to be over 5 feet wide, which seems a little unlikely. A standard sheet of A4 is 210mm, so I think Joe would struggle to write out the numbers after the 4th application of the procedure. The digit lengths of the numbers being: 4, 12, 23, 68, 135, 270, 809, 1618.

    • geoffrounce 21 April 2015 at 8:30 pm

      Yes, same answer, testing all the possible 3,4,5, and 6 digit numbers less than 1 million.

      def get_num(num):
          for n in range(1,8):
              r1,r2 = num % 5, num % 6
              if r1 > r2: num = (num + 1) ** 2
              if r1 < r2: num = (num + 2) ** 3
          return(len(str(num)),num)
      
      list1 = []
      
      # 3 digit numbers
      for n1 in (111,222,333,444,555,666,777,888,999):
          num = n1
          res1,res2 = get_num(num)
          if not res1 == res2 == 0:
              list1.append((n1,res1,res2))
      
      # 4 digit numbers
      for n2 in (1111,2222,3333,4444,5555,6666,7777,8888,9999):
          num = n2
          res1,res2 = get_num(num)
          if not res1 == res2 == 0:
              list1.append((n2,res1,res2))
      
      # 5 digit numbers
      for n3 in (11111,22222,33333,44444,55555,66666,77777,88888,99999):
          num = n3
          res1,res2 = get_num(num)
          if not res1 == res2 == 0:
              list1.append((n3,res1,res2))
      
      # 6 digit numbers
      for n4 in (111111,222222,333333,444444,555555,666666,777777,888888,999999):
          num = n4
          res1,res2 = get_num(num)
          if not res1 == res2 == 0:
              list1.append((n4,res1,res2))
      
      # find number and its maximum number of digits
      m = max (list1, key=lambda x: x[1])
      print('Number = {}, No digits = {} '.format(m[0],m[1]))
      
      # Ans: Number = 5555, No digits = 1618
      # NB. print(m[2]) to get the 1618 digit length number!
      
      
      

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: