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.
***
|
