[seqfan] Re: Is A026477 determined by prime signatures?
Bob Selcoe
rselcoe at entouchonline.net
Sat Aug 27 04:48:46 CEST 2016
Hi Graeme et al.
OK, I think I understand a little better.
> So, for example, if the input is (), (1,1), (1,1), then the output should
> be (2,1,1), (1,1,1,1)
Right, got it.
>My thinking is that I would apply the function to all triples of prime
> signatures that are IN the set to generate a list of prime signatures that
> are OUT.
OK, that explains why (2,2) is OUT: () and (2) are IN and (), (2), (2)
generates (2,2).
But I'm still a little confused about a couple of things (forgive me if it's
clear from the programming ideas you've mentioned, but I don't program so I
couldn't see it, no matter how obvious). First, (1,1) is OUT so based on the
comment above, your approach doesn't seem to apply to (), (1,1), (1,1).
Second, say we do evaluate all triples (not just ones that are IN), then in
the (), (1,1), (1,1) example, how do you distinguish that (1,1,1,1) is IN
but (2,1,1) is OUT??
Are you saying it's iterative, and that because (1) and (2) are IN then (1),
(1), (2) generates (2,1,1) OUT?? If so, I think your approach would work.
So I gather this is the method; let (P) be the partitions whose sum = S.
Testing for P as S increases:
S (P) IN or OUT
0 () IN by definition
1 (1) IN essentially by definition
2 (2) IN no combination of (), (1) => (2)
(1,1) OUT from (), (1), (1)
3 (3) OUT from (), (1), (2)
(2,1) OUT from (), (1), (2)
(1,1,1) OUT from (1), (1), (1)
4 (4) IN no combination of (), (1), (2) => (4)
(3,1) OUT from (1), (1), (2)
(2,2) OUT from (), (2), (2)
(2,1,1) OUT from (1), (1), (2)
(1,1,1,1) IN no triple combination of (), (1), (2), (4) =>
(1,1,1,1)
Then test for S=5 with triple combinations of (), (1), (2), (4) and
(1,1,1,1), which generates only (3,1,1) as IN; add that to the list to test
S=6, etc.
Is this what you meant by applying the partitions?? It might be pretty
cumbersome but I can't see a more efficient approach.
Cheers,
Bob
--------------------------------------------------
From: "Graeme McRae" <graememcrae at gmail.com>
Sent: Friday, August 26, 2016 6:58 PM
To: "Sequence Fanatics Discussion list" <seqfan at list.seqfan.eu>
Subject: [seqfan] Re: Is A026477 determined by prime signatures?
> Yeah, I agree, Bob S., it's no easy task, for sure. The heart of my idea,
> (or the germ of my idea, to be honest), is a function ProductSignature(a,
> b, c), which takes as input three prime signatures, and returns as output
> a
> list of all the possible prime signatures that can result from multiplying
> three distinct integers with these prime signatures.
>
> So, for example, if the input is (), (1,1), (1,1), then the output should
> be (2,1,1), (1,1,1,1)
>
> Notice that (2,2) isn't included in the output. This is because the three
> numbers with the input prime signatures must be distinct. This is but one
> of the many tricky things needed to write this function.
>
> But then, once the function is written and debugged, then the rest of the
> job isn't that hard (or maybe you see something I don't, quite possible!)
>
> My thinking is that I would apply the function to all triples of prime
> signatures that are IN the set to generate a list of prime signatures that
> are OUT. Then, I would find the "smallest" prime signature not already
> known to be IN or OUT, and define it to be IN. Rinse and repeat.
>
> Now, about "smallest", that's pretty easy. I would use a list of integer
> partitions in a standard sequence. (I've already written *that* part of
> the
> program!)
> ()
> (1)
> (2)
> (1,1)
> (3)
> (2,1)
> (1,1,1)
> (4)
> (3,1)
> (2,2)
> (2,1,1)
> (1,1,1,1)
> (5)
> (4,1)
> (3,2)
> (3,1,1)
> (2,2,1)
> (2,1,1,1)
> (1,1,1,1,1)
> (6)
> (5,1)
> (4,2)
> (4,1,1)
> (3,3)
> (3,2,1)
> (3,1,1,1)
> (2,2,2)
> (2,2,1,1)
> (2,1,1,1,1)
> (1,1,1,1,1,1)
> etc.
>
>
> --Graeme McRae
> Palmdale, CA
>
> On Fri, Aug 26, 2016 at 2:21 PM, Bob Selcoe <rselcoe at entouchonline.net>
> wrote:
>
>> Hi Graeme and Seqfans,
>>
>> I submitted a proof yesterday (revised today) on A026477 for Charles'
>> initial conjecture, noting that defining which signatures are IN and OUT
>> becomes increasingly complex as the sequence progresses; I welcome any
>> revisions to make the proof clearer.
>>
>> Then, find the "smallest" prime signature not previously listed as IN or
>>> OUT. This, of course, is the next one IN the sequence. The "smallest"
>>> prime
>>> signature means the prime signature with the smallest sum, listed in
>>> high-to-low collating sequence. (e.g. prime signatures whose sum is 4
>>> would
>>> be considered in this order: (4), (3,1), (2,2), (2,1,1), (1,1,1,1))
>>>
>>
>> Graeme, if I understand correctly, I think you may encounter some
>> difficulty with this approach. For example, (5,5) is OUT because (3,3)
>> and
>> (2) are IN rather than (2,2). So I think it's more complicated than
>> just
>> looking at signature sums. Am I missing something?
>>
>> Overall, I suspect coming up with a solution will be quite challenging.
>>
>> Cheers,
>> Bob S.
>>
>>
>> --------------------------------------------------
>> From: "Graeme McRae" <graememcrae at gmail.com>
>> Sent: Friday, August 26, 2016 2:26 PM
>> To: "Sequence Fanatics Discussion list" <seqfan at list.seqfan.eu>
>> Subject: [seqfan] Re: Is A026477 determined by prime signatures?
>>
>>
>> I've been reading this thread about A026477 with great interest, and have
>>> been trying to think about how I would write a program to build a list
>>> of
>>> prime signatures representing numbers that are IN (and a list that are
>>> OUT)
>>> of the sequence.
>>>
>>> My first thought was to start with the prime signatures of 1, 2, and 3,
>>> which are (), (1), and (1), respectively, and then consider the
>>> "products"
>>> of all triples of prime signatures that are already IN. These products,
>>> then, will be OUT.
>>>
>>> Then, find the "smallest" prime signature not previously listed as IN or
>>> OUT. This, of course, is the next one IN the sequence. The "smallest"
>>> prime
>>> signature means the prime signature with the smallest sum, listed in
>>> high-to-low collating sequence. (e.g. prime signatures whose sum is 4
>>> would
>>> be considered in this order: (4), (3,1), (2,2), (2,1,1), (1,1,1,1))
>>>
>>> When finding the products of prime signatures, I need to consider that
>>> (1)
>>> and (1) must represent different primes, so their product can't be (2).
>>> However, the prime factors of (1,1) and (1,1) need not be unique, so
>>> their
>>> products include (2,1,1) and (1,1,1,1) but not (2,2).
>>>
>>> I'll give this some more thought, and try a little programming using the
>>> VBA that comes with MS Excel. Who knows? Maybe some interesting
>>> sequences
>>> (or a comment on this sequence) might come out of it.
>>>
>>> --Graeme McRae
>>> Palmdale, CA
>>>
>>> On Fri, Aug 26, 2016 at 11:55 AM, Charles Greathouse <
>>> charles.greathouse at case.edu> wrote:
>>>
>>> I also haven't found a good way of discovering which prime signatures
>>> are
>>>> in the sequence. In principle this is combanatorial but I don't know of
>>>> a
>>>> good algorithm.
>>>>
>>>> Charles Greathouse
>>>> Case Western Reserve University
>>>>
>>>> On Fri, Aug 26, 2016 at 7:17 AM, Don Reble <djr at nk.ca> wrote:
>>>>
>>>> > A026477... a(1) = 1, a(2) = 2, a(3) = 3; and for n > 3,
>>>> >> a(n) = smallest number > a(n-1) and not of the form a(i)*a(j)*a(k)
>>>> >> for 1 <= i < j < k < n.
>>>> >>
>>>> >> It seems that if two numbers have the same prime signature (multiset
>>>> >> of
>>>> >> prime exponents) then either both or neither are in the sequence,
>>>> >> but
>>>> >> I
>>>> >> can't prove this.
>>>> >>
>>>> >
>>>> > Just do strong induction on the number of prime factors (sum of
>>>> > signature exponents).
>>>> >
>>>> > ... prime powers p^r can only be r = {1,2,4,8,15,22...}, ...
>>>> >>
>>>> >
>>>> > Yes: A026474.
>>>> > Also, square-free numbers have 3n+1 prime factors.
>>>> >
>>>> > This suggests that A026477 intersect A025487 (least value of each
>>>> > signature) would be a worthy sequence. But I don't see how to
>>>> > easily
>>>> > recognize those signatures.
>>>> >
>>>> > value signature
>>>> > 1:
>>>> > 2: 1
>>>> > 4: 2
>>>> > 16: 4
>>>> > 120: 3 1 1
>>>> > 210: 1 1 1 1
>>>> > 216: 3 3
>>>> > 256: 8
>>>> > 384: 7 1
>>>> > 2880: 6 2 1
>>>> > 6300: 2 2 2 1
>>>> > 7200: 5 2 2
>>>> > 15360: 10 1 1
>>>> > 15552: 6 5
>>>> > 26880: 8 1 1 1
>>>> > 27648: 10 3
>>>> > 32768: 15
>>>> > 49152: 14 1
>>>> > 73728: 13 2
>>>> > 83160: 3 3 1 1 1
>>>> > 120120: 3 1 1 1 1 1
>>>> > 189000: 3 3 3 1
>>>> > 510510: 1 1 1 1 1 1 1
>>>> > 921600: 12 2 2
>>>> > 1399680: 7 7 1
>>>> > 1966080: 17 1 1
>>>> > 2365440: 11 1 1 1 1
>>>> > 2822400: 8 2 2 2
>>>> > 2985984: 12 6
>>>> > 3440640: 15 1 1 1
>>>> > 4194304: 22
>>>> > 4860000: 5 5 4
>>>> > 5670000: 4 4 4 1
>>>> > 6291456: 21 1
>>>> > 6912000: 11 3 3
>>>> > 9437184: 20 2
>>>> > 10644480: 10 3 1 1 1
>>>> > 15375360: 10 1 1 1 1 1
>>>> > 60466176: 10 10
>>>> > 65345280: 8 1 1 1 1 1 1
>>>> > 71663616: 15 7
>>>> > 117964800: 19 2 2
>>>> > 127401984: 19 5
>>>> > 161243136: 13 9
>>>> > 251658240: 24 1 1
>>>> > 251942400: 9 9 2
>>>> > 302776320: 18 1 1 1 1
>>>> > 361267200: 15 2 2 2
>>>> > 440401920: 22 1 1 1
>>>> > 536870912: 29
>>>> > 805306368: 28 1
>>>> > 892371480: 3 1 1 1 1 1 1 1 1
>>>> > 1109908800: 6 2 2 2 2 1
>>>> > 1207959552: 27 2
>>>> > 1327104000: 17 4 3
>>>> > 1968046080: 17 1 1 1 1 1
>>>> > 4232632320: 11 10 1 1
>>>> > 6469693230: 1 1 1 1 1 1 1 1 1 1
>>>> > 9172942848: 22 7
>>>> > 9932482560: 11 1 1 1 1 1 1 1
>>>> > 10883911680: 12 12 1
>>>> > 12570798240: 5 5 1 1 1 1 1 1
>>>> > 13759414272: 21 8
>>>> > 13783770000: 4 4 4 1 1 1 1
>>>> > 15330615300: 2 2 2 2 2 2 1
>>>> > 16307453952: 26 5
>>>> > 23279477760: 10 10 1 1 1
>>>> > 24461180928: 25 6
>>>> > 32212254720: 31 1 1
>>>> > 32248627200: 16 9 2
>>>> > 38755368960: 25 1 1 1 1
>>>> > 39729690000: 4 4 4 3 1 1
>>>> > 56371445760: 29 1 1 1
>>>> > 68719476736: 36
>>>> > 103079215104: 35 1
>>>> > 114223549440: 10 1 1 1 1 1 1 1 1
>>>> > 154618822656: 34 2
>>>> > 156728328192: 15 14
>>>> > 169869312000: 24 4 3
>>>> > 251909898240: 24 1 1 1 1 1
>>>> > 408410100000: 5 5 5 5
>>>> > 717001084800: 7 2 2 2 2 1 1 1
>>>> > 812665405440: 17 11 1 1
>>>> > 828120733440: 8 1 1 1 1 1 1 1 1 1
>>>> >
>>>> > --
>>>> > Don Reble djr at nk.ca
>>>> >
>>>> >
>>>> >
>>>> > --
>>>> > Seqfan Mailing list - http://list.seqfan.eu/
>>>> >
>>>>
>>>> --
>>>> Seqfan Mailing list - http://list.seqfan.eu/
>>>>
>>>>
>>> --
>>> Seqfan Mailing list - http://list.seqfan.eu/
>>>
>>>
>> --
>> Seqfan Mailing list - http://list.seqfan.eu/
>>
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>
More information about the SeqFan
mailing list