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:

14580760813448290724195882524536958581033617611478790815209371566091196151166833
6918514186483194731836978245852413088760934190534265346137795237326531057
x 2^214 = 383 88333388383388388833838838833333333838833333888838333383883338383333888883383833
383333833383833888383338388833883388383883383883883883338333338883833388838338383333883833338
88883833338883388388888888888833383333888

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_0(o,e)=0

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_98(3,4)
v_98(7,8)
v_119(5,6)
v_122(9,4)
v_139(7,2)
v_139(5,8)
v_156(9,4)
v_167(7,6)
v_167(9,8)
v_189(1,2)
v_205(3,2)
v_227(7,4)
v_238(5,8)
v_301(3,4)
v_331(5,6)
v_340(3,4) and
v_398(1,4)

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]... http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/challenges/December1999.html

***

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

p=26.51(4).3.8(7).9013.8(16).9=265151515138888888901388888888888888889

and

p*2^3=2.12(4).1(7+3).2.1(16+3).9=2121212121111111111211111111111111111112

 

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.

***

 

 

 
 

 

 

---