1

Find the largest positive integer $n<100$, such that there exists an arithmetic progression of positive integers $a_1,a_2,...,a_n$ with the following properties.

  • $1)$ All numbers $a_2,a_3,...,a_{n−1}$ are powers of positive integers, that is numbers of the form $j^k$, where $j \geq 1$ and $k \geq 2$ are integers.

  • $2)$ The numbers $a_1$ and $a_n$ are not powers of positive integers.

MJD
  • 65,394
  • 39
  • 298
  • 580
KLG
  • 19
  • 2
    This question has been reposted from [Brilliant.org](url: https://brilliant.org/i/ppYFuz/) - Calvin Lin, Brilliant Challenge master. – Calvin Lin Aug 07 '13 at 21:21
  • We can obtain arbitrarily long arithmetic progressions of perfect powers: It is always possible to prolong by at least one in at least one direction. I don't see why $n=99$ should not be achievable (i.e., why prolonging a slightly shorter sequence should always jump across the length of 99). – Hagen von Eitzen May 12 '16 at 06:50
  • @HagenvonEitzen: "It is always possible to prolong by at least one": why?? –  May 12 '16 at 06:57

2 Answers2

0

Partial solution. First observe that there are arbitrary long arithmetic sequences of perfect powers. Indeed, assume for some $n\ge1$ that $a_k=mk+d$ (with $m,d\in\Bbb N$) is an arithmetic sequence where for $1\le k\le n$, $a_k$ is a perfect power (say, $a_k=b_k^{c_k}$ with $c_k\ge 2$). Then we can find an arithmetic sequence $a_k'=m'k+d'$ such that $a_k'$ is a perfect power for $1\le k\le n+1$. To do so we just let $m'=a_{n+1}^rm$ and $d'=a_{n+1}^rd$ where $r=\operatorname{lcm}(c_1,\ldots,c_n)$. That makes $a_k'=a_ka_{n+1}^r=(b_ka_{n+1}^{r/c_k})^{c_k}$ a perfect power for $1\le k\le n$, and of course also $a_{n+1}'=a_n^{r+1}$ is a perfect power. In particular, we can pick the exponents $c_k'=c_k$ for $1\le k\le n$ and $c_{n+1}'=\operatorname{lcm}(c_1,\ldots,c_n)+1$.

However, regarding the OP's question we have to watch out if $a_0'$ and/or $a_{n+2}'$ "accidentally" become perfect powers.

0

From a quick search, this question appears to still be open. Bounds on $n$ exist for some restricted sets of powers $k$, and it is known that the number of progressions of length $n$ for $n\geq 6$ with relatively coprime terms (if any) is finite.

See for instance:

Roby5
  • 4,287
user7530
  • 49,280
  • This question has been reposted from [Brilliant.org](url: https://brilliant.org/i/ppYFuz/) - Calvin Lin, Brilliant Challenge master. – Calvin Lin Aug 07 '13 at 21:25
  • @CalvinLin Whoah what? I'm assuming Bruin et al missed a significantly simpler approach to their problem? – user7530 Aug 07 '13 at 21:32
  • Did you see the second condition? The first and last numbers are not powers. – Calvin Lin Aug 07 '13 at 21:33
  • In your first paper, the powers must be distinct. In your second paper, the powers must be the same. Neither of these hold in the question. – Calvin Lin Aug 07 '13 at 21:35
  • If it helps, the ideas involved are pretty simple, but it has a very low correct rate. about 10% of the high level users have gotten it right so far. – Calvin Lin Aug 07 '13 at 21:39
  • @CalvinLin Are you sure in the first paper the exponents must be distinct? I must have missed that... – user7530 Aug 07 '13 at 21:41
  • Oh sorry, that's not what unlike means. Looking at the abstract, they use the condition that the exponents are bounded ($2 \leq l_k \leq L$), which is not given in this question. Basically, the idea is to take multiply to a larger exponent to allow you to add more terms. – Calvin Lin Aug 07 '13 at 21:45
  • @CalvinLin Nice website, and nice problem you made, but when I registered, I was not able to answer the problem. Is it a paying website? – Fujoyaki Sep 18 '14 at 15:52
  • @Fujoyaki Most of the site is free, and there are a lot of similar problems. For certain problems (like this), which we spent significant effort to develop, they are currently placed behind a paywall. – Calvin Lin Sep 18 '14 at 21:58