5
$\begingroup$

Let

  • $k(0)=11$
  • $k(1)=1101$
  • $k(2)=1101001$
  • $k(3)=11010010001$
  • $k(4)=1101001000100001$
  • And So on....

    I've checked it up to $k(120)$, and I did't find anymore prime of such form. Are there anymore prime numbers of that form ? (I just realized that only $k(6n+5)$ could be a prime (?))

$\endgroup$
  • $\begingroup$ I think you have an off-by-one error, Peter. Letting k[b_][n_] := FromDigits[Flatten[{1, 1}~Join~Riffle[Map[0 & /@ Range[#] &, Range[n]], 1]~Join~If[n != 0, {1}, {}]], b], then searching k=1...100 via Position[PrimeQ /@ k[10] /@ Range[100], True] gives {{35}}. $\endgroup$ – evanb May 18 '18 at 7:16
  • 2
    $\begingroup$ Well, we can be sure that $k(n)$ will never be prime for all $n\equiv 1\pmod 3$. Also, we have that $11\nmid k(n)_{n>0}$ $\endgroup$ – Mr Pie May 18 '18 at 7:18
  • $\begingroup$ @evanb You are right, it is $k(35)$ with $667$ digits $\endgroup$ – Peter May 18 '18 at 7:18
  • 1
    $\begingroup$ Actually I am incorrect $-$ it should be that $11\nmid k(n)$ for $n$ odd. And, if $n$ is even, $11\mid k(n)$. $\endgroup$ – Mr Pie May 18 '18 at 7:24
  • 4
    $\begingroup$ Also, an important clarification: what base are these numerals written it? In base 10, 11 is prime, but 11 is prime in bases 2 (which seems the most likely alternative), 4, 6, ... also! $\endgroup$ – evanb May 18 '18 at 7:36
5
$\begingroup$

The formation law is clearly

$$ n_k = 2^k n_{k-1}+1 $$

with $n_1=3$

n0 = 3; For[i = 2, i < 50, i++, n1 = 2^i n0 + 1; If[PrimeQ[n1], Print[n1, " ", IntegerString[n1, 2]]]; n0 = n1]

obtaining

n = 13 -- 1101

n = 271302750695377321080849818469209754627603342031510693802940799730825845099036699701989532948734015220469369753358523432961 -- 11010010001000010000010000001000000010000000010000000001000000000010000000000010000000000001000000000000010000000000000010000000000000001000000000000000010000000000000000010000000000000000001000000000000000000010000000000000000000010000000000000000000001000000000000000000000010000000000000000000000010000000000000000000000001000000000000000000000000010000000000000000000000000010000000000000000000000000001

If the number is considered in basis $10$ then the procedure is analogous. In this case we have $n_1 = 11$ and the recurrence equation is $n_k = 10^k n_{k-1}+1$ giving n = 1101001000100001000001000000100000001000000001000000000100000000001000000000001000000000000100000000000001000000000000001000000000000000100000000000000001000000000000000001000000000000000000100000000000000000001000000000000000000001000000000000000000000100000000000000000000001000000000000000000000001000000000000000000000000100000000000000000000000001000000000000000000000000001000000000000000000000000000100000000000000000000000000001000000000000000000000000000001000000000000000000000000000000100000000000000000000000000000001000000000000000000000000000000001000000000000000000000000000000000100000000000000000000000000000000001000000000000000000000000000000000001 -- 1101001000100001000001000000100000001000000001000000000100000000001000000000001000000000000100000000000001000000000000001000000000000000100000000000000001000000000000000001000000000000000000100000000000000000001000000000000000000001000000000000000000000100000000000000000000001000000000000000000000001000000000000000000000000100000000000000000000000001000000000000000000000000001000000000000000000000000000100000000000000000000000000001000000000000000000000000000001000000000000000000000000000000100000000000000000000000000000001000000000000000000000000000000001000000000000000000000000000000000100000000000000000000000000000000001000000000000000000000000000000000001

$\endgroup$
  • $\begingroup$ Clearly? Well then, you sir have a good eye :) $\endgroup$ – Mr Pie May 18 '18 at 12:24
  • 2
    $\begingroup$ In basis $2$ the multiplication by $2^k$ provides a left shift by $k$ places. $\endgroup$ – Cesareo May 18 '18 at 12:41
  • $\begingroup$ Hah, like a magician revealing their secret! I did not think to consider in base $2$. Good job! I cannot upvote as I have reached my daily voting limit, though, but well done :) $\endgroup$ – Mr Pie May 18 '18 at 12:45
  • $\begingroup$ Is it clear that the numbers in the OP are given in base 2? It doesn't seem to say so anywhere. $\endgroup$ – Henning Makholm May 21 '18 at 23:53
  • $\begingroup$ The procedure is analogous. In this case we have $n_1 = 11$ and the recurrence equation is $n_k = 10^k n_{k-1}+1$. This case was attached to the answer. Thanks. $\endgroup$ – Cesareo May 22 '18 at 0:06
2
$\begingroup$

This is not really an answer but might be of some help.


According to the "Divisibility by $3$ Rule," if $n\equiv 1\pmod 3$ then $k(n)$ will not be prime as it will be divisible by $3$. And, it will be divisible by $11$ if $n$ is even.

That leaves only all the odd numbers for $n$ (since the congruence above is also even).

$\endgroup$
  • 2
    $\begingroup$ I think you mean that it leaves the congruence classes $3,5 \pmod 6$. For example, $1$ is congruent to $1$ mod 3 but is not even. $\endgroup$ – Jalex Stark May 18 '18 at 8:28
  • $\begingroup$ @JalexStark yes I probably did. I did not think of that :) $\endgroup$ – Mr Pie May 18 '18 at 12:21
2
$\begingroup$

Here is a Mathematica search to answer your question:

b[1] = 1;
b[2] = 2;
b[n_] := b[n] = b[n - 1] + n - 1;
list[t_] := b /@ Range[t];
Reap@Do[a = ReplacePart[Array[0 &, b[t]], Transpose[{list[t]}] -> 1]; 
  c = FromDigits[a, 2]; If[PrimeQ[c], Sow@c], {t, 100}]

which yields

{Null, {{3, 13, 2713027506953773210808498184692097546276033420315106938029407997308\ 25845099036699701989532948734015220469369753358523432961}}}

$\endgroup$
  • $\begingroup$ can you elaborate on the format of your output for those in the math.SE community who are not fluent in Mathematica? $\endgroup$ – Alexander Gruber May 21 '18 at 23:41
  • $\begingroup$ Sorry... This question is first asked in mathematica community,When i answered it. $\endgroup$ – xin pei May 22 '18 at 0:44
  • $\begingroup$ Yeah, just hoping you could explain so the answer will fit in its new home $\endgroup$ – Alexander Gruber May 22 '18 at 5:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy