What are the necessary conditions for UPC primes?

Question

0 68000 00027 7 is a UPC that the Hershey Company could use for some candy bar or other product. It happens that $6800000027$ is a prime number. But $68000000277$ is not. Likewise $6800000047$ is a prime number but quite obviously $68000000475$ is not. I'm sure that there exist GTIN-12 number that are prime which are also prime without the check digit, and maybe some of those numbers correspond to actual products you can buy at the supermarket or other store.

But what I want to know is this: what are the necessary (but not necessarily sufficient) conditions for such prime numbers?

Answer 1

Restating a comment, if I understand the gtin-12 algorithm correctly, the check digit $\ell$ in a 12-digit number $abc\ldots k\ell$ is determined by the congruence

$$3a+b+3c+\cdots+3k+\ell\equiv0\mod10$$

where the coefficients on the left alternate $3$ and $1$. This makes one necessary (but far from sufficient!) condition clear:

The 11-digit (prime) starting number $abc\ldots k$ must have an odd number of odd digits.

Beyond that I rather doubt there is any meaningful condition, beyond one that rules out $\ell=5$. Heuristically, there are $\pi(10^{11})\approx10^{11}/\ln(10^{11})$ 11-digit primes, so one would expect the number of 11- and 12-digit prime pairs to be something like

$${10^{11}\over\ln(10^{11})\ln(10^{12})}\approx1.43\times10^8$$

In particular, the denominator $\ln(10^{11})\ln(10^{12})\approx699.85$ suggests that one has a shot at finding such a pair by looking at around $700$ UPC labels. (Among the caveats, of course, is that manufacturers don't have a preference for 11-digit starting numbers that are even.)

Remark (added later): In terms of hunting for UPC labels that give prime pairs, the highlighted condition is really rather pointless. All you really need do is ignore any labels for which the last two digits are anything other than $1$, $3$, $7$, or $9$. The heuristic suggests that crowdsourcing the problem offers a reasonable chance of finding an actual prime-pair label: If a bunch of MSEers each look at a bunch of random products and run a primality test on the roughly $6$% that have a shot at being prime, someone might well find one. The aforementioned caveat, though, does seem to be a potential problem: As it happens, I have a shelf of CDs sitting handily behind me, but when I pulled a bunch down I found that the penultimate digit $k$ turned out to be a $2$ way more than a tenth of the time. I only found two labels that warranted testing. Needless to say, neither one produced a prime-pair example.

Answer 2

Don't give me the bounty, I just want to make some remarks that might be too long for comments.

The condition Barry gives in his answer was very useful to me in my search for such a pair that could theoretically correspond to a Hershey product, leading me to find $0$ $68000$ $00447$ $3$.

But before I use an online tool to check whether this corresponds to an actual product, I try the tool with a product I actually know to exist, one which I enjoyed very recently: Hershey's Pot of Gold, $0$ $68000$ $00113$ $7$ (do note that although $68000001137$ is a prime number, $6800000113$ is not, being divisible by $3$, $59$ and another prime). This one checks out: http://www.upcdatabase.com/item/068000113137

But no luck on $0$ $68000$ $00447$ $3$: http://www.upcdatabase.com/itemnotfound.asp?upc=0068000004473

Unfortunately the close neighbors search function is not available to me. Another website seems to suggest that Hershey has only one product with the $68000$ barcode, but I could have misunderstood. Maybe big companies can hold on to such large UPC blocks, I don't know.