Smallest multipliers to make a number palindromic
What is the smallest number that multiplied with 81 gives a palindrome ?
Answer : This number is 12345679
And the palindrome is a series of nine nines ! = 999999999
Note that the reciprocal of 81 is 0,0123456790123456790123...
See Sloane's A050782
Careful observation reveals that powers of 3 and/or multiples of 81
require the largest multipliers. Hence the next puzzle !
Find the smallest multipliers for the following numbers:
162, 243, 324, 405, 486, 567, 648 and 729.
On [ April 27, 1997 ] I submitted this topic to sci.math but
rediscovered it only very recently [ January 2000 ] in my archive...
I got some very interesting (theoretical) replies that I like to share.
The general question was
Can every integer X be multiplied with another
integer Y to produce a palindrome P ?
Ilias Kastanas wrote after 81 * 12345679 = 999999999
That is, 10^9 = k*3^4 + 1.
It follows easily that 3^5 divides 10^27 – 1, 3^6 divides 10^81 – 1, etc.
Extra Source Number Theory List - Message from 17 Sep 1991
Angel Garcia recalls that 1 ÷ 81 = 0.012345679 012345...
to which Glaisher adapted a famous theorem and Sierpinski derived:
1/99^2 = 0.00 01 02 03 ... 97 99 00 01 ...
and similarly (Lahoz)
1/999^2 = 0.000 001 002 003 .......
Angel Garcia thinks that it is a matter of finding a LARGE enough
integer to palindromize 81.
David G Radcliffe generalized that every positive integer is a factor
of a palindrome, unless it is a multiple of 10.
If X is not divisible by 2 or 5, then 10^p = 1 mod X, where p = phi(X)
is the number of integers between 1 and X which have no common factor
with X. In this case, put Y = (10^p – 1) / X. Then X * Y = 10^p – 1
is a palindrome.
If X is even, then write X = 2^n * W, where W is odd. Construct a
palindrome Q = 10^n * R + 2^n, where R is the digit reversal of 2^n.
Let p = phi(W). Then 10^(2pn) = 1 mod W, so
S := 1 + 10^(2pn) + 10^(4pn) + ... + 10^(2(W–1)pn) = 0 mod W.
Let P := Q*S. Then P is a palindrome which is divisible by X.
A similar construction can be used when X is a multiple of 5.
Example: if X = 81, then p = 54, and Y = (10^54 – 1)/81.
81 * 12345679012345679012345679012345679012345679012345679 =
999999999999999999999999999999999999999999999999999999
Example: If X = 112, then X = 2^4 * 7, Q = 610016, and p = 6.
Then P = 610016 0..0 610016 0..0 610016 0..0 610016 0..0 610016 0..0 610016
The 610016's are placed to ensure that P is divisible by 7, while 610016
itself is divisible by 16. Therefore P is a multiple of 112. |
Kevin Brown adds the following to Radcliffe's above answer:
We might also note that phi(3^k) is always even, so we
have phi(3^k) = 2m and (10^2m – 1) = (10^m – 1)(10^m + 1).
Clearly the second term in the factorization is not divisible
by 3, so 3^k must divide 10^m – 1. Similarly, m is always
divisible by 3, and we can show that 10^(m/3) – 1 is divisible
by 3^k, as can be seen from the fact that
$$10^{3^k}-1 = (10-1)*\prod_{j=0}^{k-1}\ [\ x^{2*3^j}+x^{3^j}+1\ ]$$
The term (10 – 1) is divisible by 2 powers of 3, and each term
inside the product is divisible by exactly 1 power of 3.
This shows that 3^k not only divides 10^phi(3^k) – 1 (by
Euler's theorem), it also divides 10^(phi(3^k)/6) – 1.
For example, we have
81 * 12345679 = 10^9 – 1 = 999999999
243 * 4115226337448559670781893 = 10^27 – 1
and so on.
David M. Einstein remarks after reading
243 divides 10^162–1
739 divides 10^486–1
that these are almost certainly not the smallest solutions, but they show
that 3^n can always be made palindromic. In general if k is not divisible
by 2 or 5 then k divides 10^n–1 where n is the number of positive integers less
than k that do not share a common factor with k (look at an elementary number
theory book for a description of the totient function).
and when Hauke Reddmann asked if 12345679 is the lowest factor
which turns 81 palindromic (81 * 12345679 = 999999999), David replied :
12345679 is the smallest multiplier that makes 81 palindromic. This is
an interesting side effect of the fact that 10^n = n*9 + 1 mod 81.
An n+1 digit palindrome divisible by 81 can be written as
a_0 * (10^n+1) + a_1(10^(n–1)+10) + ... = 0 mod 81
with 0 ⩽ a_i ⩽ 9 and a_0 ≠ 0
this turns out to be
(9n+2)(a_0+...+a_{(n–1)/2}) = 0 mod 81 if n is odd
or
((9n+2)/2)(2 a_0 + ... + 2 a_{(n–2)/2} + a_{n/2}) = 0 mod 81
Since 9n+2 and ((9n+2)/2) are units mod 81, the sums must = 0 mod 81. It is
easy to see that the first time that this happens is at 999999999.
Kurt Foster distinguishes four cases in the Palindrome proof :
Case (1) X is itself a palindrome -- in this case, P = X works.
Case (2) X isn't a palindrome, and is relatively prime to 10. In this
case, there is a least positive integer N (a divisor of phi(X)) such that
X divides 10^N – 1; P = 10^N – 1 works, though it may not be the smallest
palindrome divisible by X.
Case (3) X = x * 2^m, where gcd(x, 10) = 1. Here, we first find a
palindrome p divisible by 2^m. If 2^m isn't a palindrome, then one such p
may be constructed as follows: pad 2^m out to m places by padding "on the
left" with zeros, then prepend this with the digits of 2^m IN REVERSE
ORDER. Anyhow, if p has b digits, then Q = (10^(b*N) – 1)/(10^b – 1) will
be divisible by x for a suitable N = N(x, b); and P = p * Q (the b-digit
palindrome p repeated N times) will be a palindrome divisible by X. This
may not be the smallest P that works, though.
Case (4) X = x * 5^m, x as in Case (2). Similar to Case (3). |
Many other people like Keith Lynch, Lynn Johannesen or Keith Ramsay
emailed that 999999999 is definitely the smallest palindrome divisible by 81
and with quotient 12345679.
I quote also Fred W. Helenius : "... It is indeed remarkable that one must go so far."
Then came Barry Wolk with yet another line of approach.
We were asked for a palindrome divisible by 81, and for one divisible by 3^5,
one by 3^6, etc. David Radcliffe gave a mathematical answer, based on
the result that, whenever n is not divisible by 2 or 5, 10^phi(n) – 1 is divisible by n.
Here is a more elementary answer :
9 is divisible by 9, and 111 is divisible by 3, so their product
is divisible by 9*3 = 27. This product is the palindrome 999.
999 is divisible by 27, and 1001001 is divisible by 3, so their product
is divisible by 27*3 = 81. This product is the palindrome 999999999.
999999999 is divisible by 81, and 1000000001000000001 is divisible by 3,
so their product is divisible by 81*3 = 3^5. This product is the palindrome 10^27 – 1.
This pattern continues, and it gives a proof by induction that 10^n – 1
is divisible by 9n whenever n is a power of 3.
If you want palindromes that aren't of the form 10^n – 1, you can use
a similar procedure to show that, for example:
90909 is divisible by 27
99909990999 is divisible by 81
99999999909999999990999999999 is divisible by 243
etc.
It is easy to show that 999999999 is the smallest palindrome divisible by 81.
Keith Lynch already posted that result, by a computer search. Try proving this
without an exhaustive computer search (although hand calculators are allowed).
Is there a palindrome smaller than 10^27 – 1 that is divisible by 243 ?
Barry finally asks as an extra puzzle.
Fred W. Helenius solved Barry Wolk's puzzle !
Yes, 243 divides 29799999792.
And, before you ask (these are all minimal):
729 divides 39789998793,
2187 divides 39989598993, and
6561 divides 68899199886.
The last one is the amazing one: not only is it divisible by 3^8;
it is divisible by 3^12 = 531441.
For a more challenging puzzle, find the smallest palindrome divisible by 8181.
Solution found by Patrick De Geest on [ March 10, 2001 ]
Lynn Johannesen investigated the case 2*81 or 162.
Now try 162 (=2*81). Exhaustive search demonstrates that there's
no answer where the product is less than 2^32. On the other hand, the number
composed of 81 2's works, by an argument similar to Keith Lynch's
for 999999999/81. Is there anything smaller ?
Fred W. Helenius replied positively to Lynn's question.
162 * 172839506 = 27999999972 (=28*999999999).
From here on the discussion extinguished...
Allow me to recapitulate the results in the following table.
Integer X | Smallest Multiplier | Palindrome |
81 or 3^{4} | 12345679 | 999999999 |
162 | 172839506 | 27999999972 |
243 or 3^{5} | 122633744 | 29799999792 |
324 | 86419753 | 27999999972 |
405 | 135802469 | 54999999945 |
486 | 61316872 | 29799999792 |
567 | 49382716 | 27999999972 |
648 | 45987654 | 29799999792 |
729 or 3^{6} | 54581617 | 39789998793 |
891 | 61728395 | 54999999945 |
972 | 30658436 | 29799999792 |
1053 | 27445394 | 28899999882 |
1134 | 24691358 | 27999999972 |
... | ... | ... |
2187 or 3^{7} | 18285139 | 39989598993 |
6561 or 3^{8} | 10501326 | 68899199886 |
8181 | 1173450678278939 | 9599999998999999959 |
19683 or 3^{9} | 3500442 | 68899199886 |
59049 or 3^{10} | 1166814 | 68899199886 |
818181 | 111222333444555666777889 | 90999999999999999999999999909 |
It looks like the concatenations of 81
are the most difficult cases to solve...
Strings of 81 | Multiplier Infinite Pattern by Patrick De Geest | Strings of 9 |
(81)_{1} or 81 | 1(2)_{1}3(4)_{1}5(6)_{1}7(8)_{0}9 0(1)_{1}2(3)_{1}4(5)_{1}6(7)_{1}9 12345679012345679 | 18 |
(81)_{2} or 8181 | 1(2)_{3}3(4)_{3}5(6)_{3}7(8)_{2}9 0(1)_{3}2(3)_{3}4(5)_{3}6(7)_{3}9 122234445666788901112333455567779 | 36 |
(81)_{3} or 818181 | 1(2)_{5}3(4)_{5}5(6)_{5}7(8)_{4}9 0(1)_{5}2(3)_{5}4(5)_{5}6(7)_{5}9 1222223444445666667888890111112333334555556777779 | 54 |
(81)_{k} | 1(2)_{2k–1}3(4)_{2k–1}5(6)_{2k–1}7(8)_{2k–2}9 0(1)_{2k–1}2(3)_{2k–1}4(5)_{2k–1}6(7)_{2k–1}9 | k * 18 |
Strings of 81 | Smallest Possible Multiplier | Palindrome |
81 | 12345679 | 999999999 |
8181 | 1173450678278939 - [ March 10, 2001 ] | 9599999998999999959 |
818181 | 111222333444555666777889
by Daniel Fischer [ June 19, 2008 ] | 90999999999999999999999999909 |
81818181 | 11117333444506667778277788893889
by Daniel Fischer [ June 20, 2008 ] | 909599999999999999989999999999999995909 |
It looks like the sequences 89...91 generates
some large minimal multipliers, too (by Chen Xinyao with 891 & 8991,
(Daniel Fischer with 89991, 899991 and larger) :
Sequences of 89...91 | Smallest Possible Multiplier
Palindrome |
891 | 61728395
54999999945 |
8991 | 111222333444555666777889
999999999999999999999999999 |
89991 | 11678834550110566611
1050989999998999999890501 |
899991 | 1111122222333334444455555666667777788889
999999999999999999999999999999999999999999999 |
8999991 | 1167723278834389945501056611
10509498999999999999999999989490501 |
89999991 | 11111112222222333333344444445555555666666677777778888889
999999999999999999999999999999999999999999999999999999999999999
(22 minutes) |
Continued at WONplate 96 and WONplate 223