# Binary Distance between the two Primes

Given a prime number p, is there always a smaller positive integer exponent k such that p+2^k is also prime? We will call the smallest possible value of this exponent the k*. We could interpret this number k as the position where we could add 1 to the binary expression of p in order to obtain another prime number, the smallest possible one.

For example, 61+2^8 = 317. The prime number 61 has a binary expression of 111101 and its "binary distance" function is equal to 8 (dyb[61]=8). This means that in the 8th position of its binary expression, we need to add a 1 (considering the first position as 0, so we have positions from 0 to 5 in 111101): 100111101, which is equal to the prime number 317. 31+2^4 = 47 dyb[31]=4, since 31 in base 2 is 11111, and 47 in base 2 is 101111.

dyb[n_] := Module[{c = 0, p = 0, i = 1},
If[n > 2 && PrimeQ[n],
While[! PrimeQ[n + 2^i], i = i + 1; p = i; c = p; ]; c ]]

Print[dyb[61]]


I would like to obtain a table with a certain quantity of primes, with the first column containing the primes p, the second column containing the binary distance k, and the third column containing the second prime q.

Prime p ----- Binary distance ----- Prime q
61             8                   317

• seems like there is a typo at the end of the sentence... We will call the smallest possible value of this exponent the " . perhaps we can call this k* ? please change the edit if this makes no sense Jul 23, 2023 at 0:15

Are you looking for something like Grid[Table[p = Prime[n]; {p, dyb[p], p + 2^dyb[p]}, {n, 1, 10}], Frame -> All]?

EDIT: I think this fixes your function:

dyb[n_] := Module[{i = 0}, If[PrimeQ[n], While[! PrimeQ[n + 2^i], i = i + 1;]; i]];
Grid[Table[p = Prime[n]; {p, dyb[p], p + 2^dyb[p]}, {n, 2, 20}], Frame -> All]

• It seems that your function dypis not working correctly for all prime numbers, or did I misunderstand something? Jul 22, 2023 at 13:26
• In fact. His table demonstrated some primes where it doesn't work. The table should provide p dist q 2 0 3 3 1 5 5 1 7 7 2 11 11 1 13 13 2 17 17 1 19 19 2 23 23 3 31 29 1 31 31 4 47 37 2 41 Jul 22, 2023 at 16:14
• @RubensVilhenaFonseca I have edited my answer. Jul 22, 2023 at 19:56
dyb[n_] := Module[{i = 0}, If[n > 2 && PrimeQ[n], While[! PrimeQ[n + 2^i], i = i + 1;]; i]]

primes = Select[Range[2, 97], PrimeQ];

resp = Table[dyb[n], {n, primes}];

Grid[Transpose[{primes, resp}], Dividers -> {{2 -> True}, {2 -> True}},
Alignment -> {{Center, Center}}, BaseStyle -> {FontWeight -> "Bold",
FontSize -> 14}, FrameStyle -> Directive[Thickness[0.005],
GrayLevel[0.7]], Background -> {{GrayLevel[0.95], {LightGray, GrayLevel[0.92]}}}]

• Your answer would be better, if you used the code to generate some numerical values. Jul 23, 2023 at 0:34