OFFSET
1,1
COMMENTS
The first primes reached are 485398038695407, 2, 3, 37, 5, 288368629084891241583296816292460511, 7, 137, 55212283888448697916635329662406145945631873447, ...
Except for the second term, n and a(n) have the same parity, i.e., a(n) == n (mod 2). Is it proved (or can it be disproved) that the required k exists for all n? a(10), a(21), a(24), a(38), a(52), a(55) are larger than 1500, if they exist. - M. F. Hasler, Apr 26 2017
a(10) > 40000. Terms at indices 24, 38, 55, 56, 57, 60, 62, 65, 66, 76, 78, 91, 92, 95 are > 20000. A large known term is a(330) = 9376. - Hans Havermann, May 17 2017
LINKS
Paolo P. Lava, First 100 terms (with -1 if a(n) is not presently known)
FORMULA
a(n) = 1 if n is prime.
EXAMPLE
a(1) = 15 because we have to concatenate the base-2 numbers from 1 to 15 to reach the first prime. In fact concat(1, 10, 11, 100, 101, 110, 111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111) =
1101110010111011110001001101010111100110111101111, which is prime (in base 10 it is 485398038695407).
MAPLE
P:=proc(q) local a, b, k, n; for n from 1 to q do
if isprime(n) then print(1); else a:=convert(n, binary, decimal);
for k from n+1 to q do b:=convert(k, binary, decimal); a:=a*10^(ilog10(b)+1)+b; if isprime(convert(a, decimal, binary))
then print(k-n+1); break; fi; od; fi; od; end: P(10^10);
MATHEMATICA
With[{nn = 2^10}, Table[Module[{k = n, w = IntegerDigits[n, 2]}, While[And[! PrimeQ[FromDigits[w, 2]], k - n < nn], k++; w = Join[w, IntegerDigits[k, 2]]]; If[k - n >= nn, -1, k - n + 1]], {n, 50}]] (* Michael De Vlieger, Apr 26 2017, with -1 indicating values of k > limit nn *)
PROG
(PARI) a(n, c=1, m=n)=while(!ispseudoprime(n), c++; n=n<<#binary(m++)+m); c
CROSSREFS
KEYWORD
nonn,base,more
AUTHOR
Paolo P. Lava, Jan 24 2017
EXTENSIONS
Edited by Max Alekseyev, Apr 26 2017.
Further edits from N. J. A. Sloane, Apr 26 2017
a(18) = 586, a(28) = 934, a(35) = 947, a(51) = 1325 (PRP), and further edits from M. F. Hasler, Apr 26 2017
STATUS
approved