Shyam Sunder Gupta's recent posting to the NmbrThry list
reports that Umut Uludag's base-10 concatenation in
http://oeis.org/A173426 gives a prime at n = 10 and a
probable prime at n = 2446 with 17350 decimal digits.

The OEIS sequence http://oeis.org/A173427 gives Uludag's
corresponding binary concatenation. It contains the primes
13 and 7069, at n = 2 and n = 4. At n = 38, we see a prime
with 102 decimal digits. At n = 2861, I found a probable
prime with 18209 decimal digits, exceeding Gupta's result.

More generally, one may define a sequence A_b(n) by using
Uludag's concatenation in base b. With n < b, we obtain
squares: A_b(n) = R(b,n)^2, where R(b,n) = (b^n-1)/(b-1) is
a base-b repunit. Thus the first candidate for primality is
B(b) = A_b(b) = b*c + (c - b)*(1 + b*c), with c = R(b,b).

This is prime for bases b = 2, 3, 4, 6, 9, 10, 16, 40, 104.
Moreover, B(b) is probably prime for the base b = 8840.

For example, the prime B(2) = 13 occurs in A173427 and the
memorable prime B(10) = 12345678910987654321 occurs in
A173426. The prime B(16), with 38 decimal digits, is written
as "123456789abcdef10fedcba987654321" in hex. The next two
primes, B(40) and B(104), have 127 and 418 decimal digits.
B(8840), with 69770 decimal digits, dwarfs Gupta's finding.

I give here heuristics for the occurrence of such primes.
Since B(b) = b^(2*b-1)*(1 + O(1/b)), we expect a probability
of primality asymptotic to beta/(b*log(b)), with a constant
beta = prod_{p>2} (p*(p-1) - d(p))/(p-1)^2, evaluated by a
convergent product over odd prime p, with d(p) equal to the
number of residues of b modulo p*(p-1) for which p|B(b).

To compute d(p), we loop over the residues of b modulo p,
from 2 to p-1. For each, we find 0, 1 or 2 solutions for c,
modulo p, in the easily soluble quadratic modular condition
b*c + (c - b)*(1 + b*c) = 0 mod p. For each, we compute the
order of (1 + c*(b - 1)), modulo p. If it divides the order
z of b, modulo p, we add a contribution (p-1)/z to d(p).

By this means, I performed the product over primes p < 10^5
and estimated beta as close to 2.5127. OpenPFGW determined
that there are no more than 10 primes B(b) with b < 10^4.
The probability for an 11th prime B(b) with 10^4 < b < x is
estimated by 1 - (log(10^4)/log(x))^beta, which gives 43% at
x = 10^5, where B(x) has almost a million decimal digits.

ECPP primality proofs for A173426(2446) and A173427(2861)
would be feasible, since these probable primes have less
than 20000 decimal digits. Primality of B(8840), with 69770
decimal digits, might not be provable within my lifetime.

David Broadhurst, 1 August 2015
-- The Open University is incorporated by Royal Charter (RC 000391), an exempt charity in England & Wales and a charity registered in Scotland (SC 038302). The Open University is authorised and regulated by the Financial Conduct Authority.