Find the largest positive integer n < 1 0 0 , 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 ≥ 1 and k ≥ 2 are integers.
2) The numbers a 1 and a n are not powers of positive integers.
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.
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 < 2 0 0 , where 2 0 1 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.
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.
Log in to reply
Indeed. For this construction, the important aspect is that we have two primes p 1 > p 2 > n and p 1 − p 2 = n − 1 .
Clearly we must have n odd. Is this a sufficient condition?
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.
Log in to reply
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.
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 , there exist 2 primes p and q such that p + 2 n = q (i.e. the 2 primes that we need). You can see A020483 of OEIS for more details.
You're right of course. Sorry, I have to pick large enough primes, like 211, 409.
This looks like a good research topic. What subjects do you think will be needed for this? Number theory perhaps?
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 .
What a hard problem! If I may ask a question, why must the progression be of the form 1 0 1 k , 1 0 2 k , . . . 1 9 9 k ? Why can't it be k , 2 k , 3 k . . . or m , m + k , m + 2 k . . . ?
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 1 0 1 , 1 0 2 , … , 1 9 9 (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 1 0 2 2 , which is a power.
Induction step: Let the terms a 2 , a 3 , … a k be powers. Let the LCM of the exponents be M . Then, multiplying the entire sequence by a k + 1 M + 1 makes all the terms a 2 , … a k + 1 a power term.
Hence, it is possible to make a 2 , a 3 , … a 9 8 all powers. Now, we check that a 1 (respectively a 9 9 ) is not a power. This is because it is a multiple of 101 (resp 199), but not 1 0 1 2 (resp 1 9 9 2 ).
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 k + 1 M + 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.
Problem Loading...
Note Loading...
Set Loading...
Take the arithmetic progression 1 0 1 k , 1 0 2 k , … , 1 9 9 k , which has 99 terms. We wish to find a k such that 1 0 2 k , 1 0 2 k , … , 1 9 8 k 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 × …
for suitable non-negative integers m 2 , m 3 , m 5 , m 7 , … .
Pick any distinct primes q 1 0 2 , q 1 0 3 , … , q 1 9 8 ; for every prime p ∈ S solve the following congruences:
m p + ν ( 1 0 2 , p ) m p + ν ( 1 0 3 , p ) m p + ν ( 1 9 8 , p ) ≡ 0 ( m o d q 1 0 2 ) , ≡ 0 ( m o d q 1 0 3 ) , ⋮ ≡ 0 ( m o d q 1 9 8 ) .
Here, ν ( n , p ) is the largest j such that p j ∣ n . Note that since all prime factors of 1 0 2 , … , 1 9 8 lie in S, we have:
1 0 2 = p ∈ S ∏ p ν ( 1 0 2 , p ) , 1 0 3 = p ∈ S ∏ p ν ( 1 0 3 , p ) , … , 1 9 8 = p ∈ S ∏ p ν ( 1 9 8 , p ) .
By Chinese Remainder Theorem, there's a solution for m p in the above congruences. Since k = ∏ p ∈ S p m p , we see that:
1 0 2 k = p ∈ S ∏ p ν ( 1 0 2 , p ) p m p = p ∈ S ∏ p m p + ν ( 1 0 2 , p )
is a q 1 0 2 -th power, and likewise for each of i = 1 0 3 , … , 1 9 8 , the multiple i k is a 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.