15
$\begingroup$

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

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

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.

$\endgroup$
  • $\begingroup$ No wonder, I did not find any primes. Thanks. $\endgroup$ – Peter Jan 2 '14 at 17:12
  • 2
    $\begingroup$ 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$. $\endgroup$ – Hagen von Eitzen Jan 2 '14 at 17:12
  • $\begingroup$ Good observation! I saw the other factor $49000\cdots07000\cdots01$ but the $23$, $233$ etc was easier to analyze. Thanks $\endgroup$ – user44197 Jan 2 '14 at 17:17
  • $\begingroup$ You might be interested to know that this generalizes widely - see my answer. $\endgroup$ – Bill Dubuque Jan 3 '14 at 1:04
  • $\begingroup$ Well done! Perhaps you might be interested in this problem as well ? $\endgroup$ – Lucian Jan 3 '14 at 2:01
14
$\begingroup$

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

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

The expression is congruent of 3.

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

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.