Sum of unique prime squares?
Toni Lassila
(including negative terms) of only squares of primes and one so that
no term is repeated twice?
16 = 25 - 9
36 = 49 - 9 - 4
64 = 81 - 49 - 25 - 9 + 4 - 1
100 = 81 + 49 - 25 - 4 - 1
144 = 81 + 49 + 9 + 4 + 1
196 = 169 + 49 - 25 + 4 - 1
...
Hugo Pfoertner
>
> Is there a theorem that states any square can be written as a sum
> (including negative terms) of only squares of primes and one so that
> no term is repeated twice?
>
> 16 = 25 - 9
> 36 = 49 - 9 - 4
> 64 = 81 - 49 - 25 - 9 + 4 - 1
square of a prime?
[...]
Hugo
Toni Lassila
Replace with:
64 = 49 + 25 - 9 - 1
100 = 121 - 25 + 4
Robert Israel
Toni Lassila <to...@nukespam.org> wrote:
>Is there a theorem that states any square can be written as a sum
>(including negative terms) of only squares of primes and one so that
>no term is repeated twice?
>16 = 25 - 9
>36 = 49 - 9 - 4
>64 = 81 - 49 - 25 - 9 + 4 - 1
I don't think you need the 1.
64 = 13^2 - 11^2 + 5^2 - 3^2
81 = 11^2 - 7^2 + 3^2
100 = 11^2 - 5^2 + 2^2
144 = 13^2 - 5^2
196 = 17^2 - 11^2 + 7^2 - 5^2 + 2^2
225 = 13^2 + 11^2 - 7^2 - 5^2 + 3^2
256 = 13^2 + 7^2 + 5^2 + 3^2 + 2^2
Actually it seems that all positive integers at least up to 1000 can be
written as differences of sums of squares of distinct primes. I wouldn't
be surprised if this was true for all positive integers, but I don't
immediately see a way to prove it.
Robert Israel isr...@math.ubc.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia
Vancouver, BC, Canada V6T 1Z2
Toni Lassila
>In article <433bpvo7387dkpvg0...@no.spam>,
>Toni Lassila <to...@nukespam.org> wrote:
>>Is there a theorem that states any square can be written as a sum
>>(including negative terms) of only squares of primes and one so that
>>no term is repeated twice?
>
>I don't think you need the 1.
>
> 64 = 13^2 - 11^2 + 5^2 - 3^2
> 81 = 11^2 - 7^2 + 3^2
> 100 = 11^2 - 5^2 + 2^2
> 144 = 13^2 - 5^2
> 196 = 17^2 - 11^2 + 7^2 - 5^2 + 2^2
> 225 = 13^2 + 11^2 - 7^2 - 5^2 + 3^2
> 256 = 13^2 + 7^2 + 5^2 + 3^2 + 2^2
>
>Actually it seems that all positive integers at least up to 1000 can be
>written as differences of sums of squares of distinct primes. I wouldn't
>be surprised if this was true for all positive integers, but I don't
>immediately see a way to prove it.
Was this result derived from another result or brute-forced?
Another related question is, is it possible to express the square of
any prime as differences of sums of other squares of distinct primes?
It's certainly possible if one includes 1, but what about without it?
Jyrki Lahtonen
This surely look plausible. A possibly related result due to
Sprague states that any integer larger than 128 can be expressed
as a sum of distinct squares. Using only squares of primes will
make things a little bit more difficult, but there are plenty of
primes around, so one might be able to prove the same result
using squares of primes only, and for a limit larger than 128.
Then you could simply run a computer check for the (finite set of)
excluded values.
Look up e.g. Joe Roberts, "Elementary Number Theory - a Problem
Oriented Approach", ch. XI for ideas leading to Sprague's result.
I don't know, if such a simple approach will work in this case.
Cheers,
Jyrki Lahtonen, Turku, Finland
Martin Cohen
My guess is that the primality is a red herring. What matters is that
the sequence has a growth rate that is not too fast and is moderately
regular.
Martin Cohen
Hugo Pfoertner
A related question:
I wrote a little program checking how many terms are needed to represent
n by the minimum number of distinct squares of primes.
The program only searched for a maximum of 4 terms. The results for
n<=20:
n Terms Primes in sum
0 4 7 -11 -17 19 (means 0 = 7^2 -11^2 -17^2 +19^2)
1 3 7 11 -13
2 4 5 7 17 -19
3 4 2 -7 -11 13
4 1 2
5 2 3 -2
6 ?
7 ?
8 4 3 -7 -11 13
9 1 3
10 4 3 7 11 -13
11 4 -2 -3 -5 7
12 3 -2 -3 5
13 2 3 2
14 4 -3 -5 -11 13
15 3 -3 -5 7
16 2 5 -3
17 ?
18 ?
19 4 2 -3 -5 7
20 3 2 -3 5
List for n<=200 at
http://www.randomwalk.de/scimath/sumpsq.txt
Can we always find a solution with 5 terms for those n marked with "?".
The list of n where I didn't find a solution with <=4 tems continues:
6,7,17,18,31,41,42,55,60,66,84,89,90,102,103,113,114,127,132,138,162,
180, >200
Hugo Pfoertner
Hugo Pfoertner
> 6,7,17,18,31,41,42,55,60,66,84,89,90,102,103,113,114,127,132,138,162,
> 180, >200
>
> Hugo Pfoertner
In the meantime Edwin Clark confirmed that 5 terms are suficient. He
writes:
<<
I find that just using the first 12 primes all numbers from 1 to 1123
can be written in the form sum(s[i]*p[i]^2, i=1..k) where s[i] is 1 or
-1,
the primes p[i] are distinct and k <=5
>>
Hugo
Bill Dubuque
>
> Is there a theorem that states any square can be written as a sum
> (including negative terms) of only squares of primes and one so that
In fact every integer > 17163 is representable as a sum of distinct
squares of primes, see 54:7373 below. Also below are reviews of some
papers on this and related topics (by no means complete).
-Bill Dubuque
------------------------------------------------------------------------------
10:283d 10.0X
Sprague, R. Uber Zerlegungen in ungleiche Quadratzahlen.
Math. Z. 51 (1948). 289--290.
------------------------------------------------------------------------------
The author shows in a quite elementary way that every positive integer than
128 is the sum of distinct squares. The proof depends on showing with a small
list of such representations that the integers between 129 and 256 are sums of
distinct squares not exceeding 100. There are exactly 32 integers
2,3,6,7,8,11,...,128 which are not the sum of distinct squares.
Reviewed by D. H. Lehmer
------------------------------------------------------------------------------
10:514h 10.0X
Sprague, R.
Uber Zerlegungen in n-te Potenzen mit lauter verschiedenen Grundzahlen.
Math. Z. 51 (1948). 466--468.
------------------------------------------------------------------------------
Let P_n(k) denote the number of partitions of k into distinct parts taken
from 1, 2^n, 3^n, ... . The author proves that there is a positive integer
N_n depending only on n such that P_n(k) > 0 for all k > N_n . In other
words, for each n there are only a finite number of integers which are not
the sums of distinct n th powers. This result for n = 2 has already been
obtained by the author [same vol., 289-290 (1948); these Rev. 10:283].
The method of proof is an application of the Tarry-Escott problem.
Reviewed by D. H. Lehmer
------------------------------------------------------------------------------
11:646a 10.0X
Richert, Hans-Egon
Uber Zerlegungen in paarweise verschiedene Zahlen.
Norsk Mat. Tidsskr. 31, (1949). 120--122.
------------------------------------------------------------------------------
The author generalizes some theorems by Sprague [Math. Z. 51, 289-290, 466-468
(1948); these Rev. 10:283,514] and himself [Math. Z. 52, 342-343 (1949); these
Rev. 11:502] about the partition of numbers into distinct parts. The general
theorem may be stated as follows. Let M be an infinite set of positive
integers m_1, m_2, ... , with the following properties: (A) there exist
integers k >= 2, N >= 0, S > 0, such that each integer x, with N < x <= N+S,
may be partitioned into distinct parts taken from the first k members of M;
(B) S >= m_{k+1}; (C) 2m_i >= m_{i+1} for i>k. Then every integer greater
than N may be partitioned into distinct parts taken from M. The proof is
quite straightforward. As an example, if M is the set of triangular numbers
then (A), (B) and (C) are satisfied with k=8, N=33, S=45. Hence every integer
except 2,5,8,12,23,33 is the sum of distinct triangular numbers.
Reviewed by D. H. Lehmer
------------------------------------------------------------------------------
22:26 10.00
Birch, B. J.
Note on a problem of Erdos.
Proc. Cambridge Philos. Soc. 55 1959 370--373.
------------------------------------------------------------------------------
The following result is proved: given any positive coprime integers p, q,
there exists a number N(p,q) such that every n > N(p,q) is expressible as
a sum of the form n = p^a1 q^b1 + p^a2 q^b2 +..., where the (ai,bi) are
distinct pairs of positive integers. The proof is self-contained and
elementary, but far from trivial.
Reviewed by L. Mirsky
------------------------------------------------------------------------------
24:A103 10.46 (10.48)
Cassels, J. W. S.
On the representation of integers as the sums of distinct summands taken
from a fixed set.
Acta Sci. Math. Szeged 21 1960 111--124.
------------------------------------------------------------------------------
Let A be a sequence of distinct positive integers a_1 < a_2 < a_3 <... ;
A(n) denotes the number of members of A less than or equal to n. For a real
number x, write |x| for the difference between x and the nearest integer. The
main theorem proved is that if (1) lim[A(2n)-A(n)]/log(log n) = oo, and if
(2) sum|a_n t|^2 = oo for every real t in 0<t<1, then every sufficiently
large integer is the sum of distinct elements of A. The author proves his
theorem by an original adaptation of the Hardy-Littlewood circle method.
An outstanding feature of this result is the weakness of the growth condition
(1); this gives the theorem great generality. Earlier work by Roth and Szekeres
[Quart. J. Math. Oxford Ser. (2) 5 (1954), 241-259; MR 16:797] gave estimates
for the number of partitions of a large integer n as the sum of distinct
elements of A, but only at the cost of much stronger conditions corresponding
to (1) and (2).
Erdos and others had conjectured that the conclusion of the theorem would
remain true if condition (2) were replaced by the condition that the sequence
A contains infinitely many numbers in every arithmetic progression. As his
second theorem, the author shows that this is not so: for every e>0 there is
a sequence C such that (i) c_n = O(n^{2+e}), (ii) C contains infinitely
many elements in every arithmetic progression, but (iii) the set of integers
which are sums of distinct elements of C has density less than e. In fact,
a suitable sequence C may be constructed from the Fibonacci numbers.
Reviewed by B. J. Birch
------------------------------------------------------------------------------
26:2387 10.45
Erdos, P.
On the representation of large integers as sums of distinct summands taken
from a fixed set.
Acta Arith. 7 1961/1962 345--354.
------------------------------------------------------------------------------
Let {a_i} be an infinite sequence of positive integers such that every
arithmetic progression contains at least one integer which is the sum of
distinct a's; A(n) is the number of a's not exceeding n . The author
proves by elementary means that if A(n) increases faster than
n^{(sqrt(5)-1)/2}, then every large enough integer is a sum of distinct a's.
This appears much weaker than a result recently obtained by the circle method
by Cassels [Acta Sci. Math. (Szeged) 21 (1960), 111-124; MR 24:A103]; but the
author dispenses with a regularity condition essential to Cassels' argument,
and in fact the theorem as stated becomes false if the exponent 1/2(sqrt(5)-1)
is reduced to 1/2-\eps; it may well be possible to reduce the exponent to
1/2+\eps by improving the method of this paper. The crux is the construction
of a fairly long representable arithmetic progression with not too large
difference; this is achieved by means of Lemma 1, the rest is mopping-up.
Reviewed by B. J. Birch
------------------------------------------------------------------------------
29:63 10.60 (12.30)
Graham, R. L. Complete sequences of polynomial values.
Duke Math. J. 31 1964 275--285.
------------------------------------------------------------------------------
Let S = (s_1,s_2,...) be a sequence of real numbers and P(S) the set of
sums of the form \sum_{k=1}^oo e_k s_k , where e_k is 0 or 1 and all but a
finite number of e_k are 0. If all sufficiently large integers belong to P(S),
then S is said to be complete. It is proved in the paper in a simple and
elementary manner that if f(x) is a polynomial with real coefficients,
f(x) = a0 + a1(x 1) +...+ an(x n), an != 0, (x r) = (x(x-1)...(x-r+1))/r!
then the sequence S(f)=(f(1),f(2),...) is complete if and only if
(1) ak = p_k/q_k for some integers p_k and q_k with (p_k,q_k)=1 and
q_k != 0 for 0 <= k <= n
(2) an > 0
(3) gcd(p_0,p_1,...,p_n) = 1 .
Reviewed by M. J. Wonenburger
------------------------------------------------------------------------------
33:7318 10.45
Folkman, Jon
On the representation of integers as sums of distinct terms from a fixed
sequence.
Canad. J. Math. 18 1966 643--655.
------------------------------------------------------------------------------
Let A be a sequence of positive integers a_1 <= a_2 <= a_3 <=... and
denote by P(A) the set of integers which are the sums of any number of
distinct terms of A , that is, P(A) = {\sum_{n=1}^oo e_n a_n : e_n = 0 or 1,
almost all e_n = 0}. It is proved that P(A) contains all sufficiently large
integers provided that (i) it contains an element of every arithmetic
progression, and (ii) either a_n = O(n^\a) or a_n is strictly increasing
and a_n = O(n^{1+\a}) , where \a is a fixed number in the range 0 <= \a < 1.
The theorems become false for \a > 1. The strictly increasing case confirms a
conjecture of Erdos, who was able only to cope with \a <= (sqrt(5)-1)/2
[Acta Arith. 7 (1961/62), 345-354; MR 26:2387]. The proofs are elementary in
the technical sense.
Reviewed by J. W. S. Cassels
------------------------------------------------------------------------------
48:5994 10A45 (10-04)
Dressler, Robert E.; Parker, Thomas
12,758.
Math. Comp. 28 (1974), 313--314.
------------------------------------------------------------------------------
Authors' introduction: "R. Sprague [Math. Z. 51 (1948), 289-290; MR 10:283]
proved that every positive integer greater than 128 can be expressed as a sum
of distinct perfect squares. He also proved [ibid. 51 (1948), 466-468;
MR 10:514] that, for every integer n >= 2, there exists a largest positive
integer r_n that is not expressible as a sum of distinct n th powers (of
positive integers). In the light of the first reference above, we have
r_2 = 128. Unfortunately, the technique used in the second reference above is
existential and does not give any idea of the size of r_n for n>2. Our
purpose here is twofold: (1) we use a computer to find explicitly the value
of r_3 (it turns out to be 12,758), and (2) in the process we give a new
quantitative proof of Sprague's theorem for n=3."
------------------------------------------------------------------------------
50:9759 10A40
Dressler, Robert E.; Parker, Thomas
An addendum to: "12,758" (Math. Comp. 28 (1974), 313--314).
Math. Comp. 29 (1975), 675.
------------------------------------------------------------------------------
The authors point out that the result proved in the original article had been
announced by R. L. Graham [Duke Math. J. 31 (1964), 275-285; MR 29:63].
------------------------------------------------------------------------------
54:7373 10B35
Dressler, Robert E.; Pigno, Louis; Young, Robert
Sums of squares of primes.
Nordisk Mat. Tidskr. 24 (1976), no. 1, 39--40.
------------------------------------------------------------------------------
It is known [R. Sprague, Math. Z. 51 (1948), 289-290; MR 10, 283] that the
largest integer not representable as a sum of distinct squares is 128. In this
paper, the authors announce that the largest integer not representable as a
sum of distinct squares of primes is 17163. The authors use a lemma due to
H.-E. Richert [Nordisk Mat. Tidskr. 31 (1949), 120-122; MR 11:646] with the
inequality p_{i+1}^2 <= 2 p_i^2 (i >= 5) (p_i denoting the i th prime), and
computational verification for the numbers n in 17163 < n <= 17163 + 503^2.
Reviewed by K. Thanigasalam
------------------------------------------------------------------------------
90h:11011 11B13 (11D85 11P99)
Zannier, U.(I-SLRN)
On a theorem of Birch concerning sums of distinct integers taken from
certain sequences.
Math. Proc. Cambridge Philos. Soc. 106 (1989), no. 2, 199--206.
------------------------------------------------------------------------------
B.J. Birch [same journal 55 (1959), 370-373; MR 22:26] has proved that, for
coprime integers p, q >= 2, every sufficiently large integer may be written
as a sum of distinct terms p^r q^s. J.W. Cassels [Acta Sci. Math. (Szeged)
21 (1960), 111-124; MR 24:#A103] established a more general result by making
use of the circle method of Hardy and Littlewood. Here a different
generalization is presented: Let p >= 2 be an integer and let A be an
infinite set of positive integers such that the quotient of distinct elements
of A is never a power of p. If every arithmetic progression contains a sum of
distinct terms p^r a with r >= 0 and a in A then there is a finite subset
A' of A such that every sufficiently large integer is a sum of distinct terms
p^r a with a in A' . Taking A = {q^s : s >= 0} implies (a more precise form
of) Birch's result since, as is easy to see, every arithmetic progression
contains a sum of distinct powers of p , q and pq . The proof is quite
elementary but by no means trivial. {In (2) the central term must be replaced
by the fractional part of log K/log p+h/m .}
Reviewed by G. Turnwald
------------------------------------------------------------------------------
92j:11115 11P05 (11B13)
Mimura, Yoshio(J-KOBEE)
Partial sums of sequences.
Math. Japon. 36 (1991), no. 4, 677--679.
------------------------------------------------------------------------------
The author gives a generalization of a method used by Sprague to show that all
integers larger than 128 are sums of distinct squares. H.-E. Richert [Norsk
Mat. Tidsskr. 31 (1949), 120-122; MR 11:646], J. L. Brown, Jr. [Amer. Math.
Monthly 83 (1976), no. 8, 631-634; MR 55:2741] and R. L. Graham [Duke Math.
J. 31 (1964), 275-285; MR 29:63] have all dealt with similar questions and the
author's theorem is very close to a generalization given by Brown [op. cit.].
A number of special cases, some of which will be found in the above-mentioned
papers, are worked out. For example [...]
Reviewed by Joe Roberts
------------------------------------------------------------------------------
98a:11016 11B25 (11B05)
Hegyvari, Norbert(H-EOTVO)
Subset sums in N^2 . (English. English summary)
Combin. Probab. Comput. 5 (1996), no. 4, 393--402.
------------------------------------------------------------------------------
A well-known result of J. Folkman [Canad. J. Math. 18 (1966), 643-655;
MR 33:7318] is that given an increasing sequence of positive integers
A = {a_i}_{i=1}^oo <= N whose counting function A(n) = \sum_{a_i <= n} 1
satisfies A(n) > n^{1/2+\d} for all sufficiently large n and a fixed
positive \d, the subset sums set P(A) = {\sum e_i a_i : \e_i in {0,1}}
always contains an infinite arithmetic progression.
In his earlier paper [European J. Combin. 17 (1996), no. 8, 741-749;
MR 97g:11006], the author showed that no similar result holds for sequences on
the plane: there exists a sequence A < N^2 such that the number A(n) of
elements of this sequence in any square |x_i|<n, i=1,2, is A(n) > \a n^2
for all sufficiently large n and a positive constant \a, but P(A) contains
no infinite arithmetic progression.
In the paper under review it is shown, however, that a conclusion of this type
(and in fact, a much stronger conclusion) holds provided that the density
restriction imposed on A is expressed in the "correct" way. The main result
is essentially the following: Theorem. Let A <= N^2 , and let \d be a fixed
positive number. Assume that for any n in N^2 there is an a in A for which
|a-n| <= |n|^{1/8-\d}. Then there exist x_0 in N^2 and linearly independent
d1, d2 in N^2 such that {x0 + x1 d1 + x2 d2 : x1, x2 in N} <= P(A) .
It is also shown that d1 and d2 can always be chosen in such a way that
the angle between these two vectors is "large" and that the exponent 1/8
in the conditions of the theorem cannot be replaced by anything greater than
(sqrt{13}+1)/6 ~= 0.7675.
Reviewed by Vsevolod F. Lev
------------------------------------------------------------------------------
2001c:11014 11B25 (11B75)
Hegyvari, Norbert(H-EOTVO)
On the representation of integers as sums of distinct terms from a fixed set.
Acta Arith. 92 (2000), no. 2, 99--104.
------------------------------------------------------------------------------
An infinite set of distinct positive integers is said to be subcomplete if its
set of subset sums contains an infinite arithmetic progression. P. Erdos asked
for the maximal density of a non-subcomplete set. He proved [Acta Arith. 7
(1961/1962), 345-354; MR 26:2387] that, if the counting function A of a set
is such that A(n) >> n^{(sqrt(5)-1)/2}, then this set is subcomplete. This
result was improved by J. Folkman [Canad. J. Math. 18 (1966), 643-655;
MR 33:7318], who relaxed the condition on the counting function to
A(n) > n^{1/2 + e} for any e>0. No exponent better than 1/2 can be expected
in view of Cassels' construction [J. W. S. Cassels, Acta Sci. Math. Szeged
21 (1960), 111-124; MR 24:A103].
The paper provides a proof that A(n) > 300(n log(n))^{1/2} suffices to ensure
the subcompleteness. The key tool is a result obtained by A. Sarkozy [J. Number
Theory 48 (1994), no. 2, 197-218; MR 95k:11010] and G. A. Freiman [Discrete
Math. 114 (1993), no. 1-3, 205-217; MR 94b:11013] on the structure of the set
of subset sums for sufficiently dense sets (the result is that under such a
kind of hypothesis it contains a long arithmetic progression).
Let us finish this review with two references. Firstly, there is an addendum
to Freiman's quoted paper, namely [Discrete Math. 126 (1994), no. 1-3, 447
MR 1264518]. Secondly, the paper (mentioned in the addendum in the article
under review) by T. Luczak and T. Schoen ["On the maximal density of sum-free
sets", Acta Arith., to appear] contains essentially the same result as the
paper under review.
Reviewed by Alain Plagne
------------------------------------------------------------------------------
2003j:11019 11B75 (11A67)
Chen, Yong-Gao(PRC-NJN)
On subset sums of a fixed set.
Acta Arith. 106 (2003), no. 3, 207--211.
------------------------------------------------------------------------------
Let A be an infinite set of positive integers. The set of subset sums is
defined by P(A) = {\sum_{a in B} a : B <= A; |B|<oo}. The sequence is said
to be subcomplete if P(A) contains an infinite arithmetic progression.
In 1962 Erdos proved that |A(n)| > cn^\a, c>0 , implies the subcompleteness
of A , where \a = sqrt{5}-1/2 and A(n) is the counting function of A .
In 1966 Folkman proved that \a = 1-\eps, and recently the reviewer [Acta Arith.
92 (2000), no. 2, 99-104; MR 2001c:11014] and independently T. Luczak and
T. Schoen [Acta Arith. 95 (2000), no. 3, 225-229; MR 2001k:11018] improved this
result, proving for |A(n)| > c' sqrt{n log n} that the sequence is subcomplete.
In the present paper the author improves our result. He proves that if
|A(n)| > c sqrt{n}, c>0, then A is subcomplete.
The reviewer should mention that Szemeredi has also proved a similar result,
and his proof will appear in the near future.
Reviewed by Norbert Hegyvari
Robert B. Israel
> On 21 Oct 2003 22:26:31 GMT, isr...@math.ubc.ca (Robert Israel) wrote:
>
> >In article <433bpvo7387dkpvg0...@no.spam>,
> >Toni Lassila <to...@nukespam.org> wrote:
> >>Is there a theorem that states any square can be written as a sum
> >>(including negative terms) of only squares of primes and one so that
> >>no term is repeated twice?
> >I don't think you need the 1.
> > 64 = 13^2 - 11^2 + 5^2 - 3^2
> > 81 = 11^2 - 7^2 + 3^2
> > 100 = 11^2 - 5^2 + 2^2
> > 144 = 13^2 - 5^2
> > 196 = 17^2 - 11^2 + 7^2 - 5^2 + 2^2
> > 225 = 13^2 + 11^2 - 7^2 - 5^2 + 3^2
> > 256 = 13^2 + 7^2 + 5^2 + 3^2 + 2^2
> >Actually it seems that all positive integers at least up to 1000 can be
> >written as differences of sums of squares of distinct primes. I wouldn't
> >be surprised if this was true for all positive integers, but I don't
> >immediately see a way to prove it.
> Was this result derived from another result or brute-forced?
Computed, not quite brutally, but now here's a proof (well, almost).
Let p_n be the n'th prime.
Note (by explicit computation) that all integers up to 642 can be expressed
using the first 8 primes, e.g. 642 = 19^2 + 13^2 + 11^2 - 3^2.
The bottleneck, btw, is 2, which can't be expressed using the first 7 primes,
but is 19^2 - 13^2 - 11^2 - 7^2 - 5^2 + 3^2 - 2^2.
Let X_k be the largest positive integer x such that all integers from 1 to x
can be expressed using the first k primes (so X_8 >= 642). Note that
X_8 > p_9^2 = 529. Now if X_k >= p_{k+1}^2, then X_{k+1} >= X_k + p_{k+1}^2
(since for any integer x from X_k + 1 to X_k + p_{k+1}^2, we can subtract
p_{k+1}^2 and obtain an integer that can be expressed using the first k primes).
We will then have X_{k+1} >= p_{k+2}^2 if 2 p_{k+1}^2 >= p_{k+2}^2, i.e.
p_{k+2} <= sqrt(2) p_{k+1}. Now I'm quite sure that this is true
for all k > 3. It certainly is true for k sufficiently large, by the Prime
Number Theorem, but I don't know of explicit estimates. Assuming it is
true, we have X_k >= p_{k+1}^2 for all k >= 8, so X_k -> infinity
as k -> infinity, and any integer can be expressed by taking k sufficiently
large. Moreover, in the expression any negative terms will come from the
first 8 primes.
Rainer Rosenthal
Robert B. Israel wrote
>
> Computed, not quite brutally, but now here's a proof (well, almost).
>
Clap - clap - clap - bravo!!
Well, they say there are similarities between math and music.
This is pretty true: You can enjoy the performance even if
you do not really understand :-)
(Am I right, when I see a distant connection between your
conjecture (...well, almost...) and Andrica's conjecture?)
With kind regards
Rainer Rosenthal
r.ros...@web.de
Manning
seem to be many possible answers - I found 21 variations for 4^2 = 16 just
using the first 10 primes (2 3 5 7 11 13 17 19 23 29).
Eg:
16 = 529 - 361 - 289 + 121 + 25 - 9 (23, 19, 17, 11, 5, 3)
16 = 841 - 361 - 289 - 121 - 49 - 9 + 4 (29, 19, 17, 11, 7, 3, 2)
However there is nothing special about squares, I generated numerous
variations for every integer, positive and negative. I ran the first
2,000,000 results (out of the 3^20 possible) using the first 20 primes and
saw no special pattern - every integer appears to be getting represented
repeatedly by different permutations.
Regards
Manning
Sydney
"Bill Dubuque" <w...@nestle.ai.mit.edu> wrote in message
news:y8zbrs9...@nestle.ai.mit.edu...
Toni Lassila
wrote:
>Computed, not quite brutally, but now here's a proof (well, almost).
>
>Let p_n be the n'th prime.
>Note (by explicit computation) that all integers up to 642 can be expressed
>using the first 8 primes, e.g. 642 = 19^2 + 13^2 + 11^2 - 3^2.
>The bottleneck, btw, is 2, which can't be expressed using the first 7 primes,
>but is 19^2 - 13^2 - 11^2 - 7^2 - 5^2 + 3^2 - 2^2.
>Let X_k be the largest positive integer x such that all integers from 1 to x
>can be expressed using the first k primes (so X_8 >= 642). Note that
>X_8 > p_9^2 = 529. Now if X_k >= p_{k+1}^2, then X_{k+1} >= X_k + p_{k+1}^2
>(since for any integer x from X_k + 1 to X_k + p_{k+1}^2, we can subtract
>p_{k+1}^2 and obtain an integer that can be expressed using the first k primes).
>We will then have X_{k+1} >= p_{k+2}^2 if 2 p_{k+1}^2 >= p_{k+2}^2, i.e.
>p_{k+2} <= sqrt(2) p_{k+1}.
Impressive.
>Now I'm quite sure that this is true for all k > 3. It certainly is true for k
>sufficiently large, by the Prime Number Theorem, but I don't know of explicit
>estimates.
So the question is, can we find an example for all integers before the
ratio of subsequent primes p_(k+1)/p_k falls permanently under sqrt(2)
at some k > N? To complete the proof, I think we need a definite upper
bound for N (assumed to be three at the moment).
Toni Lassila
<martin_...@west.raytheon.com> wrote:
>My guess is that the primality is a red herring. What matters is that
>the sequence has a growth rate that is not too fast and is moderately
>regular.
This is actually what I began wondering about when attempting to
formulate the problem. Assuming a set (finite or infinite) of unique
integers, what is the minimal set of integers that covers all possible
integers as a sum of their differences?
It's trivial to prove that there are infinite sequences that are much
denser than the sequence of, say square primes, but that still don't
cover nearly every integer. Take for example the sequence of evens[1],
which fails to cover every odd number etc. So can we construct a
minimally dense sequence that covers all integers and if so, what does
that sequence look like?
This is related to my second conjecture about the sequence of square
primes, which might be reposed as "is it possible to leave out any of
the square primes and still cover all the integers"?
[1] BTW, is this also the densest sequence that fails to do so?
Hugo Pfoertner
> >
> > Robert Israel wrote:
> > >
> > > In article <433bpvo7387dkpvg0...@no.spam>,
> > > Toni Lassila <to...@nukespam.org> wrote:
> > > >Is there a theorem that states any square can be written as a sum
> > > >(including negative terms) of only squares of primes and one so that
> > > >no term is repeated twice?
> > >
> > A related question:
> >
> > I wrote a little program checking how many terms are needed to represent
> > n by the minimum number of distinct squares of primes.
> >
6 ?
7 ?
...
[...]
> > Can we always find a solution with 5 terms for those n marked with "?".
>
Edwin Clark wrote:
> <<
> I find that just using the first 12 primes all numbers from 1 to 1123
> can be written in the form sum(s[i]*p[i]^2, i=1..k) where s[i] is 1 or
> -1,
> the primes p[i] are distinct and k <=5
> >>
Although it seems that my question about minimal representations is
considered to be "off topic" in this thread, here is what I've found
so far by brute force search:
http://www.randomwalk.de/sequences/a088910.txt
Hugo Pfoertner
Toni Lassila
wrote:
>Another related question is, is it possible to express the square of
>any prime as differences of sums of other squares of distinct primes?
>It's certainly possible if one includes 1, but what about without it?
I've verified that the only prime squares less than (p_8)^2 not
expressible as sums of differences of other prime squares less than
(p_8)^2 are 4 and 9:
25 = 49 - 121 + 169 + 289 - 361
49 = 121 + 289 - 361
121 = 49 - 289 + 361
169 = 25 - 49 + 121 - 289 + 361
289 = 49 - 121 + 361
361 = -49 + 121 + 289
Hugo Pfoertner
The "minimal" representations, minimizing the largest prime used
in the sum:
:
2^2 = 4 = -29^2 + 19^2 + 17^2 + 11^2 + 7^2 + 5^2
3^2 = 9 = -37^2 + 23^2 + 19^2 + 17^2 + 11^2 + 7^2 + 5^2 + 2^2
5^2 = 25 = -19^2 + 17^2 + 13^2 - 11^2 + 7^2
7^2 = 49 = -19^2 + 17^2 + 11^2
11^2 = 121 = 19^2 - 17^2 + 7^2
13^2 = 169 = 19^2 - 17^2 + 11^2 - 7^2 + 5^2
17^2 = 289 = 19^2 - 11^2 + 7^2
19^2 = 361 = 17^2 + 11^2 - 7^2
23^2 = 529 = 19^2 + 17^2 - 11^2
29^2 = 841 = 19^2 + 17^2 + 11^2 + 7^2 + 5^2 - 2^2
31^2 = 961 = 19^2 + 17^2 + 13^2 + 11^2 + 5^2 - 2^2
37^2 = 1369 = 23^2 + 19^2 + 17^2 + 13^2 + 5^2 - 2^2
41^2 = 1681 = 29^2 + 19^2 + 17^2 + 13^2 + 5^2 - 2^2
= 29^2 + 23^2 + 13^2 + 11^2 + 5^2 - 2^2
43^2 = 1849 = 29^2 + 23^2 + 17^2 + 13^2 + 5^2 - 2^2
47^2 = 2209 = 29^2 + 23^2 + 19^2 + 17^2 + 13^2 + 5^2 - 3^2 + 2^2
= 29^2 + 23^2 + 19^2 + 17^2 + 13^2 + 7^2 - 5^2 - 2^2
53^2 = 2809 = 31^2 + 29^2 + 23^2 + 19^2 + 11^2 - 2^2
If we don't look for the smallest possible maximum prime, but for the
minimum number of terms, there are different representations for
13^2 = 169 = 31^2 - 29^2 + 7^2
= -31^2 + 29^2 + 17^2
29^2 = 841 = 23^2 + 19^2 - 7^2
31^2 = 961 = 29^2 + 13^2 - 7^2
37^2 = 1369 = 31^2 + 23^2 - 11^2
41^2 = 1681 = 31^2 + 29^2 - 11^2
43^2 = 1849 = 37^2 + 23^2 - 7^2
47^2 = 2209 = 37^2 + 31^2 - 11^2
53^2 = 2809 = 47^2 + 31^2 - 19^2
Hugo Pfoertner