[seqfan] Re: A098550.

Wed Dec 3 07:33:04 CET 2014

Hi All,

I think I have a proof that the sequence is a permutation, which is not too
complicated. Essentially the proof just uses the fact co-prime numbers work
similar to prime numbers.

Thm. A098550 is a permutation of the natural numbers.

It is helpful to define for sequence A098550 another sequence

a[n_] := Complement[ Range[n + 1], A098550[[1 ;; n]]  ][[ 1 ]]

which is well defined for all n, and finds the smallest integer not
included up to A09855[ n ].

After a[30] = 18 the sequence a[n] ~appears~ to fall in line with the
primes; that is, whenever a[n] changes value, it changes from one prime to
the next largest. If it is the case that

Conjecture 1. All a[n] for n > 30 are successive primes,

then it must be the case that all numbers appear because any given prime
number occurs in sequence:

Assume that all prime numbers up to the prime p[n] occur. Then all
composite numbers x up to p[n] can occur, and

x < p[n] < p[n+1]

implies that

p[?] x < p[?] p[n] < p[?] p[n+1]

where p[?] is a prime less than p[n] already occurring as a factor in the
series. There are only N[ p[?] ] ( p[n] - 1 ) such inequalities, where N[
p[?] ] is number of primes less than p[n]. After these possibilities have
been exhausted, the prime p[n] must already have occurred in the sequence
or must occur next in sequence.

Conjecture 1 remains a mystery to me, but it can be worked around involving
the values a[n].

Define four different states { N, B, C, D }:

( Using shorthand A = A098550 )

N)    A[ n -1 ],    a[ n ]       not co-prime
        A[ n ],       a[ n ]           co-prime

B)    A[ n -1 ],    a[ n ]           co-prime
        A[ n ],       a[ n ]           co-prime

C)    A[ n -1 ],    a[ n ]           co-prime
        A[ n ],       a[ n ]         not co-prime

 D)    A[ n -1 ],    a[ n ]       not co-prime
        A[ n ],       a[ n ]       not co-prime

The state transition diagram has B --> B or C, C --> D or N, D --> D or N.

Whenever the sequence reaches state N as in Next, the next element of the
sequence is A[ n + 1 ] = a[ n ] the previously missing smallest number, and
the sequence goes into some arbitrary state. Thus the sequence includes
every number as long as it never gets stuck in an B-loop or a D-loop.

Exploration of the state sequence introduces a new conjecture, which is
related to Conjecture 1:

Conjecture 2. the sequence never reaches state D.

But this conjecture does not matter because prime numbers occur throughout
the sequence and primes are co-prime to all numbers, so an infinite D-loop
cannot exist.

Recycling the logic used above let the smallest un-included number a[n] =
x, and count p[??] to equal N[ p[??] ] all the prime numbers co-prime to x
satisfying

p[??] < x < p[m].

where p[m] is the smallest prime number larger than x. The numbers p[??]
multiply together to form less than or equal to ( x-1 ) composite numbers y
satisfying

y < x,

which implies,

p[??] y < p[??] x < p[??] p[m].

If the sequence is in state B, it can move around exploring the various p[
?? ] y only until the finite set of inequalities, less than or equal to N[
p[??] ] ( x - 1 ) of them, becomes exhausted. At which point the sequence
must have somewhere included

p[??] x

Changing the state from B to C. This shows that no infinite B-loop can
exist, thus the sequence always reaches another state N, and then the
sequence always includes the next smallest un-included number.

There is one caveat related to the conjectures: practically the sequence
always reaches p[ ?? ] x, but in the proof logic, it could reach p[ ?? ]
factor[ x ]. Regardless, the state still changes from B to C, breaking the
B-Loop, etc.

As the sequence always includes the next smallest number, and never
includes a number twice, it must be a permutation of the natural numbers.

~

Please send questions or comments,
especially if you think I am somewhere in error.

Thanks,

 Brad

On Tue, Dec 2, 2014 at 10:18 PM, Neil Sloane <njasloane at gmail.com> wrote:

> I've created entries for most of the new sequences mentioned in this
> thread, and a few others.  They are all mentioned in the Cross-references
> section of A098550. See A250127 and entries A251411 onwards.
>
> I would certainly like to see the details of Bob Selcoe's proof that every
> odd number appears in A251413.
>
> We know quite a lot about the original sequence, A098550,
> including analogs of Bob's properties, but we still don't have a proof that
> it is a permutation.
>
>
> 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 Tue, Dec 2, 2014 at 12:40 PM, Antti Karttunen <
> antti.karttunen at gmail.com>
> wrote:
>
> > On Tue, Dec 2, 2014 at 3:11 PM,  <seqfan-request at list.seqfan.eu> wrote:
> >
> > > Message: 11
> > > Date: Mon, 1 Dec 2014 22:17:54 -0500
> > > From: Neil Sloane <njasloane at gmail.com>
> > > To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>
> > > Subject: [seqfan] Re: A098550.
> > > Message-ID:
> > >         <
> > CAAOnSgSR74Wq-t34ajxf3jzKV-wdJZAB0KZy05kWMvVd4tubxQ at mail.gmail.com>
> > > Content-Type: text/plain; charset=UTF-8
> > >
> > > Hans, I never thought of that. Nice.
> > >
> > > What about the following related sequences:
> > > - length of loop if you start at n
> > > - high-water mark in loop starting at n
> > >
> > > (I'm writing this without actually seeing the loops)
> > >
> > > The reason for adding these seqs to the OEIS (please!) is that if we
> keep
> > > doing this, sooner or later one of these sequences from one of these
> > > problems is going to match a sequence
> > > from one of the other problems, and we will have a remarkable theorem
> > >
> > > (or, to use Barry Cipra's phrase, if one of these fingerprints
> > > turns up in an unrelated crime scene, we will learn something!)
> >
> > I would even say: The less likely a sequence is to be related to
> > anything else, the higher its serendipity-value is, if it ever _does_
> > appear in another problem.
> >
> >
> > BTW,
> >
> > what are the deadlines when voting for A250000, and what is the
> > timespan for AMS/MAA "the best new formula/recurrence/gf competition"?
> > E.g. will any new formula added in 2014 do? Or does it have to be
> > added after the official announcement?
> >
> >
> > Best,
> >
> > Antti
> >
> >
> > >
> > > 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/
>