Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.1 6/24/83; site alice.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!allegra!alice!td
From: td@alice.UUCP (Tom Duff)
Newsgroups: net.math
Subject: Re: Another Prime Number Question With No Practical Application
Message-ID: <3725@alice.UUCP>
Date: Tue, 14-May-85 15:50:47 EDT
Article-I.D.: alice.3725
Posted: Tue May 14 15:50:47 1985
Date-Received: Wed, 15-May-85 01:50:57 EDT
References: <226@ihnet.UUCP> <574@lll-crg.ARPA>, <298@faron.UUCP>
Organization: Bell Labs, Murray Hill
Lines: 46

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
$