[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
finite.
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...
Thanks,
Benoit
>
> 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