Problems & Puzzles: Puzzles

 Puzzle 1109 Related to A112386 Emmanuel Vantieghem sent the following nice puzzle: In the OEIS figures the sequence  A112386 :   11, 211, 31, 41, 511111, 61, 71, 811, 911, 101, 1111111111111111111, ... with description : smallest prime obtained by appending one or more 1's to n. I completed that sentence by ", -1 if no such prime exists."   I also added the comment that  a(37) = -1 since a) the set  {371, 3711, 37111, ...} has a covering by the primes  {3, 7, 13, 37}, b) which implied that there are infinitely many values -1  in  A112386. Hence I thought the following questions might interest the puzzlers of your site : Q1. Can you prove my two assertions a) & b)? Q2. What about  a(38)?  Q3. What about  a(56) ?

During the week Oct 29-Nov 5, contributions came from Gennady Gusev, Oscar Volpatti

***

a(n) has the formula ((9n+1)*10^k-1)/9.
Q1.
So let's write a(37)=(334*10^n-1)/9.
a(37) has a covering set {3, 7, 13, 37} since
- if n = 3k, then (334*10^n-1)/9 is divisible by 37
- if n = 3k + 2, then (334*10^n-1)/9 is divisible by 3
- if n = 6k + 1, then (334*10^n-1)/9 is divisible by 7
- if n = 6k + 4, then (334*10^n-1)/9 is divisible by 13

Q2.
a(38)=(343*10^n-1)/9
- if n = 3k + 1, then (343*10^n-1)/9 is divisible by 3
- if n = 3k + 2, then (343*10^n-1)/9 is divisible by 37
- if n = 3k, then (343*10^n-1)/9 is factored as ((7*10^k-1)/3)*((49*10^2k+7*10^k+1)/3).
Since (7*10^k-1)/3 can be written as 23, 233, 2333, ..., so for a(38) we have a covering set {3, 37, 23, 233, ...) with infinitely many terms.

Additionly: a(n) with n= 176 and 209 have a covering set {3, 7, 11, 13},
with n= 407, 814, 936 - {3, 7, 11, 37}.
That's all for n < 1000.

From Q1 and Q2 follows that a(n) with n = 371,3711,37111,.. and 381,3811,38111,.. are all composite.
So such n is infinitely many.

Q3.
a(56)=(505*10^k-1)/9 is prime for k=18470.

***

Oscar wrote:

For a given number x_0, let x_n be the number obtained by appending n ones to x_0:

x_n = ((9*x_0+1)*10^n - 1)/9
Q1: a(37+10101*k) = -1.
For x_0=37, consider index n=6*q+r:
if r=0, then 37 divides x_n;
if r=1, then 7 divides x_n;
if r=2, then 3 divides x_n;
if r=3, then 37 divides x_n;
if r=4, then 13 divides x_n;
if r=5, then 3 divides x_n;
so x_n is always composite for n>0.

The same covering holds for every number of the form
x_0 = 37+3*7*13*37*k = 37+10101*k.

Q2: a(38) = -1 too.
For x_0 = 38, consider index n=3*q+r;
if n=3*q+1, then 3 divides x_n;
if n=3*q+2, then 37 divides x_n;
if n=3*q, we have the algebric factorization x_n = y_q*z_q, with:
y_q = (49*100^q + 7*10^q + 1)/3,
z_q = (7*10^q - 1)/3;
so x_n is always composite for n>0.

Q3: a(56) = 18470.
For x_0 = 56, the first prp is x_18470.
This number is actually a proven prime, with proof certificate available at factordb.com.

***

 Records   |  Conjectures  |  Problems  |  Puzzles