Problems & Puzzles: Puzzles

Puzzle 138.  Deletable primes


For sure you already know the "deletable primes". They were studied by Chris Caldwell as far as 1987 and are described in one page of his interesting "Glossary". The definition and the example are simply copied from this page:

A deletable prime has been defined ([Caldwell87]) to be a prime that you can delete the digits one at a time in some order and get a prime at each step. One example is 410256793, because the following are (deletable) primes:

  • 410256793
  • 41256793
  • 4125673
  • 415673
  • 45673
  • 4567
  • 467
  • 67
  • 7

It can be shown that you may construct very easily a deletable prime composed of any quantity of digits starting from any of the one-digit-primes available (2, 3, 5 & 7).

Less easy is - sometimes - to demonstrate that a given prime is deletable or not.

For sure the reader can imagine swiftly why these two things (construct = upward & demonstrate = downward) involve very different levels of difficulty.

Questions:

1. Construct a 500 digits-deletable-prime such that this prime has only one odd digit.

An easy example to construct of these kind of primes is the following 10 digits prime w/only one odd digit:

6002446267
600244627
60044627
6044627
604427
60427
6047
647
47
7

2. Verify if the following prime numbers are deletable or not:

a) 52077159376068462281 (20 digits)
b) 4512965097670605230048163378016770906883 (40 digits)

3. Exists a deletable prime constructible departing from each one of the four distinct one digit- prime available (2, 3, 5 & 7)?

For example, the prime 523 can be constructed from the prime 2 or from the prime 3 or from the prime 5.

523
23
2

523
23
3

523
53
5

4. Can you produce one rigidly-deletable-prime of 20 digits?

A rigidly-deletable-prime is such that in each step downward there is only one option to produce the next-smaller prime. An example of 8 digits is this:

12351467
1235167
123517
12517
1217
127
17
7

5. According to Caldwell it should exist infinite deletable primes. What about their complement, the primes that are not deletable, let's say the undeletable primes, are these infinite?

______
(*) or at least one titanic one such that all the involved primes are Strong-Pseudoprimes.


Solution

Paul Jobling has sent (14/5/2001) a 500 digits deletable prime, having only one odd digit, as the asked in question 1.

In order to support that this is a deletable prime he sent also the other 499 primes involved in the del500oneodd.txt file 128 Kb large. In his own words "Well, to be honest these numbers are only PRPs, however I am sure that it wouldn't take long for Titanix to prove them if necessary".

***

Michael Bell has solved (21/5/01) the question 2.b showing that the given prime is deletable, providing the list of primes pertinent.

7
97
947
9473
90473
950473
9750473
97504783
976504783
9765004783
97650047813
697650047813
6976500437813
26976500437813
269765004378013
2697650043780173
26976500483780173
126976500483780173
1269676500483780173
12696765200483780173
126096765200483780173
1260967652004813780173
12960967652004813780173
129609676052004813780173
1296096760520048137801783
12960967605200481378016783
129609676052004813780167083
1296096760520048137801677083
12965096760520048137801677083
129650967605230048137801677083
1296509676052300481637801677083
12965096760523004816378016770983
129650967605230048163378016770983
1296509670605230048163378016770983
12965097670605230048163378016770983
129650976706052300481633780167709883
4129650976706052300481633780167709883
41296509767060523004816337801677090883
451296509767060523004816337801677090883
4512965097670605230048163378016770906883

("Sorry if its wrong anywhere it was done by hand", M.B.)

***

Giuliano Daddario solved (6/9/01) the questions 2.a & 4:

2.a: the number 52077159376068462281 is not deletable

4:

I found this rigidly-deletable-prime of 20 digits:

13734216236814763253
1373421623681463253
137342162368143253
17342162368143253
1734216368143253
173421636814253
13421636814253
1341636814253
134163684253
13416368453
1341636853
134163683
13463683
1346363
134363
13463
3463
463
43
3

***

J. K. Andersen wrote (May 4, 2003)

Question 3.

There is no deletable prime constructible from both 2 and 7 - or from both 5 and 7.

Proof: By considering the downward sequence of required primes modulo 3. First divide the digits in sets mod 3: R0={0,3,6,9}, R1={1,4,7}, R2={2,5,8}. Deleting a digit from R0 does not change the mod 3 value of a number. Deleting a digit from R1 does change it. If the number is not divisible by 3 both before and after the deletion, then the number must change from 2 to 1 (mod 3). Similarly, deleting a digit from R2 must change the number from 1 to 2 (mod 3). It is now clear that if deletions from R0 is ignored and the final digit is from R1 or R2, then the remaining deletions must always alternate between R1 and R2. This means the downward sequence of numbers not divisible by 3 cannot end with both 2 and 7 - or with both 5 and 7.

The only case where 3 of the 4 one-digit primes is possible is the digits 2, 3 and 5. The smallest example of this is the given 523. 7 can only be combined with 3 and the smallest example is obviously 37.

The above proof also gives a quick test to prove certain primes are not

deletable: If the number of digits from R1 and R2 differs by more than two then the prime is not deletable since the alternating deletions cannot change this difference to 0 or 1 in the end position. Unfortunately this cannot be used to prove that the number in question 2a is not deletable since it has 6 digits from R1 and 7 from R2. Note that two consecutive deletions from the same of R1 or R2 is possible in one case: When the second deletion leads to the final prime 3, the only case where a number divisible by 3 is okay.

Example: 523, 23, 3.

***

 


Records   |  Conjectures  |  Problems  |  Puzzles