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 eleventotal but only fourdistinct primes: 97, 1000000097 (eight
times), 1000000007, 1000000009
Q2. Get a large
(titanic?) droppingdigitsprime, 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
[09]
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 nonanswer 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^191)/9 and 10^(n1)+(10^181)/9 be primes then
10^n+(10^191)/9 is a large prime with this property.
The number n's that 10^n+(10^191)/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^(n1)+(10^181)/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:
444444444444444444444444444444444444444444444444441111111113333333333333333333333333
***
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
***
