Problems & Puzzles:
published the following
The core is
that he got somehow a solution of this type: p*2^x = n, where p is
prime and n is a number composed only by just two kind of digits.
you do it better (a larger nontrivial n)?
Contributions came from Luke Pebody, Farideh Firoozbakht, Fred
Schneider & Andrew Rupinski too.
Luke sent several examples, as:
x 2^214 = 383
and the following comments:
The problem is much much harder if you require that p be less
5^x. Basically for any pair of odd and even digits, for each x,
is precisely one k less than 5^x such that k*2^x is made up entirely
of these two digits. You'll see that above I have broken the product
into two parts. The latter part is the sole multiple of 2^x less
10^x, while the earlier part are just put on to make the dividend be
prime. I will start looking for such p with p<5^x.
[regarding the method]... for every odd digit o, and even digit
e, define a sequence of numbers
v_k(o,e) as follows:
v_k+1(o,e)=(v_k(o,e)+o*5^k)/2 if v_k(o,e) is odd
v_k+1(o,e)=(v_k(o,e)+e*5^k)/2 if v_k(o,e) is even
Then v_k(o,e) is the unique number n less than 5^k such that n*2^k
consists solely of o's and e's.
Rupinski noted that v_95(3,2) is prime.
Larger primes of the form v_k(o,e) include:
These are all with 95<k<=400... [this method]...Wasn't published as
far as I know. There is a fairly standard
brainteaser of "show that there is a multiple of 2^1000 that doesn't
contain a digit 0 in it", and this is an easy extension of this. It
isn't particularly new, I think...
[see for example]...
I think the interesting thing related to this curio is
" p*(2^95) has 95 digits
with two distinct digits " and it seems
that we can't do better.
But we can find many large nontrivial primes p such that for
some x>2, p*2^x has
only two distinct digits.
For example we have the following pattern (dot between
numbers means concatenation).
26.51(m).3.8(n).9013.8(r).9 * 2^3 = 2.12(m).1(n+3).2.1(r+3).9
Example: m=4, n=7, r=16 then
We can find many such patterns.
Also I defined the following two sequences:
1. a(n) is the smallest odd prime p such that p* 2^n has n
digits with at most two
3, 3, 29, 101, 691, 15467, 39023, 71023, 437977, 4344227,
344590189, 2956838897, ...
Andrew Rupinski's curio shows that a(95) exists.
2. b(n) is the smallest odd number m such that m* 2^n
has n digits with at most two
1, 3, 25, 101, 363, 3125, 15625, 71023, 390625,
1183713, 5474669, 27151397,
135646011, 1220703125, ...
It's obvious that for each n, b(n) exists and
(5^(n-1))/2 < b(n) <= 5^(n-1).
I implemented the following algorithm in PARI:
For n>1, the tens (t) and unit (u) digits of x*2^n are the same as
(x+50)*2^n because (x+50)*2^n = x*2^n+100*2^(n-1).
In general we can show that the mth digit from the right of x*2^n
and (x+2*5^m)*x^n are the same (assuming x*2^n has m digits).
So for each n, one only needs to iterate through odd integers x
between 1 and 49. If x*2^n has even t and u, skip it.
If not, find an x+a*50 such that, the hundredths digit h is equal
to t or u. One only needs to check from a=0 to 4. If no number
skip to the next x.
If we do find an "a" set x=x+a*50 and look for x+a*250 such that the
thousandths digit matches h, t or u.
Clearly, we can attempt to construct a number of arbitrary length
with only two different digits.
So at most we have 25*n*5 checks for each 2^n, making this a linear
a linear algorithm. One can pick and choose when to check "x" for
primality. For performance reasons (and given the probabilities
involved), I only checked where m>n-10.
I was able to find numerous solutions over n=95 and they proved to
be fairly common.
The largest number I found was a 1396-digit prime number [omitted]
It wouldn't be difficult running the same script to find a larger
Fun fact: For every number which is composed of 1 and 6's, 2 times
that number is composed of 3 and 2's only. The puzzle example is
such a case.
The largest example I found of this was this 1000-digit prime
[omitted]... There's no known composite which is a pseudoprime both
ways. [omitted] when when multiplied by 2^1432 or 2^1433
yields two different two-digit only number (of 1431 digits)...
I forgot one thing. I should add that I only looked for numbers
up to n digits (which factored to 2^n * some prime).
One could easily extend to larger numbers without this constructive
Say, I had a number of 107 digits = x * 2^100, whose first 100
digits were one of two digits, say 3 and 2.
If the 105th digit was 1,
add (2-1)*10^(105-100)*5^100 to my x to change the digit to 2.
add (3-1)*10^(105-100)*5^100 to my x to change the digit to 3.
One could use this approach as well perhaps to find large solutions
past n digits.
As you surely are aware [Nop!...], puzzle 376 was already solved
in puzzle 218,
where J.K. Andersen
found the probable prime R(1,6,33587) which has over 24K digits.
Actually the method discussed for finding such primes vastly
generalizes in the following way:
Given a base B and any number n dividing B, if we choose digits
(a_1,...,a_n) in base B such that a_i = i mod n, there is a
unique number N composed of D digits in base B, all taken from
(a_1,...,a_n), such that n^D divides N.
The numbers B(O,E,D) examined in puzzle 218 correspond to the
case B = 10, n = 2. I have looked at other bases and sets
(a_1,...,a_n) briefely, but have not searched for large primes
arising in this more general way.