# 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)
```

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