A129755 (??!!)

[Andrew Plewe]

sum of constant-spaced integers, can you "easily" (i.e., at most polynomial
sure if it can be done quickly.
	-Andrew Plewe-
From: Jonathan Post [mailto:jvospost3 at gmail.com]
Sent: Thursday, May 31, 2007 11:44 AM
To: zak seidov
Cc: seqfan at ext.jussieu.fr; jvospost2 at yahoo.com
Subject: Re: A129755 (??!!)
Return-Path: <maxale at gmail.com>
X-Ids: 164
DKIM-Signature: a=rsa-sha1; c=relaxed/relaxed;
        d=gmail.com; s=beta;
        h=domainkey-signature:received:received:message-id:date:from:to:subject:cc:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references;
        b=MAymFwuddWAbbVFjqFPOjQewuTmJOCZo3TsYP6ZrhS8+a5lRgvBIqFhxPJblku7K9NeQlfqmmyzda+ccE8O7nQNaT1ZRsIxN0k47755zIHX2D5NG2o1bZy0l2q8WPXOIeu4ajGsQlDJ6sRNZmw4jbsKYET7TTfoHeUU9w1VjVi0=
DomainKey-Signature: a=rsa-sha1; c=nofws;
        d=gmail.com; s=beta;
        h=received:message-id:date:from:to:subject:cc:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references;
        b=Jy2soTuN2GcLm/KSbS7nDuHvHzNJPvMuyKVFuoFw2QS681qPubN3KJXxexcoyP69zsATvHRM5LgKKtByl+NO6VNLRt07NBIIPkQkxLCsFY6+SHxqpv6FA/RSGCUtb/NCksATsw1wBVilVvrlOTeaBT+v3DZ2PPUPSYkxS5XhKk0=
Message-ID: <d3dac270706011254r771618f8l327e506f39c704ea at mail.gmail.com>
Date: Fri, 1 Jun 2007 12:54:10 -0700
From: "Max Alekseyev" <maxale at gmail.com>
To: "Andrew Plewe" <aplewe at sbcglobal.net>
Subject: Re: A129755 (??!!)
Cc: "Jonathan Post" <jvospost3 at gmail.com>, "zak seidov" <zakseidov at yahoo.com>,
   seqfan at ext.jussieu.fr, jvospost2 at yahoo.com
In-Reply-To: <200706011859.l51Ix3nf017185 at shiva.jussieu.fr>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
References: <5542af940705311143we220ac3ybfec25c65cca405c at mail.gmail.com>
	 <200706011859.l51Ix3nf017185 at shiva.jussieu.fr>
X-Greylist: IP, sender and recipient auto-whitelisted, not delayed by milter-greylist-3.0 (shiva.jussieu.fr [134.157.0.164]); Fri, 01 Jun 2007 21:54:12 +0200 (CEST)
X-Virus-Scanned: ClamAV 0.88.7/3336/Fri Jun  1 13:28:33 2007 on shiva.jussieu.fr
X-Virus-Status: Clean
X-j-chkmail-Score: MSGID : 46607963.000 on shiva.jussieu.fr : j-chkmail score : X : 0/50 1 0.619 -> 1
X-Miltered: at shiva.jussieu.fr with ID 46607963.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)!

On 6/1/07, Andrew Plewe <aplewe at sbcglobal.net> wrote:

> 1.) If you know the factors of some composite integer k, can you find all
> the representations of k as a sum of constant-spaced integers? For instance,
> 35 = 5*7, has at least the following representations:
> {7 7 7 7 7; 5 6 7 8 9; 3 5 7 9 11; 1 4 7 10 13; 5 5 5 5 5 5 5; 2 3 4 5 6 7
> 8}. Is that all of them? Is there an algorithmic way to determine all of
> them?

First off, I assume that you are looking for sums of non-negative integers.
Let
k = a + (a + d) + (a + 2d) + ... + (a + (n-1)d)
be the sum of n>1 equally spaced integers where a is the smallest
integer and d is the distance between two adjacent integers.
Then
k = ( (2a + (n-1)d) * n ) / 2
implying that n is a divisor of 2k.

Let n go over all divisors of 2k (the factorization of which is known)
greater than 1.
Define
b = (2k/n) mod (n-1)
and for every integer in the row:
a = b/2, a = (b + (n-1))/2, a = (b + 2(n-1))/2, ..., a = (2k/n)/2,
let d = (2k/n - 2a) / (n-1).
This procedure will give you all possible values of parameters n, a, d.

Furthermore, the range of n can be limited to divisors of k, and
divisors of 2k smaller than sqrt(2k).

For the example above: k = 35 = 5*7
n goes over divisors of 2k=70:
We have:
1) n=2, b=0, (a,d)=(0,35), (a,d)=(1,34), ..., (a,d)=(17,1), giving
35 = 0 + 35
35 = 1 + 34
...
35 = 17 + 18
2) n=5, b=2, (a,d)=(1,3), (a,d)=(3,2), (a,d)=(5,1), (a,d)=(7,0), giving
35 = 1 + 4 + 7 + 10 + 13
35 = 3 + 5 + 7 + 9 + 11
35 = 5 + 6 + 7 + 8 + 9
35 = 7 + 7 + 7 + 7 + 7
3) n=7, b=4, (a,d)=(2,1), (a,d)=(5,0), giving
35 = 2 + 3 + 4 + 5 + 6 + 7 + 8
35 = 5 + 5 + 5 + 5 + 5 + 5 + 5
4) n=35, b=2, (a,d)=(1,1), giving
35 = 1 + 1 + 1 + ... + 1 (35 ones)

