Problems & Puzzles: Puzzles

Puzzle 78.- The least prime by concatenating K consecutive integers


Days ago, Patrick De Geest asked by email to some of us by the least prime formed by the concatenation of K consecutive integers, a) in ascending order, b) in descending order.

For example:

a) ascending for K=4: 4567
b) descending for K=7:73727170696867 

(See the Neil's sequences A052077, A052078, A052079, A052080 )


Felice Russo and myself produced - a kind of easily - the required primes for K>6 to 150 or so, except for the following cases:

1) All K=0 mod 3
2) In ascending order: for K= 44 & 110
3) In descending order: for K= 22, 88 & 110

It's easy to explain why there are no prime numbers for a concatenation of L=0 mod 3 consecutive integers.

The surprising fact is that all the "K hard cases" are a multiple of 11 (the inverse is not true)

Questions:

1) can you solve the "K hard cases"?
2) or can you give an explanation about why all the "K hard cases" found are a multiple of 11?


Solution

Jim Howell noted yesterday (26/01/2000) that all numbers formed by a concatenation of 22 ( or a multiple of 22) consecutive numbers are divided by 11 if all the concatenated numbers are of the same length (the same quantity of digits)

I guess that I have discovered the reason of the Jim's observation and then the solution to the question 2 of this Puzzle. Please let me remind, first, the divisibility by 11, thumb rule:

If the absolute difference between the sum of digits in odd position and the sum of the digits in even position, of an arbitrary number N, is divided by 11 then N is also divided by 11:

Example N = 7183 is divided by 11 because (7+8)-(1+3) is divided by 11.

Now if you concatenate the first 22 two digits consecutive numbers:

N=10111213141516171819202122232425262728293931

the sum of digits in even position = 91
the sum of digits in odd position = 36
91-36 = 55 then N is divided by 11

Now, please verify by yourselves that if you shift the starting number from 10 to 11 or 12, or... the difference remains divisible by 11.

The same can be argued for N composed of 22 consecutive numbers of 3 or more digit-, always being all those concatenated numbers of the same quantity of digits.

Then only few -very few! - numbers N of this type are non-composite.... and that's why all numbers as a concatenation of multiple of 22 consecutive numbers, are hard to be a prime number...

***

Using the very important observation of Jim Howell I (C.R.) made a code in Ubasic to search precisely and only "near the border" of a power of 10. There is where changes the quantity of digits of consecutive numbers...

In such a way, it was not a very time consuming task to solve the following two of  "hard cases":

a) For K= 110, ascending, the following number is "strongpseudoprime":

9999968-9999969-9999970 ... 10000074-10000075-10000076-10000077 (digits=848)

b) For K=88, descending the following number is "strongpseudoprime":

100000000000006-100000000000005-...- 99999999999920-99999999999919 (digits=1239)

The remaining cases (descending 22, 110 & ascending 44) are out of the possibility of solving by the Ubasic code. Maybe here is necessary to switch to PRIMEFORM.

***

Following a recommendation of Felice Russo, I show here the current status for all K<150 multiples of 11 not divided by 3, bolding and in blue the 22 multiples, bolding & in red the unsolved cases, bolding & in fucsia the recently solved cases

K

Ascending

 Descending

11

129....139

219.....209

22

9998....10019

a...b, a>10^92, a>b

44

a...b, a>10^46, a<b 

 46.....3

55

305....359

 641....587

77

461....537 

 999...923

88

9962....10049

 10^14+6...10^14+6-87

110

10^7-32...10^7-32+109

See below the Chris Nash solution 

121

7 ... 127

 17441...17321

143

10127 ... 10269

 949...807

***

Chris Nash has tackled the "hard cases" (ascending K=44 and descending 22 & 110) using PRIMEFORM and formulas from his own, finding a solution for the last one: 

Descending K=110: 10^19+26....10^19-83 (2117 digits)

"I'll state without proof the formulae that can be used in PrimeForm for the concatenations of z consecutive integers, the first of which is 10^n-k (k<z), so the number of digits changes part-way through the number and so the 'hard cases' can be solved. Also we assume the number of digits changes only once, since all small values are tested. Take a deep breath - it took a long time to get these right - I checked with the known solutions.

1) Ascending case.

(((10^n-k)*10^(k*n)+(10^(k*n)-10^n)/(10^n-1)-(10^n-1))/(10^n-1))*10^((n+1)* (z-k))+((10^n)*10^((z-k)*(n+1))+(10^((z-k)*(n+1))-10^(n+1))/(10^(n+1)-1)-(10^n +z-k-1))/(10^(n+1)-1)

*ouch*

We start the search now for z=44, k=2 to 42 step 2, n=2 to 9999999.

2) Descending case.

(((10^n+z-k-1)*10^((z-k)*(n+1))-(10^((z-k)*(n+1))-10^(n+1))/(10^(n+1)-1)- 10^n)/(10^(n+1)-1))*10^(n*k)+((10^n-1)*10^(k*n)-(10^(k*n)-10^n)/(10^n- 1)-(10^n-k))/(10^n-1)

*ouch again*"

***

J. K Andersen wrote (1/2/03)

I have proved all the mentioned solutions, except K=110 descending, with Primo. The proof would take around a day but I skipped it. I have used PrimeForm/GW with Chris Nash's formula to find the smallest probable prime for K=44 ascending. It is the gigantic 10^348-32....10^348+11 with 15324 digits. This is Fermat prp to many bases. It cannot be proven with current programs and computers. A search to a=10^1000 found no solution for K=22 descending. This is the only remaining unsolved case and must have a prime above 10^22000. According to the heuristics there should be infinitely many solutions.

***

On Feb 2011 James Merickel wrote:

Jens Kruse Andersen and I have separately confirmed (I found) that the descending concatenation from 10^1631+10 down to 10^1631-11 is a prp.

Andersen added (Feb 18, 2011):

 I have now proved the K=110 descending solution with Primo.

 

***

 

 

 


Records   |  Conjectures  |  Problems  |  Puzzles