eklhad@ihnet.UUCP (K. A. Dahlke) (05/07/85)
< and other diversionary tactics > How many primes, when written in base 10, also produce prime sub-numbers (looking at the first n digits)? For example: 7193 is in the set, since 7, 71, 719, and 7193 are all prime. The list begins: 3, 5, 7, 31, 37, 53, 59, 71, 73, 79, 311, 313, 317, 373, 379, 593, 599, ... Is the list infinite? If so, can anyone prove it. If not, and I conjecture not, what is the largest such number? Anyone with some time (personal and computer) can enjoy this one. -- Karl Dahlke ihnp4!ihnet!eklhad
chuck@dartvax.UUCP (Chuck Simmons) (05/08/85)
> The list begins: 3, 5, 7, 31, 37, 53, 59, 71, 73, 79, > 311, 313, 317, 373, 379, 593, 599, ... > > Karl Dahlke ihnp4!ihnet!eklhad Uh, what happened to 2? 2, 3, 5, 7, 23, 29, ...
muffy@lll-crg.ARPA (Muffy Barkocy) (05/09/85)
In article <226@ihnet.UUCP> eklhad@ihnet.UUCP (K. A. Dahlke) writes: >< and other diversionary tactics > > How many primes, when written in base 10, >also produce prime sub-numbers (looking at the first n digits)? >For example: 7193 is in the set, since >7, 71, 719, and 7193 are all prime. >The list begins: 3, 5, 7, 31, 37, 53, 59, 71, 73, 79, >311, 313, 317, 373, 379, 593, 599, ... >Is the list infinite? >If so, can anyone prove it. >If not, and I conjecture not, what is the largest such number? >Anyone with some time (personal and computer) can enjoy this one. >-- > >Karl Dahlke ihnp4!ihnet!eklhad What *is* that list? It is not a list of the first n primes, nor is it a list of the primes described... Muffy
bs@faron.UUCP (Robert D. Silverman) (05/10/85)
> In article <226@ihnet.UUCP> eklhad@ihnet.UUCP (K. A. Dahlke) writes: > >< and other diversionary tactics > > > How many primes, when written in base 10, > >also produce prime sub-numbers (looking at the first n digits)? > >For example: 7193 is in the set, since > >7, 71, 719, and 7193 are all prime. > >The list begins: 3, 5, 7, 31, 37, 53, 59, 71, 73, 79, > >311, 313, 317, 373, 379, 593, 599, ... > >Is the list infinite? > >If so, can anyone prove it. > >If not, and I conjecture not, what is the largest such number? > >Anyone with some time (personal and computer) can enjoy this one. > >-- > > > >Karl Dahlke ihnp4!ihnet!eklhad > > > What *is* that list? It is not a list of the first n primes, nor is it a > list of the primes described... > Muffy The set is quite definitely finite. In fact it is rather small and takes very little computer time to generate. A better way of defining it is: The set of all primes p such that 10p + r (r = 1,3,7,9) is also in the set for some r. It is easy to convince yourself that the set should be finite based on probability arguments. I don't know of a rigorous proof other than construction of the set.
td@alice.UUCP (Tom Duff) (05/14/85)
Given problem: > How many primes, when written in base 10, >also produce prime sub-numbers (looking at the first n digits)? The problem statement is fairly ambiguous, but applying some AI, we get the following program to solve it (mod bugs), and output: $ cat prime.c /* print out all primes all of whose initial substrings are also prime */ #define N 100 long p[N+4]={2, 3, 5, 7}; prime(n){ /* n odd */ register i; for(i=3;i*i<=n;i+=2) if(n%i==0) return 0; return 1; } main(){ register long i, j, k; printf("2\n3\n5\n7\n"); for(i=0,j=4;i!=j;i++){ if(p[i]>=0x7fffffff/10){ printf("overflow\n"); exit(1); } if(j>=N){ printf("approximately out of room\n"); exit(1); } if(prime(k=10*p[i]+1)){ p[j++]=k; printf("%d\n", k); } if(prime(k=10*p[i]+3)){ p[j++]=k; printf("%d\n", k); } if(prime(k=10*p[i]+7)){ p[j++]=k; printf("%d\n", k); } if(prime(k=10*p[i]+9)){ p[j++]=k; printf("%d\n", k); } } exit(0); } $ cc prime.c $ a.out|pr -t -l1 -6 2 3 5 7 23 29 31 37 53 59 71 73 79 233 239 293 311 313 317 373 379 593 599 719 733 739 797 2333 2339 2393 2399 2939 3119 3137 3733 3739 3793 3797 5939 7193 7331 7333 7393 23333 23339 23399 23993 29399 31193 31379 37337 37339 37397 59393 59399 71933 73331 73939 233993 239933 293999 373379 373393 593933 593993 719333 739391 739393 739397 739399 2339933 2399333 2939999 3733799 5939333 7393913 7393931 7393933 23399339 29399999 37337999 59393339 73939133 $
matt@oddjob.UUCP (Matt Crawford) (05/15/85)
In article <298@faron.UUCP> bs@faron.UUCP (Robert D. Silverman) writes: >The set is quite definitely finite. In fact it is rather small and takes >very little computer time to generate. A better way of defining it is: > >The set of all primes p such that 10p + r (r = 1,3,7,9) is also in the >set for some r. > >It is easy to convince yourself that the set should be finite based >on probability arguments. I don't know of a rigorous proof other >than construction of the set. The set YOU describe must be either empty or infinite. Otherwise it would have a maximum member P, but by your definition 10P+r is also in the set. Therefore there is no maximum member. Will this definition for the disputed set work? The set consists of {2,3,5,7} and all primes p such that int(p/10) is also in the set. this does not make the cardinality of the set obvious, but the decision algorithm for membership is easy. _____________________________________________________ Matt University crawford@anl-mcs.arpa Crawford of Chicago ihnp4!oddjob!matt
jfk2@nvuxf.UUCP (J Kitchin) (05/19/85)
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.
muffy@lll-crg.ARPA (Muffy Barkocy) (05/20/85)
I have seen several postings on the prime number question. As I understand
it, a prime number is one which is only divisible by itself and one. Now,
in many of the postings on this, I have seen "9" or numbers ending in "9"
given as answers. Last I heard, 9 was divisible by 1, 3, and 9. What am
I missing, or am I?
Muffyables@mcc-db.UUCP (King Ables) (05/20/85)
> ..in many of the postings on this, I have seen "9" or numbers ending in "9" > given as answers. Last I heard, 9 was divisible by 1, 3, and 9. Well, if 9 is in the list (I haven't been paying too much attention) then they're either joking or confused... but some numbers ending in "9" are ok (for example, 19 and 29). -King ARPA: ables@mcc UUCP: {ihnp4,seismo,ctvax}!ut-sally!mcc-db!ables