> 2.) Is the converse true; if you know one of the representations of k as the
> sum of constant-spaced integers, can you "easily" (i.e., at most polynomial
> time) determine the others?

 From the list of *all* such representations of k one can easily
determine the factorization of k.
On the other hand, a single representation gives at most two
co-factors of k. Therefore, generally it is not possible to derive all
representations from a single one without completing (directly or
indirectly) factorization of k.

Max



Excellent, thanks for this. Regarding this:

 From the list of *all* such representations of k one can easily
determine the factorization of k.
On the other hand, a single representation gives at most two
co-factors of k. Therefore, generally it is not possible to derive all
representations from a single one without completing (directly or
indirectly) factorization of k.

-----Original Message-----

On 6/1/07, Andrew Plewe <aplewe at sbcglobal.net> wrote:

> 1.) If you know the factors of some composite integer k, can you find all
> the representations of k as a sum of constant-spaced integers? For
instance,
> 35 = 5*7, has at least the following representations:
> {7 7 7 7 7; 5 6 7 8 9; 3 5 7 9 11; 1 4 7 10 13; 5 5 5 5 5 5 5; 2 3 4 5 6 7
> 8}. Is that all of them? Is there an algorithmic way to determine all of
> them?

First off, I assume that you are looking for sums of non-negative integers.
Let
k = a + (a + d) + (a + 2d) + ... + (a + (n-1)d)
be the sum of n>1 equally spaced integers where a is the smallest
integer and d is the distance between two adjacent integers.
Then
k = ( (2a + (n-1)d) * n ) / 2
implying that n is a divisor of 2k.

Let n go over all divisors of 2k (the factorization of which is known)
greater than 1.
Define
b = (2k/n) mod (n-1)
and for every integer in the row:
a = b/2, a = (b + (n-1))/2, a = (b + 2(n-1))/2, ..., a = (2k/n)/2,
let d = (2k/n - 2a) / (n-1).
This procedure will give you all possible values of parameters n, a, d.

Furthermore, the range of n can be limited to divisors of k, and
divisors of 2k smaller than sqrt(2k).

For the example above: k = 35 = 5*7
n goes over divisors of 2k=70:
We have:
1) n=2, b=0, (a,d)=(0,35), (a,d)=(1,34), ..., (a,d)=(17,1), giving
35 = 0 + 35
35 = 1 + 34
...
35 = 17 + 18
2) n=5, b=2, (a,d)=(1,3), (a,d)=(3,2), (a,d)=(5,1), (a,d)=(7,0), giving
35 = 1 + 4 + 7 + 10 + 13
35 = 3 + 5 + 7 + 9 + 11
35 = 5 + 6 + 7 + 8 + 9
35 = 7 + 7 + 7 + 7 + 7
3) n=7, b=4, (a,d)=(2,1), (a,d)=(5,0), giving
35 = 2 + 3 + 4 + 5 + 6 + 7 + 8
35 = 5 + 5 + 5 + 5 + 5 + 5 + 5
4) n=35, b=2, (a,d)=(1,1), giving
35 = 1 + 1 + 1 + ... + 1 (35 ones)

> 2.) Is the converse true; if you know one of the representations of k as
the
> sum of constant-spaced integers, can you "easily" (i.e., at most
polynomial
> time) determine the others?

 From the list of *all* such representations of k one can easily
determine the factorization of k.
On the other hand, a single representation gives at most two
co-factors of k. Therefore, generally it is not possible to derive all
representations from a single one without completing (directly or
indirectly) factorization of k.

Max





Oops, I hit a key and Outlook sent that last email before I was done
writing. Here's what I meant to write:


Excellent, thanks! Regarding this statement:

"From the list of *all* such representations of k one can easily determine
the factorization of k. On the other hand, a single representation gives at
most two co-factors of k. Therefore, generally it is not possible to derive
all representations from a single one without completing (directly or
indirectly) factorization of k."

There is one property of constant-spaced integers which allows for the easy
factorization of some of them. Consider the following representation of 35:

2+3+4+5+6+7+8 = 35

By visual inspection it's easy to see that this could be rewritten:

5+6+7+8+9 = 35

By noting that 2+3 = 5 and redistributing this over the remaining 5 terms.
Another example, using a slightly different representation:

1+2+3+4+5+6+7+8+9+10+11+2 = 5+6+7+8+9+10+11+12 = 68 = 4*17,

By adding 1+2+3+2 = 8 and redistributing. Since 8 redstributes completely
over the remaining terms, we can then compute GCD(k, n), where n is the
number of terms in the new representation of k.

The general idea is that if the factors of k are relatively close together
or far apart, then there is a good chance that a representation exists which
transforms "easily" into another representation, revealing other factors of
k. Hence if a number has many such representations, then perhaps the chance
of finding one goes up.