Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.1 6/24/83; site nvuxf.UUCP
Path: utzoo!watmath!clyde!cbosgd!ihnp4!mhuxn!mhuxr!ulysses!allegra!bellcore!sabre!zeta!epsilon!gamma!pyuxww!pyuxv!nvuxa!nvuxf!jfk2
From: jfk2@nvuxf.UUCP (J Kitchin)
Newsgroups: net.math
Subject: Re: Another Prime Number Question With No Practical Application
Message-ID: <114@nvuxf.UUCP>
Date: Sun, 19-May-85 04:00:35 EDT
Article-I.D.: nvuxf.114
Posted: Sun May 19 04:00:35 1985
Date-Received: Wed, 22-May-85 01:09:00 EDT
Organization: Bell Communications Research, Red Bank, NJ
Lines: 64

Given problem:
>	How many primes, when written in base 10,
>also produce prime sub-numbers (looking at the first n digits)?

Let's be a little more formal (and general) in stating the
question and see if anything interesting comes about.

Let   N   be the set of non-negative integers
Let   P   be the set of primes, equal to {2,3,5,7,11,...} in base 10
Let   b   be a postive integer >= 2 ; the problem so far (with one
	  execption) has been stated with  b=10 .
Let   %/  be the integer divide operator, e.g.,   137%/10 = 13
Let   A   be a subset of  N
Let  ~e~  stand for "is an element of"

Let   f   be the mapping  f[A] = { x ~e~ N : x%/b ~e~ A }

          (We should say  f sub b  but suppress the subscript for now)
	  (Also, define f[{ }] = { } , where { } is the empty set)

Now to the question:

Define   A0 = {0}
	 A1 = f[A0] intersect P
	 A2 = f[A1] intersect P
	 A3 = f[A2] intersect P
	 and so on.

Question:  What is the smallest  k  such that  Ak is empty?
	   
Remark:  The "set in question" is  A1 union A2 union A3 union ...  .
	 To say  k=infinity  when  b=10  is to say
	 that there are an infinte number of primes
	 whose "substrings" in base 10 representation are also prime.
	 Tom Duff of AT&T Bell Labs posted results of a computer
	 search showing
	 A8 = {23399339, 29399999, 37337999, 59393339, 73939133 }
	 and A9 is empty (k=9). (Did I get that right, Tom?)

Remark:  k=1 for b=2
	 k=5 for b=3
	 Don't believe the above two claims without checking.
	 I did them by hand.

Another Question: Is k monotone increasing as a function of b?

Remark: Besides looking at values of b other than 10, I
	suggest making A0 arbitrary.
	For example, set A0 = {1,2,3,...,9} find k for b=10.
	How much greater is this k than that for A0={0}?

Final Remarks: This "question with no practical application"
              is interesting because it
	      combines primality properties with number
	      representation properties. I doubt there
	      are any suprises (like an infinite k
	      for some finite b), but ya never Know.
              While computer searches are nice, a simple
	      proof of "no suprises" would be something
	      to talk about. Proof of a surprise would
	      be something to write about. Any takers?

John Kitchin
Bell Communications Research, Inc.