Problems & Puzzles: Puzzles

Puzzle 892. Primes as a concatenation of a series of powers of a prime On August 17, 2017, Vic Bold sent the following nice and easy puzzle. Given a prime number p, concatenate orderly the powers p^0, p^1, p^2,... and find prime solutions as in the following examples, concatenating orderly three powers: For p=11, 1&11&121 => 111121, prime number For p=29, 1&29&841 => 129841, prime number Vic asked for the first p solution concatenating orderly four powers. I found the p=337 is the asked solution: 1&337&113569&38272753 => 133711356938272753. Larger quantity of concatenated powers are easily produced with the help of a little code. Naturally I wanted to know if prime solutions are possible for any quantity of powers. I was very surprised that NO prime solutions are possible for 6, 12, 18, ... orderly concatenated powers. Here are my results (K= quantity of orderly concatenated prime P powers; Pmin= Minimal prime P to give a concatenated prime) K, Pmin 2 - 3 (1&3) 3 - 3 (1&3&9) 4 - 337 ( 1&337&113569&38272753) 5 - 23 7 - 373 8 - 37 9 - 839 10 - 421 11 - 7 13 - 1447 14 - 2113 15 - 29 16 - 43 17 - 17 19 - 1789 20 - 523 21 - 84737 22 - 7669 23 - 397 25 - 3851 26 - 3583 Q. Can you explain why NO prime solutions are possible for 6m quantity of orderly concatenated powers?

---

Contributions came from Jan van Delden, Emmanuel Vantieghem & T. D. Noe.

Jan wrote (Set 2, 2017):

The sum of digits of any number n mod 3 is equal to n mod 3.

 

Define n[i]=n^i and our concatenated number m[k]=n[0].n[1]. ..n[k-1] (k terms).

 

If n=0 mod 3 every n[i]=0 mod 3 (i>=1)  and n[0]=1 mod 3 so the sum of digits is 1 mod 3 and m[k]=1 mod 3 for any k (k>=1).

 

If n=1 mod 3 we have n[i]=n^i=1 mod 3. So concatenating k terms where k=0 mod 3 will give a number m[k] which is 0 mod 3. [The sum of digits of m[k] will be equal to the sum of digits of the n[i]  which equals the sum of n[i] mod 3 = (k*1) mod 3=0 mod 3].

 

If n=2 mod 3 we have n[i]=n^i=(-1)^i mod 3. If i is even this is equal to 1 mod 3 otherwise -1 mod 3. So concatenating k terms where k=0 mod 2 will give a number m[k] which is 0 mod 3. [The sum of digits of m[k] is equal to the sum of digits of the n[i] which equals (k/2*(2+1) mod 3 = 0 mod 3].

 

So:

 

n=0 mod 3          3 is not a divisor of m[k]

n=1 mod 3          3 is a divisor of m[k] iff 3 is a divisor of k

n=2 mod 3          3 is a divisor of m[k] iff k is even

 

Therefore:

 

For all primes p,  except 3,  3 is a divisor of m[6k]=0 since 6=lcm(2,3).
If p=3, 3 is not a divisor of m[k] (and hence also not of m[6k]).

 

So the only possible solutions of numbers of the form m[6k] are generated by the prime 3.
I tested p=3 until k=666 (m[666] has 105987 digits) but no prime was found. No apparent pattern in the smallest divisor of m[6k].
I think that a solution with p=3 can not be excluded entirely.

 

***

Emmanuel wrote (Set 2, 2017)

The answer to the puzzle 892 is immediately found as follows :

 

If  p = 1 mod 3, then the set of powers  { p^0, p^1, ..., p^k } is

   {1, 1, ..., 1} mod 3.

Thus, the concatenation of these powers will be congruent to  k+1  mod 3.

Thus, if you have  k = 6m - 1, the concatenation will be divisible by 3.

 

If  p = -1 mod 3  then the set of powers  { p^0, p^1, ..., p^k } is

   {1, -1, 1, -1, ..., (-1)^k} mod 3.

Thus, the concatenation of these powers will be :

  *   congruent to  1-1+1-1+...+1 = 1  mod 3  if  k  is even

  *   congruent to . 0  when k is odd.

Thus, if you have  k = 6m - 1, the concatenation will be divisible by 3.

...

The case  p = 3  should be treated also.

It is indeed clear that for every  k  the concatenations  p^0 & p^1 &  ... & p^k  are not divisible by  3.

Thus, there may be values of  k  of the form  6m-1  that give prime concatenations (though I could not find one below  203 ; bigger values of  k  demand more time due to the size of the concatenation).

***

T. D. Noe wrote on 7 Set 2017:

For prime p=3, I was unable to prove the non-existence of primes which are
the concatenation of orderly powers -- beyond the two (13 and 139) found
already. I tested the concatenation of powers of 3 up to 600. The last
number I tested was 1 3 9 27...3^600, a number over 86000 digits long. It
is unlikely that there are more primes of this form. The following proof
works for all other primes p:

We show that for all primes p not equal to 3, the sum of the digits of the
number

    N = 1 ; p ; p^2 ;...; p^(6k-1)     (where ";" means concatenation)

is a multiple of 3. We do the case k=1 here, but the general case is similar.

By Fermat's theorem, for prime p not equal to 3, p^2 = 1 (mod 3). Cubing
both sides, this leads to p^6 = 1 (mod 3). By considering the two cases p =
1 (mod 3) and p = -1 (mod 3), it is clear that 3 divides 1 + p + p^2 + p^3
+ p^4 + p^5.

For every p, there is a power m of 10 such that p^5 < 10^m. In base 10^m,
consider the number N' = 1 p p^2 p^3 p^4 p^5. The sum of its "digits" is 1
+ p + p^2 + p^3 + p^4 + p^5, which is divisible by 3. Hence, N' is
divisible by 3. The only difference between N and N' is the inclusion of
some zero digits, which do not have any affect on a number being divisible
by 3. QED

***

---