Enigmatic Code

Programming Enigma Puzzles

Enigma 1091: One’s best years

From New Scientist #2247, 15th July 2000 [link]

Mr Meaner has now retired from teaching. As a tough arithmetic exercise each year he used to ask his class to take the number of the year and find some multiple of it which consists simply of a string of ones followed by a string of zeros. For example in 1995 one girl in the class found that the 19-digit number 1111111111111111110 was a multiple of 1995!

Mr Meaner had been asking this question every year since he started training as a teacher. On the first occasion it was a reasonably straightforward exercise and most of the class found a multiple using as few digits as possible.

It is lucky that he did not ask the question a year earlier, for that year would have required over two hundred times as many digits as that first occasion did.

In what year did Mr Meaner first ask the question?

[enigma1091]

5 responses to “Enigma 1091: One’s best years

  1. Jim Randell 23 October 2017 at 9:51 am

    Any repunit ends in 1, so it can’t have divisors of 2 or 5, so any factors of 2 or 5 in the year must be covered by the 0’s at the end of the number, and we need as many 0’s as the largest number of factors of 2 or 5 in the original year. The remaining factors need to be covered by the repunit.

    The [[ drop_factors() ]] function was recently added to the enigma.py library.

    This Python code runs in 80ms.

    Run: [ @repl.it ]

    from enigma import irange, drop_factors, printf
    
    # find the smallest multiple of <n> consisting of a string of 1's
    # followed by a string of 0's
    # return (<number of 1's>, <number of 0's>)
    def solve(n):
      # first remove factors of 2 and 5
      (f2, n) = drop_factors(n, 2)
      (f5, n) = drop_factors(n, 5)
      # find the smallest repunit r with k digits that divides what's left
      (k, r) = (1, 1)
      while r % n != 0:
        k += 1
        r *= 10
        r += 1
      return (k, max(f2, f5))
    
    # check the example given
    assert solve(1995) == (18, 1)
      
    # work backwards from 1995
    p = None
    for y in irange(1995, 1, step=-1):
      (d1, d0) = solve(y)
      n = d1 + d0
      printf("{y} -> {n} ({d1}, {d0})")
      # look for previous year with >200x the number of digits
      if p and n > 200 * p:
        printf("year={y1} digits={p} [year={y} digits={n}]", y1=y + 1)
        break
      p = n
    

    Solution: Mr Meaner first asked the question in 1950.

    1950 divides an 8-digit number (11111100) and 1949 divides a 1948-digit number (1…1), but this is not the largest number required in the period 1949 – 1995. 1979 requires a 1978 digit number to be constructed (1…1), and 1977 requires a 1974-digit number (1…1).

    • Jim Randell 24 October 2017 at 12:16 pm

      If Mr Meaner was still teaching and had set the puzzle this year (2017), the pupils would find that the shortest number possible is a string of 2016 1’s.

      We almost get a second solution to the problem with the years 1999 and 2000. 1999 requires a string of 999 1’s, and 2000 will divide 10000 (5 digits), the ratio 999/5 being just less than 200.

      As it is the next solution occurs with the years 2099 and 2100. 2099 requires a string of 2098 1’s, and 2100 will divide 11111100 (8 digits). 2098/8 is more than 200.

  2. Hugh Casement 24 October 2017 at 4:59 pm

    A difficult exercise without a computer.  I suppose factorizing would help:
    111111 = 3 × 7 × 11 × 13 × 37, so if you tack on a couple of zeros you could expect
    1924 = 2² × 13 × 37 and 1925 = 5² × 7 × 11 and 1950 = 2 × 3 × 5² × 13 to be factors.

    It’s a lot more work to find 1111111 = 239 × 4649 and 1912 = 2³ × 239.
    Mean indeed to ask schoolchildren to do it for most other years in the range.

    The repunits with 19 and 23 and 317 digits are prime.  I didn’t try any more.

  3. geoffrounce 24 October 2017 at 5:25 pm

    The term ‘repunit number’ was first coined by Alfred H Beiler in 1964 in his book – “Recreations in The Theory of Numbers:

    http://primes.utm.edu/glossary/xpage/Repunit.html

    I found an easy way of constructing long repunit numbers in Python, as shown in the attached snippet of code. Having found a repunit of any desired length, it is easy to check factors using the modulus function. The repunit could also be made of any other single digit.

    # An easy method of constructing long repunits in Python
    
    s = ""
    
    # Build a long repunit string - all 'ones'
    
    for i in range(1, 2017):      # ie 2016 long repunit string of '1' s
        s += str(1)
    
    print(); print('Divisors: 2016 long repunit of ones')
    
    # find divisor years from 1900 to 2099
    for y in range(1900, 2100):      # range of years as divisors
        if int(s) % y == 0:
            print(y, end = ' ')
    
    print()
    
    #-------------------------------------
    # All years between 1900 and 2099 as divisors of long repunits of '1' s
    # Repunits/Divisors - Other Examples
    
    # 2016 long digit repunit ('1's)
    # Divisors: 1911 1919 1
    # 921 1923 1933 1967 1989 2017 2019 2037 
    
    # 1948 long digit repunit ('1's)
    # Divisors: 1949 only
    
    # 1978 long digit repunit ('1's)
    # Divisors: 1903 1979 
    
    # 1974 long digit repunit ('1's)
    # Divisors: 1911 1933 1977 1981
    
    
    • Jim Randell 24 October 2017 at 5:32 pm

      @geoff: A quick way to construct a string of repeated characters in Python is to use the [[ * ]] operator on strings. So you can construct a string with 2016 1’s in it using:

      s = "1" * 2016
      

      There is also the [[ repdigit() ]] function in the enigma.py library that can produce repunits (or numbers composed of other repeated digits) without constructing them using strings. It is implemented like this:

      def repdigit(n, d=1, base=10):
        return d * (base ** n - 1) // (base - 1)
      

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: