5

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 (?))

Community
  • 1
  • 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}}. – evanb May 18 '18 at 07:16
  • 2
    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}$ – Mr Pie May 18 '18 at 07:18
  • @evanb You are right, it is $k(35)$ with $667$ digits – Peter May 18 '18 at 07:18
  • 1
    Actually I am incorrect $-$ it should be that $11\nmid k(n)$ for $n$ odd. And, if $n$ is even, $11\mid k(n)$. – Mr Pie May 18 '18 at 07:24
  • @HenrikSchumacher But $k(35)$ is prime, check which numbers are calculated by your program. – Peter May 18 '18 at 07:27
  • @Peter. Yes, you are right. Code should have been a = FoldList[#1 10^#2 + 1 &, 1, Range[122]][[ 3 ;;]]; Or @@ (PrimeQ /@ a) (there was a superfluous 1 in the beginning). – Henrik Schumacher May 18 '18 at 07:32
  • 4
    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! – evanb May 18 '18 at 07:36
  • Upto $n=199$, there is no further prime. – Peter May 18 '18 at 07:37
  • @evanb True, but this must be mentioned in the question in this case. Without any additional context, a decimal expansion is the most reasonable guess. And in the binary case, $1101$ is prime – Peter May 18 '18 at 07:38
  • With PARI/GP I could prove the primality of $k(35)$. If another prime exists, it must have more than $20\ 000$ digits. – Peter May 18 '18 at 07:46
  • The problem is base dependent. Some posted answers interpret it as base 2! – Oscar Lanzi May 18 '18 at 09:11

3 Answers3

5

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

Cesareo
  • 33,252
  • Clearly? Well then, you sir have a good eye :) – Mr Pie May 18 '18 at 12:24
  • 2
    In basis $2$ the multiplication by $2^k$ provides a left shift by $k$ places. – Cesareo May 18 '18 at 12:41
  • 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 :) – Mr Pie May 18 '18 at 12:45
  • Is it clear that the numbers in the OP are given in base 2? It doesn't seem to say so anywhere. – hmakholm left over Monica May 21 '18 at 23:53
  • 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. – Cesareo May 22 '18 at 00:06
2

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).

Mr Pie
  • 9,459
2

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}}}

Alexander Gruber
  • 26,963
XinBae
  • 129