A bevy of ones

Take any positive integer d that is not a multiple of 2 or 5. Then there is some integer k such that d * k has only 1's in its decimal representation. For example, take d = 13. We have

13 * 8457 = 111111.

Or if we take d = 27,

27 * 4115226337448559670781893 = 111111111111111111111111111.

Let's change our perspective and start with the string of 1's. If d is not a multiple of 2 or 5, then there is some number made up of only 1's that is divisible by d. And in fact, the number of 1's is no more than d.

This theorem generalizes to any integer base b > 1. If d is relatively prime to b, then there is a base b number with d or fewer digits" which is divisible by d [1].

The following Python code allows us to find the number k such that d * k has only 1's in its base b representation, provided k is relatively prime to b. It returns the number of 1's we need to string together to find a multiple of k. If k shares a factor with b, the code returns 0 because no string of 1's will ever be divisible by k.

 from math import gcd def all_ones(n, b = 10): return sum(b**i for i in range(n)) def find_multiple(k, b = 10): if gcd(k, b) > 1: return 0 for n in range(1, k+1): if all_ones(n, b) % k == 0: return n

The two Python functions above default to base 10 if a base isn't provided.

We could find a multiple of 5 whose hexadecimal representation is all 1's by calling

 print(find_multiple(5, 16))

and this tells us that 11111_sixteen is a multiple of 5, and in fact

5 * 369d_sixteen = 11111_sixteen.

[1] Elmer K. Hayashi. Factoring Integers Whose Digits Are all Ones. Mathematics Magazine, Vol. 49, No. 1 (Jan., 1976), pp. 19-22

The post A bevy of ones first appeared on John D. Cook.