[seqfan] Re: A greedy sequence
David Wilson
davidwwilson at comcast.net
Sun Feb 15 12:21:05 CET 2009
The fact that each greedy pass in this algorithm terminates is not
completely trivial, since the greedy passes must avoid numbers that have
appeared in earlier greedy passes, which interferes with the standard
termination argument. However, the argument can be patched to show that each
pass terminates.
As Maximilian's computations indicate, this sequence will quickly generate
some very large numbers, larger than we would probably want to include in a
b-file.
What is interesting to me is the subsequence of starting elements of each
pass, that is (1,2,4,11,31,83,...). It is arguably related to A002387, but I
am willing to bet it diverges at some point.
----- Original Message -----
From: <franktaw at netscape.net>
To: <seqfan at list.seqfan.eu>
Cc: <robin_murison at yahoo.co.uk>
Sent: Saturday, February 14, 2009 6:43 PM
Subject: [seqfan] Re: A greedy sequence
>I think you may have misread the reference you gave. The greedy
> algorithm
> for unit fractions always terminates (for a positive, rational target).
> It is only
> the *odd* greedy algorithm (constraining all denominators to be odd)
> for
> which termination is an unsolved problem. So there is no question that
> all
> sub-sequences do, in fact, terminate.
>
> You need to do this kind of computation using exact, "unlimited"
> precision
> integer arithmetic. Any floating point arithmetic will soon fail with
> this
> algorithm.
>
> Franklin T. Adams-Watters
>
>
> -----Original Message-----
> From: Jeremy Gardiner <jeremy.gardiner at btinternet.com>
>
> The following 'greedy' sequence is formed by summing unit fractions
> until
> the sum is 1, and repeating using up the 'left over' fractions:
>
> 1,
> 2,3,6,
> 4,5,7,8,9,10,15,230,57960,
> 11,12,13,14,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,1544,8242614,
> 31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,5
> 5,5
> 6,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80
> ,81
> ,82,202,60402,
>
> (according to my BASIC program implementation: could be errors due to
> accuracy of representation)
>
> - anyone else find this interesting, or seen this before?
>
> Likely needs some more investigation before thinking about submitting to
> OEIS!
>
> Perhaps related to the The Greedy Algorithm for Unit Fractions:
> http://www.mathpages.com/home/kmath454.htm
>
> I guess it may not be known if all of the sub-sequences terminate?
>
> Jeremy
>
>
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>
>
>
>
>
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
--------------------------------------------------------------------------------
Internal Virus Database is out of date.
Checked by AVG - www.avg.com
Version: 8.0.233 / Virus Database: 270.10.19/1939 - Release Date: 02/07/09
13:39:00
More information about the SeqFan
mailing list