Truncating primes

22 views
Skip to first unread message

Rajnish Kumar

unread,
Jul 14, 2006, 3:36:37 AM7/14/06
to
Here is one very STICKY kind of prime.
There are a few primes who are so obsessed with remaining primes that
even after chopping off their last digits they remain primes.

Here is an interesting Prime number

593993, this number is a prime. Strangely truncating (removing the last
digit) this number we find

59399 5939 593 59 5

These are all prime numbers, very fascinating.

The following number have the same property.


73939133
Find some more

Christian Siebert

unread,
Jul 14, 2006, 4:29:01 AM7/14/06
to
> There are a few primes who are so obsessed with remaining primes that
> even after chopping off their last digits they remain primes.
>
> Find some more
There are only 14 such prime numbers of this format:

2
23
233
2333
23333
23339
23399
233993
2339933
23399339
29399999
37337999
59393339
73939133

So there is nothing interesting... :-(

Christian

Rajnish Kumar

unread,
Jul 14, 2006, 4:51:30 AM7/14/06
to
Dear Christian
You think that is boring, well not to me. I am impressed with your
knowledge

The Last Danish Pastry

unread,
Jul 14, 2006, 5:06:43 AM7/14/06
to
"Rajnish Kumar" <rajnishk...@gmail.com> wrote in message
news:1152862597.7...@p79g2000cwp.googlegroups.com...

See
http://mathworld.wolfram.com/TruncatablePrime.html

--
Clive Tooth
www.clivetooth.dk
Stock photos:
http://submit.shutterstock.com/?ref=61771


Christian Siebert

unread,
Jul 14, 2006, 5:19:41 AM7/14/06
to
> See http://mathworld.wolfram.com/TruncatablePrime.html
Ah yes, I was a bit too fast. I wanted to find a larger prime number of
this form, so I printed only the currently smallest one. The correct
answer is: there is only a constant number of such primes (but 83
instead of my 14). Sorry...

Christian

Jens Kruse Andersen

unread,
Jul 14, 2006, 1:49:11 PM7/14/06
to
> > See http://mathworld.wolfram.com/TruncatablePrime.html

Christian Siebert wrote:
> Ah yes, I was a bit too fast. I wanted to find a larger prime number of
> this form, so I printed only the currently smallest one. The correct
> answer is: there is only a constant number of such primes (but 83
> instead of my 14).

All truncatable primes can easily be found by computer in seconds.
It becomes more interesting if 2 or 3 digits are removed at a time:
http://hjem.get2net.dk/jka/math/left-truncatable.htm
There are probably larger primes but a finite number.
Can you beat the listed records?

--
Jens Kruse Andersen


Christian Siebert

unread,
Jul 15, 2006, 4:19:17 PM7/15/06
to
> All truncatable primes can easily be found by computer in seconds.
Yes, I've just tested it: there are 4259 left-truncatable prime
numbers, with 357,686,312,646,216,567,629,137 being the largest one.

> It becomes more interesting if 2 or 3 digits are removed at a time

Just curious: It it easy to prove that there are infinity many prime
numbers. Is it also possible to prove (for a fixed k) that there are
infinity many left-truncatable prime numbers of order k?

> http://hjem.get2net.dk/jka/math/left-truncatable.htm
> There are probably larger primes but a finite number.
> Can you beat the listed records?

Not with the trivial implementation I've hacked together within two
minutes. I let it run for two hours and found the 166 digit number
83407413931464561918816674307519277235617416385574137410305417139 \
01265886584309018199965947257366357541878698780936021762189791214 \
241224169216265742162019111212121061
which seems to be a left-truncatable prime of order 2.

I wouldn't be surprised if there is a much better approach to search
for those kind of numbers. What method did you use?

Christian

Jens Kruse Andersen

unread,
Jul 15, 2006, 9:54:32 PM7/15/06
to
Christian Siebert wrote:
> > All truncatable primes can easily be found by computer in seconds.
> Yes, I've just tested it: there are 4259 left-truncatable prime
> numbers, with 357,686,312,646,216,567,629,137 being the largest one.

4260 to be exact. I agree with other sources on this.

> > It becomes more interesting if 2 or 3 digits are removed at a time
> Just curious: It it easy to prove that there are infinity many prime
> numbers. Is it also possible to prove (for a fixed k) that there are
> infinity many left-truncatable prime numbers of order k?

My guess would definitely be that the number is finite for any fixed k and
any fixed base.
The average distance between primes tends to infinite but any fixed k
will only give a finite number of possibilities to add k digits to the left of
a prime. I have a hard time imagining that continue to produce primes forever.

> > http://hjem.get2net.dk/jka/math/left-truncatable.htm
> > There are probably larger primes but a finite number.
> > Can you beat the listed records?
> Not with the trivial implementation I've hacked together within two
> minutes. I let it run for two hours and found the 166 digit number
> 83407413931464561918816674307519277235617416385574137410305417139 \
> 01265886584309018199965947257366357541878698780936021762189791214 \
> 241224169216265742162019111212121061
> which seems to be a left-truncatable prime of order 2.

I have confirmed this with primality proofs by PARI/GP.

> I wouldn't be surprised if there is a much better approach to search
> for those kind of numbers. What method did you use?

Probably the same as you. If my program is initialized with "61" as the
rightmost digits then it also starts generating primes on the form
".....19111212121061".
My page says:
"The prime was found by starting with 11 and recursively trying to add two
digits from 10 to 99 on the left end."
You wisely avoided starting with 11 which would have reproduced my search.

I used a C program with generic trial factoring and a single prp test by the
GMP library.
Custom made trial factoring could be a little faster but I don't see other
ways to optimize.

I searched a couple of days and found 20 left-truncatable primes of order 2
with 166 digits, but only one with 178 (which fortunately could be extended to
184).
An exhaustive search for left-truncatable primes of order 2 seems infeasible.
It would be feasible for right-truncatable. I completed primes starting with
11 in around 2 GHz weeks. That's 1 of the 21 possible starts. I'm not planning
to search other starts.

--
Jens Kruse Andersen


Reply all
Reply to author
Forward
0 new messages