Bidigit Powers
Bob Harris
A while back, I posted to rec.puzzles:
> Ob puzzle: In base 10, what powers can be made that only use *two* different
> digits? Discounting powers of 10, and any powers that are less than 100, as
> trivial. 7776 is one answer, 121, 484, 676, and 1331 are others.
>
> Second ob puzzle For any two digits a,b, is there a base ten power than uses
> only those two digits? From the examples above (and the trivial answers), the
> table looks like this (monospace font please):
And several contributors have helped produce this table (I've modified the
entries for <0,4>, <0,8>, and <0,9>):
>
> 1 2 3 4 5 6 7 8 9
> --+------+------+------+------+------+------+------+-------+---------+
> 0 | 10^x no ? 20^x no no ? 20^x 30^x |
> 1 | - 11^2 11^3 12^2(a) ? 2^4(b) ? 3^4(c) ? |
> 2 | - - 2^5 ? 5^2(d) no 3^3 ? 173^2 |
> 3 | - - - 7^3 ? 6^2 ? ? ? |
> 4 | - - - - ? 2^6 88^2 22^2 7^2(e)|
> 5 | - - - - - ? ? ? ? |
> 6 | - - - - - - 6^5(f) ? 264^2(g)|
> 7 | - - - - - - - ? ? |
> 8 | - - - - - - - - ? |
> --+------+------+------+------+------+------+------+-------+---------+
>
> (a) also 21^2 and 38^2
> (b) also 81619^2
> (c) also 109^2
> (d) also 15^2 and 235^2
> (e) also 212^2
> (f) also 26^2
> (g) also 3114^2
Hugo van der Sanden <h...@crypt0.demon.co.uk> has determined that there are no
more bidigit powers less than 10^16 (not counting powers of 10, 20, or 30).
The largest he finds is 81619^2 = 6661661161.
I've been trying to prove certain entries impossible. I have had no luck so
far.
One approach was to take look at all powers mod 10^k for increasing values
of k, and see what pairs can be eliminated. The answer, so far, is 'not
many'. Here's what the table looks like for powers mod 100,000. A hyphen
means there is no power whose last five digits are just those two numbers
(or one number). An x means there is some power whose last five digits are
just those two numbers. The only things that can be eliminated by this
method (assuming I wrote the program correctly) are <0,2> and <2,6>
0 1 2 3 4 5 6 7 8 9
0 x x - x x x x x x x
1 x x x x x x x x x
2 - x x x - x x x
3 x x x x x x x
4 - x x x x x
5 - x x x x
6 - x x x
7 x x x
8 x x
9 x
Presumably if we took this far enough, increasing k ever larger, we could
eventually eliminate every pair (since in this table, I consider a number
like 26^2 = 676 to be 00676).
But I spent some time exploring <1,5> by hand. As a result of those
efforts, I'm beginning to get the idea that for nearly every pair and for
any k, there is *always* some power r^n such that the last k digits are only
that pair. But I can't prove it. Anyone have any idea how to go about
this?
Bob
Geoff Bailey
In article <B5DFA87B.B78F%nit...@mindspring.com>,
Bob Harris <nit...@mindspring.com> wrote:
> Presumably if we took this far enough, increasing k ever larger, we could
> eventually eliminate every pair (since in this table, I consider a number
> like 26^2 = 676 to be 00676).
The Fermat-Euler theorem is going to make this difficult. It states
that a^phi(n) = 1 mod n when gcd(a,n) = 1. To take <0,3> as an example,
since gcd(3,10^k) = 1 then we have 3^phi(10^k) = 1 mod 10^k for all k,
and hence 3^(phi(10^k) + 1) = 3 mod 10^k for all k. Hence this approach
on its own will never suffice to eliminate <0,3>. (And similarly for
<0,7>.)
[ phi(n) = #{x : 1 <= x <= n | gcd(x,n) = 1}. So, since phi(100) = 40,
this tells us that 3^40 = 1 mod 100, and hence 3^41 = 3 mod 100. ]
> But I spent some time exploring <1,5> by hand. As a result of those
> efforts, I'm beginning to get the idea that for nearly every pair and for
> any k, there is *always* some power r^n such that the last k digits are only
> that pair. But I can't prove it. Anyone have any idea how to go about
> this?
Looking at <1,5>, we see that a number consisting solely of 1s and 5s
will be coprime to 10 iff it ends in a 1. Supposing you are looking at
the last k digits, and let n = phi(10^k) + 1. Then choose r to be some
k-digit number whose digits are solely 1s or 5s and which ends in 1.
Then we have r^(n-1) = 1 mod 10^k, and hence r^n = r mod 10^k.
So for the enumeration approach to work, we must have that each digit
is not coprime to 10, such as <5,8>. But there are still an infinite
number of primes to consider in the powers, so I can't see how to make
this work.
Cheers,
Geoff.
-----------------------------------------------------------------------------
Geoff Bailey (Fred the Wonder Worm) | Programmer by trade --
ft...@cs.usyd.edu.au | Gameplayer by vocation.
-----------------------------------------------------------------------------
Adam Stephanides
> But I spent some time exploring <1,5> by hand. As a result of those
> efforts, I'm beginning to get the idea that for nearly every pair and for
> any k, there is *always* some power r^n such that the last k digits are only
> that pair. But I can't prove it. Anyone have any idea how to go about
> this?
If one of the digits is 1, 3, 7 or 9 then it's true even if your require
n to be 3. Proof by induction: it's true for k = 1. Suppose it's true
for k = i >= 1. Choose an appropriate r, which can be assumed to have i
digits. For each digit s, (s*10^i + r)^3 is congruent to
3s*(r^2)*(10^i) + r^3 mod 10^(i+1). Since r^2 ends in 1 or 9, we can
pick s to make the i+1-th-from-the-right digit whatever we want.
--Adam