A prime of the form $38111111\ldots$

Let $z(n)$ denote the number given by $38$ followed by $n 1$'s.

What is the least number $n$, such that $z(n)$ is prime ?

With brute force, I checked up to $7000$ digits and did not find a prime.

Can anything useful be said about the possible prime factors which could help to accelerate the search ?

For those, who prefer formulas

$$z(n)=\frac{343*10^n-1}{9}$$

• Well you know $n\neq1\mod 3$ by the easy 'sum up the digits' check. – Ian Coley Jan 2 '14 at 16:44
• "I checked up to $7000$ digits" - So, you mean you checked numbers having $7000$ digits (in decimal) for primality?? How have you checked? – pushpen.paul Jul 22 '14 at 20:33
• with the adleman-pomerance-rumely-test – Peter Jul 22 '14 at 21:02
• – punctured dusk Aug 5 '15 at 11:42
• This appeared on the Benelux Mathematical Olympiad (BxMO) 2015, see bxmo.org/results/2015, so I'm tagging this as contest-math. – punctured dusk Aug 5 '15 at 11:43

There are three cases:

If $n = 3 k + 1$ then the number is clearly divisible by 3.

If $n = 3k +2$ then using the fact that $37$ divides $111$, we can see that 37 divides the number.

If $n=3k$, it gets trickier. You can show that the number is divisible by $\frac{7\, 10^k-1}{3}$, i.e numbers of the form $23$, $233$, $2333$ and so on.

• No wonder, I did not find any primes. Thanks. – Peter Jan 2 '14 at 17:12
• To elaborate on the last case: $9z(3k)=(7\cdot 10^k-1)(49\cdot 100^k+7\cdot 10^k+1 )$. If $z(3k)$ is prime, at least one of the two factors must be $\le 9$. – Hagen von Eitzen Jan 2 '14 at 17:12
• Good observation! I saw the other factor $49000\cdots07000\cdots01$ but the $23$, $233$ etc was easier to analyze. Thanks – user44197 Jan 2 '14 at 17:17
• You might be interested to know that this generalizes widely - see my answer. – Bill Dubuque Jan 3 '14 at 1:04
• Well done! Perhaps you might be interested in this problem as well ? – Lucian Jan 3 '14 at 2:01

It is true more generally that the elements of such sequences are all composite (except possible for the first few values), i.e. $\,f_n$ is composite for all $\,n>c,\,$ for some $\,c\,$ not depending on $\,n.$

Theorem $\ \ \ f_n = a^3 b^n-1\,$ is composite for all $\,n> c\ \$ if $\ \ a\ge3,\ b\ge2,\ \$ and

both gcds $\ \color{#0a0}{d_1} = (\color{#0a0}{a^3\!-b^2},b^3\!-1),\$ $\,\color{#c00}{d_2}=(\color{#c00}{a^3\!-b},b^3\!-1)\,$ are nontrivial, i.e. $\,d_i> 1.$

Proof $\ \,$ By cases on $\,n\ {\rm mod}\ 3.\,$ The first two cases below show that $\,f_n\,$ has a factor $\,d_i.$

$\ \ n=3k\!-\!2\!:\ {\rm mod}\,\ \color{#0a0}{d_1:\ a^3\equiv b^2},\, b^3\equiv 1\,\Rightarrow\, a^3b^n\! = \color{#0a0}{a^3} b^{3k-2} \equiv (b^3)^k \equiv 1\,\Rightarrow\, f_n \equiv 0$

$\ \ n=3k\!-\!1\!:\ {\rm mod}\,\ \color{#c00}{d_2\!:\ a^3\equiv b},\,\ \ b^3\equiv 1\,\Rightarrow\, a^3b^n\!= \color{#c00}{a^3} b^{3k-1} \equiv (b^3)^k \equiv 1\, \Rightarrow\, f_n \equiv 0$

$\ \ n=3k\!:\ a^3b^{3k}\!-1 = (ab^k)^3\!-1 = (e-1)(e^2\!+e+1),\ \, e = ab^k \ge a \ge 3\,\Rightarrow\,$ both factors $> 1$.

$\,d_i$ is independent of $\,n\,$ and $\,f_n$ is increasing, so $\,d_i$ is eventually a proper factor of $\,f_n$ once $\,f_n \ge \max d_i$. In the remaining case $(n = 3k)$ we see $\,e-1\,$ is a proper factor of $\,f_n.$ $\ \ \,$ QED

The OP arises from the special case $\,a,b = 7,10,\,$ so $\, (a^3-b,b^3-1) = (333,999)=333=9\cdot 37,\,$
and $\,(a^3-b^2,b^3-1) = (243,999)=9\cdot 3.\,$ Because $\,(d_1,d_2) = 9\,$ is a proper factor of $\,d_1,d_2,f_{3n},\,$ it follows that $\,z_n = f_{n}/9\,$ also has all composite values, which is the OP.

An analogous theorem holds for $\,f_n = a^k b^n\! - 1\,$ using gcds $\ (a^k\!-b^i,b^k\!-1),\,\ i =1,\ldots,k-1.$

• This is so cool! Bravo! – user44197 Jan 3 '14 at 15:10
• The final $b^3$ is missing a $-1$. I can't make an edit that small. – NovaDenizen Jan 5 '14 at 12:34
• @NovaDenizen Typo fixed, thanks! – Bill Dubuque Jan 5 '14 at 16:00

The expression is congruent of 3.

$343 \equiv 1 \pmod 3$ and 3|$10^n - 1$.