[seqfan] Re: Numbers > 1 not multiple nor a sum of any other terms.

Sun Dec 1 21:49:21 CET 2019

It's a good general point that "greedy" and "lexicographically earliest" can produce different sequences, but in this case I think they provably produce the same sequence, not just probably (*). Specifically, "greedy" and "lexicographically earliest" will only produce different sequences if "greedy" runs into a dead end, where no number meets the criteria for choosing the next term of the sequence. But since 1 is excluded from being a term of the sequence (in the draft version of A330070), we know that m * LCM(a(1), a(2), a(3), ..., a(n-1)) + 1 meets the "multiple" criterion for a(n) for all m > 0, and that no integer exceeding SUM(a(1), a(2), a(3), ..., a(n-1)) fails the "sum" criterion. So by choosing m to be sufficiently large (**), we can always find an integer that meets both the "sum" and the "multiple" criteria - i.e. "greedy" does not run into a dead end for this sequence.

Looking at Christian Lawson-Perfect's first 31 terms of the sequence:

2, 3, 7, 11, 17, 25, 59, 67, 185, 193, 563, 571, 1697, 1747, 5141, 5149, 11995, 25727, 27439, 78893, 82345, 240131, 243583, 723845, 727297, 2174987, 2178439, 6530119, 6530123, 13061947, 19590377

I notice a curious tendency for the terms to appear in pairs that are quite close to each other (at least in terms of their ratio being close to 1, not necessarily their difference being close to 0). Bracketing the pairs together to illustrate this:

2, 3, 7, 11, 17, 25, [59,67], [185,193], [563,571], [1697,1747], [5141,5149], 11995, [25727,27439], [78893,82345], [240131,243583], [723845,727297], [2174987,2178439], [6530119,6530123], 13061947, 19590377

It doesn't happen universally - 11995 and 13061947 are unpaired, and the first six terms are too small for it to be at all clear whether they're paired or not. But it would be interesting to know whether this is a persistent feature of the sequence, and if so, whether there's an explanation of it... 

(*) I notice by the way that this is a rather unusual case, where a common kind of typo - typing one letter when one means an adjacent letter on a standard qwerty keyboard - changes the meaning to another entirely plausible but different one...

(**) I think m = 1 will always be sufficiently large provided one treats the LCM of the empty set as being 1, but that is not essential for the proof.

David

> On 01 December 2019 at 18:12 Neil Sloane <njasloane at gmail.com> wrote:
> 
> 
> David Seal makes some excellent comments and indeed the definition should
> be clarified in the way he suggests.
> 
> As for "lexicographically earliest sequences " versus "a(n) is the smallest
> number such that ...", remember these are different conditions: the former
> is a global condition, the latter is a local condition. It probably doesn't
> matter here, so let's use "greedy", which is a lot simpler.
> 
> The point is that "lex earliest" allows backtracking, whereas "a(n) is
> smallest" uses the greedy algorithm and doesn't let you correct mistakes if
> you run into a dead end. Example: A327762 uses greedy alg and dies after 56
> terms, while A327460 is lex earliest and is infinite.
> 
> Jonathan, will you make the necessary changes to your submission?
> 
> Best regards
> Neil
> 
> Neil J. A. Sloane, President, OEIS Foundation.
> 11 South Adelaide Avenue, Highland Park, NJ 08904, USA.
> Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ.
> Phone: 732 828 6098; home page: http://NeilSloane.com
> Email: njasloane at gmail.com
> 
> 
> 
> On Sun, Dec 1, 2019 at 10:23 AM Christian Lawson-Perfect <
> christianperfect at gmail.com> wrote:
> 
> > A similarly naive Python script produced the following 31 terms in a few
> > seconds, then ran out of memory:
> >
> > 2, 3, 7, 11, 17, 25, 59, 67, 185, 193, 563, 571, 1697, 1747, 5141, 5149,
> > 11995, 25727, 27439, 78893, 82345, 240131, 243583, 723845, 727297, 2174987,
> > 2178439, 6530119, 6530123, 13061947, 19590377
> >
> > On Sun, 1 Dec 2019 at 09:46, jnthn stdhr <jstdhr at gmail.com> wrote:
> >
> > > Hi all.
> > >
> > > I didn't find this in the db, and superseeker had no suggestions.
> > > https://oeis.org/A330070 is the sequence of numbers that are neither a
> > sum
> > > nor a multiple of smaller terms, and starts:
> > >
> > > 2, 3, 7, 11, 17, 25, 59, 67, 185, 193, 563, 571, 1697, 1747, 5141, 5149,
> > > 11995, 25727, 27439, 78893, 82345, 240131, 243583,...
> > >
> > > Example:  a(6) = 25, because 25 = 5 x 5, and 5 is not in the sequence,
> > and
> > > no combination of 2, 3, 7, 11, and 17 sum to 25.
> > >
> > > The divisors (d > 1) of composite terms are:
> > >
> > > 25 [5]
> > > 185 [5, 37]
> > > 5141 [53, 97]
> > > 5149 [19, 271]
> > > 11995 [5, 2399]
> > > 25727 [13, 1979]
> > > 27439 [23, 1193]
> > > 82345 [5, 16469, 43, 1915, 215, 383]
> > >
> > > Based on my original idea below (composites with this property), my
> > > conjecture is that composite terms > 25  will only have either two or six
> > > non-trivial divisors.
> > >
> > > My code takes ten+ minutes to find the first 21 terms.  The "is n a
> > > multiple" test is efficient enough, just test if any divisors of n are in
> > > the sequence.  As for sums, naively, I am storing all combinations, which
> > > means in the worst case ~2^n sums must be checked.  Any ideas on how to
> > > improve on this?
> > >
> > > A330071 will be the composite-only version, if that seems appropriate.
> > > 4, 6, 9, 14, 21, 22, 38, 106, 111, 118,123, 465, 470,1394, 1405, 4193,
> > > 4209, 9446,13289, 22258, 26101, 70617, 79959, ...
> > >
> > > divisors > 1:
> > > 4 [2]
> > > 6 [2, 3]
> > > 9 [3]
> > > 14 [2, 7]
> > > 21 [3, 7]
> > > 22 [2, 11]
> > > 38 [2, 19]
> > > 106 [2, 53]
> > > 111 [3, 37]
> > > 118 [2, 59]
> > > 123 [3, 41]
> > > 465 [3, 155, 5, 93, 15, 31]
> > > 470 [2, 235, 5, 94, 10, 47]
> > > 1394 [2, 697, 17, 82, 34, 41]
> > > 1405 [5, 281]
> > > 4193 [7, 599]
> > > 4209 [3, 1403, 23, 183, 61, 69]
> > > 9446 [2, 4723]
> > > 13289 [97, 137]
> > > 22258 [2, 11129, 31, 718, 62, 359]
> > > 26101 [43, 607]
> > > 70617 [3, 23539]
> > > 79959 [3, 26653, 11, 7269, 33, 2423]
> > >
> > >  For this one, super seeker suggested  (lgdegf)
> > > 81-216*a(n)+216*a(n)^2-96*a(n)^3+16*a(n)^4.
> > >
> > > Jonathan
> > >
> > > --
> > > Seqfan Mailing list - http://list.seqfan.eu/
> > >
> >
> > --
> > Seqfan Mailing list - http://list.seqfan.eu/
> >
> 
> --
> Seqfan Mailing list - http://list.seqfan.eu/