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

David Seal david.j.seal at gwynmop.com
Sun Dec 1 13:03:34 CET 2019


The definition of this sequence could usefully be tightened up, I think. In particular, if I've understood your intention correctly, it is that:

* Not being a sum of smaller terms is to be understood as saying that there is no combination of distinct smaller terms a(i) with i < n that sums to a(n).

* Not being a multiple of smaller terms is to be understood as saying that there is no single smaller term a(i) with i < n that divides a(n).

My first reading of it was that there was no pair of smaller terms whose sum is a(n) or whose product is a(n). That didn't work out because 8 would be in the sequence if it was your intended meaning, and that first reading wasn't quite compatible with you saying "multiple" rather than "product". But "neither a sum nor a multiple of smaller terms" means "not a sum of smaller terms" and "not a multiple of smaller terms", and what you actually mean (if I've understood it correctly) is "not a sum of smaller terms" and "not a multiple of a smaller term"... My point is that "neither a sum nor a multiple of smaller terms" skates over some differences between the two criteria, making it easy to get the wrong idea...

So basically, I think the "sum" and "multiple" criteria need to each be set out precisely, with the former spelling out that it's using a combination of distinct smaller terms ("distinct" is necessary - any integer > 3 can be expressed as a sum of sufficiently many 2s and 3s!) and the latter that it's using a single smaller term.

The other point about the definition that strikes me is that there are many such sequences - which I think means that the definition needs to say "a(n) is the smallest integer > 1 such that a(n) cannot be expressed as ...", or as a possible alternative, that the words "lexicographically smallest" need to appear in the description of the sequence.

With regard to your naïve testing of the "sum" criterion, this is an example of the 'knapsack' problem, and more specifically of the 'subset sum' problem which is a special case of it. The bad news is that those problems are NP-complete or NP-hard, so exponentially-increasing difficulty is to be expected in the long term; the good news is however that there are algorithms and heuristics for them that generally do quite a lot better than your doubling for each additional term of the sequence! That outline of their status is however pretty much the limit of my working knowledge about those problems, so I think the most helpful thing I can do is probably to refer you to https://en.wikipedia.org/wiki/Subset_sum_problem in the first place and possibly https://en.wikipedia.org/wiki/Knapsack_problem for more general stuff.

David

 
> On 01 December 2019 at 06:59 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/



More information about the SeqFan mailing list