Enigmatic Code

Programming Enigma Puzzles

Enigma 467: Put out

From New Scientist #1618, 23rd June 1988 [link]

I have before me a machine which operates on integers. Turning the handle once takes the integer at the input, adds 1 to it and then divides the result by 2, providing only that this is possible without fractional result or remainder. The result is displayed at the output and automatically fed back into the input. If turning the handle would otherwise have produced a fractional result or a remainder, the handle of the machine refuses to turn.

I fed an integer N into the input. I turned the handle and found that the ultimate digit of the number output was the same as the ultimate digit of the number input. Intrigued, I turned the handle again and again. All in all I turned the handle 11 times until the ultimate digit of the 11th number output was no longer the same as the ultimate digit of N.

I cleared the machine and fed an integer A into the input. I turned the handle and found that the ultimate digit of the number output was not the same as the ultimate digit of the input number A. Put out, I turned the handle again and again. All in all I turned the handle 11 times. The ultimate digit of the 11th number output was one less than the ultimate digit of the penultimate number output.

What was the smallest possible value of: (a) N?; (b) A?

[enigma467]

One response to “Enigma 467: Put out

  1. Jim Randell 28 September 2018 at 7:58 am

    For this puzzle I took the use of “integer” to mean “positive integer” (i.e. 1, 2, 3, 4, …).

    This Python program runs in 100ms.

    Run: [ @repl.it ]

    from itertools import count
    from enigma import irange, first, printf
    
    # the function
    def f(n):
      (n, r) = divmod(n + 1, 2)
      if r != 0: return
      return n
    
    # the units digit of an integer (in base b)
    units = lambda n, b=10: abs(n) % b
    
    # A(n)
    def A(n):
      # the final digit of the initial number
      d = units(n)
      # apply the function 10 times
      for _ in irange(1, 10):
        n = f(n)
        # the final digit should be the same each time
        if units(n) != d: return
      # and the 11th time the final digit is different
      n = f(n)
      if units(n) == d: return
      return n
    
    # B(n)
    def B(n):
      # apply the function 10 times
      for _ in irange(1, 10):
        # final digit of input number
        d = units(n)
        n = f(n)
        # the final digit should be different from that of the input number
        if n is None or units(n) == d: return
      # and the 11th time the final digit is one less than that of the input number
      d = units(n)
      n = f(n)
      if units(n) + 1 != d: return
      return n
    
    # find the smallest positive integer satisfying fn
    def solve(fn):
      for n in count(1, step=1):
        try:
          r = fn(n)
        except TypeError:
          continue
        if r is not None:
          printf("{fn.__name__}: n={n}")
          break
    
    # solve the puzzle
    solve(A)
    solve(B)
    

    Solution: The smallest positive integers are: (a) 10241; (b) 2049.

    For (a), the repeated applications give:

    0: 10241
    1: 5121
    2: 2561
    3: 1281
    4: 641
    5: 321
    6: 161
    7: 81
    8: 41
    9: 21
    10: 11
    11: 6
    12: STOP

    Each application gives a number ending in the digit 1, until the 11th application gives a number ending in 6, and there can be no further applications (as 6 is even).

    Each of the first 10 numbers is of the form (2^k)×10 + 1.

    For (b), the repeated applications give:

    0: 2049
    1: 1025
    2: 513
    3: 257
    4: 129
    5: 65
    6: 33
    7: 17
    8: 9
    9: 5
    10: 3
    11: 2
    12: STOP

    Each application gives a number whose final digit is different from that of the input number. The 11th application gives the number 2, and there can be no further applications (as 2 is even).

    Each of the first 10 numbers is of the form (2^k) + 1

    If we allow negative integers we find there are solutions such as n = –10239 for part (a), which is generally considered to be “smaller than” 10241 (if we take “smaller” to mean “more negative”, or if we compare magnitudes), similarly for part (b), there is n = –2047. And if we are using “more negative” there are further values that are more negative than these.

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: