a property of multisets: unit fractions with a twist

Tue Dec 18 11:45:52 CET 2007

somewhere between 300 and 85000 CPU years on my machine.
  if (n < 3, error("Requires n >= 3"), A118085_r(2, 1, 0, n));
  local(cmin = max(prev, ceil(q / (p - q))));
  local(cmax = floor(1 / ((p / q) ^ (1 / len) - 1)));
  local(count = 0);
  local(cur, p2, q2, g, d2, pq2, fmin, f);
  if (len == 3,
    forstep (cur = cmin, cmax, 1,
      p2 = p * cur;
      q2 = q * (cur + 1); 
      g = gcd(p2, q2);
      if (g > 1, p2 /= g; q2 /= g);
      d2 = p2 - q2; 
      if (d2 > 0,
        pq2 = p2 * q2;
        if (d2 > 1,
          fmin = cur * d2 - q2;
          fordiv (pq2, f,
            if (f < fmin, next);
            if (f * f > pq2, break);
            if ((f + q2) % d2 == 0 & (pq2 / f + q2) % d2 == 0, count++);
          )
        ,           
          fmin = cur - q2;
          count += floor(numdiv(pq2) / 2);
          if (fmin > 0,
            fordiv (pq2, f, if (f < fmin, count--, break))
          );            
        );          
      );        
    );      
  ,
    forstep (cur = cmin, cmax, 1,
      p2 = p * cur;
      q2 = q * (cur + 1);
      if (p2 > q2, 
        count += A118085_r(p * cur, q * (cur + 1), cur, len - 1)
      );
    );
  );    
  count;
Return-Path: <njas at research.att.com>
X-Ids: 164
Date: Tue, 18 Dec 2007 08:05:33 -0500
From: "N. J. A. Sloane" <njas at research.att.com>
Message-Id: <200712181305.lBID5Xb8008897 at prim.research.att.com>
X-Mailer: mailx (AT&T/BSD) 9.9 2006-04-17
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
To: seqfan at ext.jussieu.fr
Subject: OEIS machine may have crashed at 05:00
X-Greylist: IP, sender and recipient auto-whitelisted, not delayed by milter-greylist-3.0 (shiva.jussieu.fr [134.157.0.164]); Tue, 18 Dec 2007 14:05:39 +0100 (CET)
X-Virus-Scanned: ClamAV 0.88.7/5164/Tue Dec 18 10:56:45 2007 on shiva.jussieu.fr
X-Virus-Status: Clean
X-Miltered: at shiva.jussieu.fr with ID 4767C5A2.005 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)!
Return-Path: <njas at research.att.com>
X-Ids: 165
Date: Tue, 18 Dec 2007 08:14:09 -0500
From: "N. J. A. Sloane" <njas at research.att.com>
Message-Id: <200712181314.lBIDE9YG008943 at prim.research.att.com>
X-Mailer: mailx (AT&T/BSD) 9.9 2006-04-17
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
To: seqfan at ext.jussieu.fr
Subject: about reporting OEIS troubles 
Cc: njas at research.att.com
X-Greylist: IP, sender and recipient auto-whitelisted, not delayed by milter-greylist-3.0 (shiva.jussieu.fr [134.157.0.165]); Tue, 18 Dec 2007 14:14:12 +0100 (CET)
X-Virus-Scanned: ClamAV 0.88.7/5164/Tue Dec 18 10:56:45 2007 on shiva.jussieu.fr
X-Virus-Status: Clean
X-Miltered: at shiva.jussieu.fr with ID 4767C7A3.002 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)!
  help at research.att.com
Return-Path: <maximilian.hasler at gmail.com>
X-Ids: 164
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=gmail.com; s=gamma;
        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;
        bh=e1VRh3Ke5f0ZxrWEx/cI/SUiryUY0XOsFtKDfnwlI80=;
        b=DNGc7zl/heLr14fnowNpk3ItpMIgwqulVeZhaLjOlI/h7wrMT1VL7/zVCmymAUgHMX3PF1veaGmdjQm3NJZXcNJzEuDpdKnkkwDHVOqXMLltq0JMuzih7utDve/IWFxbtHcJM7DYK/96ktV2wOHl6y5/hjGWoC6ojqw4052dw+Y=
DomainKey-Signature: a=rsa-sha1; c=nofws;
        d=gmail.com; s=gamma;
        h=message-id:date:from:to:subject:cc:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references;
        b=fUVXMyhXnwSZrShcAI0HcyRJyXexUmcJlcGvrOK0M812XLNC6ywTtZToPANANZD2WfGvEwgZiZ2EfJC40tirqI88i1Y9TnT2zZxfk0+jRoM8mKlBOrdSY/qM8HeAth2kao0cEGXXV9xK9ROG7QgkHeWvWrWlKESFH8DHnLj6WXU=
Message-ID: <3c3af2330712180613u4f692b79sa779baf2417f014c at mail.gmail.com>
Date: Tue, 18 Dec 2007 10:13:33 -0400
From: "Maximilian Hasler" <maximilian.hasler at gmail.com>
To: petsie at dordos.net
Subject: Re: A094913 extension
Cc: seqfan at ext.jussieu.fr
In-Reply-To: <26378697.3684461197943510104.JavaMail.servlet at kundenserver>
MIME-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
References: <26378697.3684461197943510104.JavaMail.servlet at kundenserver>
X-Greylist: IP, sender and recipient auto-whitelisted, not delayed by milter-greylist-3.0 (shiva.jussieu.fr [134.157.0.164]); Tue, 18 Dec 2007 15:13:39 +0100 (CET)
X-Virus-Scanned: ClamAV 0.88.7/5164/Tue Dec 18 10:56:45 2007 on shiva.jussieu.fr
X-Virus-Status: Clean
X-j-chkmail-Score: MSGID : 4767D591.003 on shiva.jussieu.fr : j-chkmail score : X : 0/50 1 0.409 -> 1
X-Miltered: at shiva.jussieu.fr with ID 4767D591.003 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)!

I'm sorry I cannot read your .nb file, isn't there an option to save
as txt file ?
(your "Mathe" link also just redirects to wolfram.com)

I think the outcome of your algorithm depends on the order you do the
"zero or one" and "at each possible position".
e.g. one can notice that up to n=9, one can construct a "maximal" word
just by appending 0 or 1 to an initial 1, but then one gets stuck.
So it might be possible that your algorithm also gets stuck since you
dont speak of a "going back" mechanism needed for exhaustive recursive
search.

Did you check if you get the # of subwords given by my formula (which
obviously provides an upper bound, even if it remains unproven that
this bound can always be reached)

Maximilian

On Dec 17, 2007 10:05 PM,  <petsie at dordos.net> wrote:
> Hi seqfans,
>
> I do not know, why it works, but it seems to...
>
> I start with an empty list and at each step I try to insert a zero or an one at each possible position. Then I pick the first list with maximal number of sublists and start over.
> Say, we have had {0,0,1,1,0} as one of the lists with max. nr. of sublists. Then my candidates for the next test are:
>
> With[{lastbest = {0, 0, 1, 1, 0}},
>   Union[Flatten[
>     Outer[Insert[lastbest, #2, #1] & ,
>      Range[1 + Length[lastbest]],
>      {0, 1},
>     1], 1]]]
>
> {{0, 0, 0, 1, 1, 0}, {0, 0, 1, 0, 1, 0}, {0, 0, 1, 1, 0, 0},
>   {0, 0, 1, 1, 0, 1}, {0, 0, 1, 1, 1, 0}, {0, 1, 0, 1, 1, 0},
>   {1, 0, 0, 1, 1, 0}}
>
> see http://freenet-homepage.de/Peter_Berlin/Mathe/heuristicA094913.nb for the Mathematica notebook with the complete (simple) algorithm. There's a screenshot too (same URL but with .png instead of .nb).
>
> If this works correctly, the first 100 values of A094913 are calculated in ~30s :-)
>
> Peter