[seqfan] Re: Bob Selcoe's version of the EKG and Yellowstone permutations A064413 and A098550
Bob Selcoe
rselcoe at entouchonline.net
Mon Mar 2 04:57:33 CET 2015
Hi Neil, Vladimir et. al.,
Thanks very much for the kind words.
Vladimir - A255582 was inspired by your A254077, primarily so the behaviors
could be more consonant with A098550, including a (relatively)
straightforward proof that
it's a permutation of the natural numbers. I'd be amazed if A254077 is not
a permutation - a proof undoubtedly would be quite interesting!
Neil - I was unfamiliar with the EKG sequence but certainly see your
point about the similarity between graphs; and it appears both sequences
conform to your observation in A255582 that a(n)/n tends towards 1/2, 1 and
3/2.
re: the sequences in general: please forgive my lack of familiarity with
standard
terminology, indexing and notation, but I'll try to describe some basic
things I see
happening as best I can. (Neil and Vladimir - this is what I was
trying describe several months ago with my unwieldy TABLE approach; I think
I can now provide a better description).
I'll try to be as brief and concise as possible.
When encountering a sequence that could be described as of the
"Yellowstone Type" (see A098550 and link to Applegate, et. al), it may be
helpful to analyze the behaviors from this perspective:
In all of these sequences, we start with seeds of 1 and (usually) one or two
other (generally small) numbers. a(n) is not coprime with
some prior term a(n-i) (often a(n-2)) and is the smallest number not already
appearing in the sequence, based on a specified relationship with a(n-i).
Often, a(n) is constrained by its relationship to some characteristic of an
intermediate term a(n-h) h<i (usually a(n-1)).
Given the above:
i. Let prime(k) be Pi(k).
ii. Let {P_k} be the set of numbers with smallest prime factor Pi(k). So
{P_1} contains all the even numbers, {P_2} contains all the odd multiples of
3, {P_3} contains all multiples of 5 coprime with 6, etc.
Every member of {P_k} k=1..inf is unique; therefore, the union of these
sets U is the natural numbers
> 1, and a sequence of unique terms containing all members of U is a
permutation of the natural numbers > 1.
iii-a. Let a(n) be a member of {P_k};
iii-b. Let S_a(n) be the smallest factor of a(n); and
iii-c. Let L_a(n) be the largest factor of a(n).
Thus, since a(n) is in {P_k}, S_a(n) = Pi(k).
iv. Let a(n)/S_a(n) = m.
So since a(n) and a(n-i) are not coprime, and based (typically) on the
definitional conditions of these sequences, typically we have:
v. S_a(n) <= L_a(n-i)
This means that a(n) is in {P_1} (i.e., is an even number) except when
constrained by a(n-h), or when a smaller member of {P_k} k>1 which is not
constrained by a(n-h) has not yet appeared in the sequence.
Treating a(n) as a member of {P_k} allows for ample analysis of the behavior
of these sequences. The infinite triangle T(m,k) below is a simple tool for
visualizing these behaviors as n increases (NOTE: the triangle may be
modified to reflect specific characteristics of each sequence; for example,
all terms in A251413 are odd, so the triangle for that sequence omits the
first column k=1. For present purposes let's restrict analysis to sequences
where k=1..inf.).
k 1 2 3 4 5 6 7 8 9 10
Pi(k) 2 3 5 7 11 13 17 19 23 29
1 1 1 1 1 1 1 1 1 1
2
3 3
4
5 5 5
6
7 7 7 7
8
9 9
10
11 11 11 11 11
12
13 13 13 13 13 13
14
15 15
16
17 17 17 17 17 17 17
18
19 19 19 19 19 19 19 19
20
21 21
22
23 23 23 23 23 23 23 23 23
24
25 25 25
26
27 27
28
29 29 29 29 29 29 29 29 29 29
...
Holding k constant: Pi(k)*T(m,k) {m=1..inf.} = {P_k}. All a(n) therefore
can be represented as the product of Pi(k) and a coefficient in Column k.
So for example, A255582(42) = 45 is represented by T(15,2), because S_a(42)
= 3 = Pi(2), and 45/3 = 15.
As each new term appears in the sequence, we can "cross off" the coefficient
in the triangle corresponding with a(n). So as n increases, the result is a
"ping-pong" effect where "used" terms (i.e., those which have already
appeared in the sequence) "bounce" up and down the rows, and between
columns. As coefficients are crossed off, "gaps" appear in the columns
representing "available" terms (those which have not yet appeared).
This provides for a basic visual template of sequence behavior. So for
example, in A098550, it quickly becomes apparent that the sequence is a
permutation of the natural numbers, and why: we can always potentially
select coefficients in Column 1 for a(n) except where constrained by a(n-1);
since those constraints become infinitesimal as n increases, all
coefficients in column 1 eventually get used, so the sequence is a
permutation of {P_1} (i.e., the even numbers). Consequently, in principle,
minimum S_a(n) for any a(n) then becomes 3. Thus, we can always potentially
select coefficients in Column 2, which all eventually must get used (for
similar reasons as with Column 1), so the sequence is a permutation of {P_2}
(odd multiples of 3). Accordingly, the process continues for all k>2; thus
A098550 is a permutation of the natural numbers.
So we see that while there will always be "gaps" in the sequence, it is
still ultimately such a permutation.
I hope this is clear.
While the explanation is a bit trickier for A255582, it also is a
permutation, for essentially the same reason. But for A254077, because of
the constraints imposed by A254077(n-1), the proof does not apply there.
The slightly-altered constraint in A255582(n-1) changes the sequence and
allows for a more obvious proof (or at least one that's better understood at
the moment).
I'm not sure why A255582 and the EKG sequence seem so similar. But overall,
I think conceptualizing terms as exclusive members of {P_k} can help lead to
explanations about certain sequence behaviors, generate some interesting
conjectures and point toward possible proofs for all Yellowstone-Type
sequences, including observations about prime ordering and sequence growth
in general. Triangle T(m,k) might be useful towards this end.
Perhaps this approach could shed some light on prime ordering for many of
these sequences?? the similarity between A255582 and EKG?? a proof that
A254077 is a permutation??
Best,
Bob Selcoe
--------------------------------------------------
From: "Vladimir Shevelev" <shevelev at bgu.ac.il>
Sent: Sunday, March 01, 2015 12:13 PM
To: "Sequence Fanatics Discussion list" <seqfan at list.seqfan.eu>
Subject: [seqfan] Re: Bob Selcoe's version of the EKG and Yellowstone permutations A064413 and A098550
> Dear Seqfans,
>
> I remember Bob congratulated me in co-authors' correspondence
> with A254077 he liked. However, there appeared difficulties with a proof
> that it is a permutation of the natural numbers.
> Now I am pleased to congratulate Bob who found so change of
> the definition of A254077 that such difficulties disappeared and
> the sequence A255582 became quite classic together with
> A064413 and A098550!
>
> Best regards,
> Vladimir
>
> ________________________________________
> From: SeqFan [seqfan-bounces at list.seqfan.eu] on behalf of Neil Sloane [njasloane at gmail.com]
> Sent: 28 February 2015 19:40
> To: Sequence Fanatics Discussion list
> Subject: [seqfan] Bob Selcoe's version of the EKG and Yellowstone permutations A064413 and A098550
>
> Dear Sequence Fans, Bob Selcoe recently submitted a lovely new sequence,
> A255582.
> Like A064413 (the EKG sequence) and A098550 (the Yellowstone Permutation,
> subject of our recent arXiv:1501.01669) it is a permutation of the natural
> numbers.
> The definition is closer to that of A098550, but the graph is more like
> that of A064413. It would be nice to have a better understanding of
> what is going on here!
>
> Some associated sequences are A255479, A255480, A255481, A255482,
> all of which need b-files, and A064664 (the inverse perm to the EKG
> sequence A064413) could
> use at least a 10,000-term b-file.
>
> Vladimir Shevelev's A254077 is of the same ilk, but here there is
> no proof yet that it is a permutation of the positive integers: such a
> proof is badly needed.
> The cross-references in A098550 list many other related sequences that need
> work.
>
> This is all strawberry ice-cream for anyone who likes sequences.
>
> 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
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>
More information about the SeqFan
mailing list