[seqfan] Re: Numbers not sums of perfect powers

franktaw at netscape.net franktaw at netscape.net
Thu Apr 15 06:38:08 CEST 2010

Ah, k-th powers minus 1. That's what I missed.

Certainly the k-th powers minus 1, collectively, are relatively prime. 
No prime p can divide all of them; it does not divide p^k-1.

Let gcd(a_1,...,a_n) = g, and take b relatively  prime to g. Then 
gcd(a_1/g,...,a_n/g) = 1, and by induction every sufficiently large 
number can be expressed as a sum of them. This means that every 
sufficiently large multiple of g can be expressed as a sum of 
a_1,...,a_n; in particular, we can find one that is relatively prime to 
b. This means that every sufficiently large number is a sum of 
a_1,...,a_n,b, and so we are done by induction.

(Note: the above argument relies on the fact that any relatively prime 
set of integers contains a relatively prime finite subset. This is left 
as an exercise for the reader.)

  don't know of any efficient way to determine the maximum number not 
obtainable for a set of 3 or more relatively prime numbers.

(Actually, one can find two k-th powers minus 1 that are relatively 
prime: 2^k-1, and (2^k-1)^k-1. This will produce, in general, an 
excessively large upper bound on the complement set.)

Franklin T. Adams-Watters

-----Original Message-----
From: Benoît Jubin <benoit.jubin at gmail.com>

On Wed, Apr 14, 2010 at 7:31 PM,  <franktaw at netscape.net> wrote:
> 2^k and 3^k are relatively prime. The set of numbers that cannot be
> expressed as a sum using any set of relatively prime numbers is 

Yes, this was in my original post:
For analogues of the third sequence, we have:
The numbers which are not the sum of k^th powers larger than one are
exactly those in [1,6^k-3^k-2^k] but not of the form
2^k.a+3^k.b+5^k.c.  This relies on the following fact: if m and n are
relatively prime, then the largest number which is not a linear
combination of m and n with positive integer coefficients is mn-m-n.

Is there an analogous result for relatively prime integers {m_i} ?

You answered positively to my last question: do you know a simple
expression for the largest number which cannot be written in this way?
 For the numbers which are not sums of kth-powers-minus-1, we have to
show that the latter are relatively prime, and it would be even better
to find a effective bound...


> Franklin T. Adams-Watters
> -----Original Message-----
> From: Benoît Jubin <benoit.jubin at gmail.com>
> ..  And I'm still interested in
> finiteness for the general case (k^th powers).
> _______________________________________________
> Seqfan Mailing list - http://list.seqfan.eu/


Seqfan Mailing list - http://list.seqfan.eu/


More information about the SeqFan mailing list