Problems & Puzzles: Puzzles

Puzzle 376. n=p*2^x

Andrew Rupinski published the following curio:

815955619983050852932210475138609095946139712358642850010872205049*2^95 = 32323332232222233323332233323223222232232232232332222333332332333333332223233333323323232223232

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.

Question. Can 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 88333388383388388833838838833333333838833333888838333383883338383333888883383833

and the following comments:

The problem is much much harder if you require that p be less than
5^x. Basically for any pair of odd and even digits, for each x, there
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 than
10^x, while the earlier part are just put on to make the dividend be a
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:
v_340(3,4) and

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]...


Farideh wrote:

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
distinct digits.
3, 3, 29, 101, 691, 15467, 39023, 71023, 437977, 4344227, 21158903, 109739989,
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
distinct digits.
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). 


Fred wrote:

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 exists,
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 number.

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 method.

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.


Rupinski wrote:

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.







Records   |  Conjectures  |  Problems  |  Puzzles