Problems & Puzzles: Puzzles

Puzzle 235. Dropping digits primes

There are primes that remain primes after the digit in each position is dropped, one at a time, for all the positions.

Example:

The prime 94397 produces this way the following five primes: 4397, 9397, 9497, 9437 & 9439. By the way, please notice that in particular the prime 94397 has the property that the five primes thus produced are distinct.

Q1. Is there a larger prime than 94397 with this property (that all the such produced primes are distinct)?

Of course, you may disregard the condition of distinctness for the primes produced.

Example:

The prime 10000000097 produces the following eleven-total but only four-distinct primes: 97, 1000000097 (eight times), 1000000007, 1000000009

Q2. Get a large (titanic?) dropping-digits-prime, disregarding the condition of distinctness for the primes produced.

Now let's pose a  harder problem: for a given prime you may also drop the digits, not one at a time but, simultaneously all the digits of one kind, one kind at a time, for all the kind of digits available in the original prime

Example:

The prime 1210778071 gives primes 12177871, 2077807, 110778071, 1210801 and 121077071 after dropping the digits 0, 1, 2, 7 and 8 (example given by Patrick De Geest in his sequence A057876 ; See also the Puzzle 110 of this site)
 

Q3. Obtain the earliest prime of this type, with the additional property of being pandigital (that is to say that the original prime contains all the decimal digit [0-9] at least once)

Hint: Maybe it is a good idea you to find (construct) first the earliest odd number with the following properties: a) it is pandigital b) the digital root of the ten numbers produced after dropping all the digits of each kind, are not divided by 3.  Once you get it you know for sure that the prime asked in Q3 is larger than this odd number.

Q4. Obtain the following three primes to the asked in Q3 (in order to publish them in the EIS database)

Q5. Obtain a large (titanic?) prime as the asked in Q3.

Solution:

First of all, Patrick De Geest reminded to me that the Q.3 of this puzzle is related with the subject of the Puzzle 110 of these pages.

Wilfred Whiteside, Faride Firoozbakht and Giovanni Resta sent some contributions to this puzzle. Only Resta got a solution for the harder question (Q3)

Wilfred wrote:

Here is my non-answer to puzzle 235 Q1:

Searched up through all 10 digit numbers and found no number bigger than 94397 that is prime and which remains prime when any single digit is dropped.

The following composite numbers generate primes when single digits are dropped:

6 digits:
310139 = composite
370139 = composite
376493 = composite
691493 = composite
714713 = composite

7digits:
1416719 = composite
5187417 = composite

8, 9 & 10 digits: none. Odds getting small of any solution with 11 or more digits

***

Faride wrote:

Q1. There isn't a prime larger than 94397 with this property up to prime(10^8).

Q2: 3000000770177 is one of the primes with this property that I found.

(770177,300000770177,300000070177,300000077177,300000077077&300000077017 are primes).

If there exist n (n > 18) such that,10^n+(10^19-1)/9 and 10^(n-1)+(10^18-1)/9 be primes then 10^n+(10^19-1)/9 is a large prime with this property.

The number n's that 10^n+(10^19-1)/9 is prime are : 18 598 1538,?,... (it's interesting that the last digit of each is 8,we can prove all terms of this sequence is even.)

The number n's that 10^(n-1)+(10^18-1)/9 is prime are: 4,10,12,16,19,23,26,105,116,164,201,215,242,357,372,377,529,606,?,...

Q3: I couldn't find the earliest pandigital prime of this type. But I found the earliest pandigital prime that more than eight numbers (of ten numbers) produced after dropping all the digits of each kind, are primes. This nice prime is " 10118974652473 " which produces nine primes. (1011897465247 = 29*34893016043). Thus the answer of Q3 is greater than 10118974652473.

[ Note by CR. This number will be added to the page of the Puzzle 110]

Later she sent the following other primes of this type: 222223333333, 167777777777777, 44444441333333333333 and this huge one:

***

Giovanni wrote the following splendid report for his very smart approach:

I have searched for solutions of Q3 (and Q4) of Puzzle 235, that is pandigital primes such that dropping in turn every 0s,1s,2s,...,9s, the result is always a prime. According to my experiments the least such number, and the  only one with 14 digits, is 78456580281239. At the moment I'm searching for 15 digits solutions. I will terminate at the beginning of next week.

At the present moment the other (15 digits) solutions I found are 145661743208479 248370614991571 248401577960317 436341859727017 467450831621479 474354192860371 658005884237291 but since I do not generate them in order, I do not know if they are the next smallest ones...

I used your hint. Basically: the overall number must be prime, so its residue mod 3 must be 1 or 2. Assume it is 1 (the case 2 is similar). If the number contains n times the digit d and if (n*d)==1 (mod 3) then deleting digit d from the number we obtain a number which is divisible by 3, and thus not prime. Hence, for each digit d (and all must be present) the product d*n_d must be equal to 2 or 0 (mod 3). This means that there can be any number (>1) of 0,3,6,9, and there must be 2,3,5,6,8,... 1's, 4's and 7's, and 1,3,4,6,..., of 2's, 5's and 8's.

if I'm correct the only possibilities (remembering also the constraint on the mod of the whole number) for a 14 digit number are the following (and there are no possibilities with less digits)

0123456789
----------
1121121131
1121131121
1131121121
1211211311
1211311211
1311211211

considering for example the first row above, I have to search all the permutations of 01223455678889. This is what I've done for 14 digits, founding 1 solution and for 15 digits (still running).

The algorithm I'm using for permutations (with repetitions) does not produce the number in increasing order, so I have to wait the end of run to have the right numbers. I'm using 6 machines and I estimate I'll need another day or two to finish the search for 15 digits.

...

(one week later he sent the following results of his search):

78456580281239 (14 digits)
145661743208479 (15 digits)
199408767345217
248370614991571
248401577960317
286770449139571
414178650126793
419277134580691
436341859727017
467450831621479
474354192860371
493710281416537
658005884237291
849157174162039

***