Problems & Puzzles: Puzzles

Puzzle 1011. Primes altering any digit of an integer Paolo Lava sent the following nice puzzle: Take an integer x (not necessarily prime) with d digits and consider the set A of numbers, out of 10*d, that are generated by changing one digit of x. Count the number of primes in the set A.(*)   E.g. 107 generates 13 primes because 107 is prime itself and are primes {101, 103, 109} (changing 7), {127, 137, 157, 167, 197} (changing 0), {007, 307, 607, 907} (changing 1). Then A = {7, 101, 103, 107, 109, 127, 137, 157, 167, 197, 307, 607, 907}. Here below a list of x-champions Number x Count of primes 1 4 11 8 13 10 101 11 107 13 357 14 1001 15 1011 16 10759 17 11487 19 42189 20 113183 21 344253 23 1851759 24 4787769 25 Q1. Can you extend this table? Q2. Redo Q1 when x goes only for prime numbers. ____ (*) This issue was already studied in the sequence A209252

---

During the week 1-7 August, 2020, contributions came from Simon Cavegn, Adam Stinchcombe, Emmanuel Vantieghem, Vicente Felipe Izquierdo, Oscar Volpatti, Ray Opao, Paul Cleary

***

Simon wrote:

The algorithm I implemented is fast, but limited to 32bit array indexing even in 64bit C#:
Create a byte array of 1GB size. Load primes below 1 billion from harddrive. (3.3 Seconds) For each prime: Create numbers by changing a digit and use the number as index for the byte array, increment the byte. (4 Minutes run time) Then walk through the 1GB array to get first highest count for Q1 and Q2. (2*2.5 Seconds)

 

Q1:
0 4
11 8
13 10
101 11
107 13
357 14
1001 15
1011 16
10759 17
11487 19
42189 20
113183 21
344253 23
1851759 24
4787769 25
15848679 27
139367847 28
240889077 29

 

Q2:
2 4
11 8
13 10
101 11
107 13
1297 14
1423 15
9433 16
13597 17
105967 18
249533 19
1006133 20
1477031 21
10866913 22
11917049 23
107640251 24
119628479 26

***

Adam wrote:

I found a sequence of 28 primes, starting with a seed x of

799699777757944797973477593

that leads to the primes

{799699777757944797773477593,799699777757944797973477393,799699777757944797923477593,

799299777757944797973477593,799699777757144797973477593,799699777757244797973477593,

799699777707944797973477593,799699777757944797983477593,799799777757944797973477593,

799699777757944797973477523,799699777757964797973477593,799699777757944797993477593,

799619777757944797973477593,699699777757944797973477593,799699777757944797973477597,

799699777757944797977477593,799699777757944797978477593,799698777757944797973477593,

799699777757948797973477593,799699777757944717973477593,799699777757944797973478593,

799699777757944797973427593,799699777757944797973437593,799699777757944796973477593,

799699777758944797973477593,779699777757944797973477593,799699777757944798973477593,

749699777757944797973477593}

***

Emmanuel wrote:

Q1
The list continues as follows :
15848679       27
139367847     28
240889077     29
Next number  x  (if it exists) will be > 10^9

Q2
The list goes as follows :
2                    4
11                  8
13                 10
101               11
107               13
1297             14
1423             15
9433             16
13597           17
105967         18
249533         19
1006133       20
1477031       21
10866913     22
11917049     23
107640251   24
119628479   26
The next prime (if it exists) will be > 10^9

***

Vicente wrote:

26      16.121.457

27      15.848.679

28    139.367.847

29    240.889.077
Not others under 7x10^8.

***

Oscar wrote:

I searched up to about 3.5*10^11, until I found a prime champion with count at least 30.
In the following tables, column "count" precedes column "champion" for readability.

Q1 champions

4   1
8   11
10 13
11 101
13 107
14 357
15 1001
16 1011
17 10759
19 11487
20 42189
21 113183
23 344253
24 1851759
25 4787769
27 15848679
28 139367847
29 240889077
33 1167555543
34 111738007953

Q2 prime champions

4   2
8   11
10 13
11 101
13 107
14 1297
15 1423
16 9433
17 13597
18 105967
19 249533
20 1006133
21 1477031
22 10866913
23 11917049
24 107640251
26 119628479
28 1812918883
29 22747222273
30 342054335261


This issue was also studied in the sequence A048853, co-authored by G.L. Honaker, Jr. and Patrick De Geest.
They added two restrictions: we must exclude the starting number from the count (if prime), and we can't change its leading digit to 0.
 
However, such restrictions don't reduce the count value for Paolo Lava's Q1 champions producing 4, 14, 15, 17, 20, 23, 24, 28, 33 and 34 primes respectively.

***

Ray wrote:

Q1. No (after checking up to x < 13000000), but I completed it for some missing counts:

x:: count

200:: 0
90:: 1
20:: 2
22:: 3
0:: 4
12:: 5
29:: 6
21:: 7
11:: 8
17:: 9
13:: 10
101:: 11
109:: 12
107:: 13
357:: 14
1001:: 15
1011:: 16
10759 ::17
13299:: 18
11487:: 19
42189:: 20
113183:: 21
984417:: 22
344253:: 23
1851759:: 24
4787769:: 25
 

Q2: I checked up to x < 40000000 and got following:

x:: count

294001 ::1
46769:: 2
5077:: 3
2:: 4
929:: 5
29:: 6
37:: 7
11:: 8
17:: 9
13:: 10
101:: 11
109:: 12
107:: 13
1297:: 14
1423:: 15
9433:: 16
13597:: 17
105967:: 18
249533:: 19
1006133:: 20
1477031:: 21
10866913:: 22
11917049:: 23

***

Paul wrote:

Q1

Number x       Count of primes

15848679      27

139367847    28

240889077    29

 

Q2

Number x       Count of primes

2                      4

11                    8

13                    10

101                 11

107                 13

1297               14

1423               15

9433               16

13597             17

105967           18

249533           19

1006133         20

1477031         21

10866913      22

11917049      23

107640251    24

119628479    26

1812918883  28

***