1, 4, 8, 9, 16, 25, 27, 32

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

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

2) The numbers a 1 a_1 and a n a_{n} are not powers of positive integers.


The answer is 99.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

C Lim
Aug 4, 2013

Take the arithmetic progression 101 k , 102 k , , 199 k 101k, 102k, \ldots, 199k , which has 99 terms. We wish to find a k such that 102 k , 102 k , , 198 k 102k, 102k, \ldots, 198k are powers of positive integers, while 101k and 199k aren't. To be specific, we let S denote the set of primes < 198 and excluding 101, then pick k of the form:

k = p S p m p = 2 m 2 × 3 m 3 × 5 m 5 × k =\prod_{p \in S} p^{m_p} = 2^{m_2} \times 3^{m_3} \times 5^{m_5} \times\ldots

for suitable non-negative integers m 2 , m 3 , m 5 , m 7 , m_2, m_3, m_5, m_7, \ldots .

Pick any distinct primes q 102 , q 103 , , q 198 q_{102}, q_{103}, \ldots, q_{198} ; for every prime p S p\in S solve the following congruences:

m p + ν ( 102 , p ) 0 ( m o d q 102 ) , m p + ν ( 103 , p ) 0 ( m o d q 103 ) , m p + ν ( 198 , p ) 0 ( m o d q 198 ) . \begin{aligned} m_p + \nu(102, p) &\equiv 0 \pmod {q_{102}}, \\ m_p + \nu(103, p) &\equiv 0 \pmod {q_{103}},\\ &\vdots \\ m_p + \nu(198, p) &\equiv 0 \pmod {q_{198}}. \end{aligned}

Here, ν ( n , p ) \nu(n, p) is the largest j such that p j n p^j | n . Note that since all prime factors of 102 , , 198 102, \ldots, 198 lie in S, we have:

102 = p S p ν ( 102 , p ) , 103 = p S p ν ( 103 , p ) , , 198 = p S p ν ( 198 , p ) . 102 = \prod_{p\in S} p^{\nu(102, p)}, \ 103 = \prod_{p\in S} p^{\nu(103, p)}, \ \ldots, \ 198 = \prod_{p\in S} p^{\nu(198, p)}.

By Chinese Remainder Theorem, there's a solution for m p m_p in the above congruences. Since k = p S p m p k =\prod_{p \in S} p^{m_p} , we see that:

102 k = p S p ν ( 102 , p ) p m p = p S p m p + ν ( 102 , p ) 102k = \prod_{p\in S} p^{\nu(102, p)} p^{m_p} = \prod_{p\in S} p^{m_p + \nu(102, p)}

is a q 102 q_{102} -th power, and likewise for each of i = 103 , , 198 i = 103, \ldots, 198 , the multiple i k ik is a q i q_i -th power. Thus, we have a sequence which satisfies (1).

This sequence clearly satisfies (2) as well since 101 and 199 are prime and k is not a multiple of 101 or 199.

Moderator note:

This solution seems to use the fact that 101 is a prime. Is this a necessary condition? What happens if the condition was changed to n < 200 n < 200 , where 201 201 is not a prime?

For n < 200, replace 101 and 199 with m and m+198 such that both are prime. E.g. 13, 211.

C Lim - 7 years, 10 months ago

Log in to reply

For n < 200, replace 101 and 199 with m and m+198 such that both are prime. E.g. 13, 211.

Would that work? I thought part of the idea with 101 is the fact that 102,…,198 aren't multiples of it.

Peter Byers - 7 years, 10 months ago

Log in to reply

Indeed. For this construction, the important aspect is that we have two primes p 1 > p 2 > n p_1 > p_2 > n and p 1 p 2 = n 1 p_1 - p_2 = n-1 .

Clearly we must have n n odd. Is this a sufficient condition?

How about the case of n n even? I do not know if there exists a sequence of 98 terms which satisfy the conditions. My guess is yes, but I have no proof of the fact.

Calvin Lin Staff - 7 years, 10 months ago

Log in to reply

@Calvin Lin

How about the case of n even? I do not know if there exists a sequence of 98 terms which satisfy the conditions. My guess is yes, but I have no proof of the fact.

For a sequence of 98 terms, CL's same basic method could be used to find a k-value such that 227k, 229k, ... 419k, 421k is an appropriate sequence.

Peter Byers - 7 years, 10 months ago

Log in to reply

@Peter Byers Great modification! Now I'm kicking myself for not thinking of it.

Note that is it still an open conjecture if for any positive integer n n , there exist 2 primes p p and q q such that p + 2 n = q p + 2n = q (i.e. the 2 primes that we need). You can see A020483 of OEIS for more details.

Calvin Lin Staff - 7 years, 10 months ago

You're right of course. Sorry, I have to pick large enough primes, like 211, 409.

C Lim - 7 years, 10 months ago

This looks like a good research topic. What subjects do you think will be needed for this? Number theory perhaps?

Ching Z - 7 years, 10 months ago

What BASIC maths skills do i need to begin to understand this ? If I were to start learning this stuff from scratch, where do I need to begin ? I do have high school level mathematics but this is beyond anything I ever learned before .

Simon Cochrane - 4 years, 4 months ago

What a hard problem! If I may ask a question, why must the progression be of the form 101 k , 102 k , . . . 199 k 101k, 102k, ... 199k ? Why can't it be k , 2 k , 3 k . . . k, 2k, 3k ... or m , m + k , m + 2 k . . . m, m+k, m+2k ... ?

Zhang Ning - 7 years, 10 months ago

Log in to reply

He chose the sequence because it works. See the above discussion for what are the crucial aspects of the sequence that works.

Here is a simpler way of understanding the proof, which uses very similar idea. Starting with the sequence 101 , 102 , , 199 101, 102, \ldots , 199 (where once again the important criterion is that both 101 and 199 are prime), we want to inductively make each term (from the second) a power.

Base step: Starting with the second, we multiply the sequence by 102, which makes the second term 10 2 2 102^2 , which is a power.

Induction step: Let the terms a 2 , a 3 , a k a_2, a_3, \ldots a_k be powers. Let the LCM of the exponents be M M . Then, multiplying the entire sequence by a k + 1 M + 1 a_{k+1}^{M+1} makes all the terms a 2 , a k + 1 a_2, \ldots a_{k+1} a power term.

Hence, it is possible to make a 2 , a 3 , a 98 a_2, a_3, \ldots a_{98} all powers. Now, we check that a 1 a_1 (respectively a 99 a_{99} ) is not a power. This is because it is a multiple of 101 (resp 199), but not 10 1 2 101^2 (resp 19 9 2 199^2 ).

Calvin Lin Staff - 7 years, 10 months ago

Log in to reply

Dang. I had the exact idea that if you have a small sequence that's all powers then multiplying it the next item by a M + 1 k + 1 ] a^{\frac{M+1}{k+1}}|] gives you a longer sequence of all powers. But when I tried it out on a numeric example I forgot to start with a sequence of powers and it didn't work so I moved onto other ideas.

Matt McNabb - 7 years, 10 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...