[seqfan] Re: The discriminator of a sequence

[M. F. Hasler]

Dear Neil & SeqFans,

Here is self-explaining PARI code to compute the discriminator D[s] of a
sequence s given as a vector:

D(s,a=1)=vector(#s,n,my(S=s[1..n]);while(#Set(S%a)<n,a++);a)

The above omits the initial 0, one could use D0(s)=concat(0,D(s))
to compute the sequence of discriminators including the initial 0.

D( vector(20,k,k^2)) \\ this is A016726
[1, 2, 6, 9, 10, 13, 14, 17, 19, 22, 22, 26, 26, 29, 31, 34, 34, 37, 38, 41]

The following code can be used to compute the first nMax terms of the
discriminator sequence of a sequence s given as a function:

A192420(nMax, s=n->n^4)={my(S=[], a=1); vector(nMax, n, S=concat(S, s(n));
while(#Set(S%a)<n, a++); a)}

- M.

On Wed, May 4, 2016 at 2:45 AM, Olivier Gerard <olivier.gerard at gmail.com>
wrote:

> Dear Neil,
>
> The OEIS has the original sequence and a ref to the original 1985 article
> for the discriminator
>
> A016726   Smallest k such that 1, 4, 9, ..., n^2 are distinct mod k.
>
> as well as two immediate similar sequences
>
> A192419 <http://oeis.org/A192419> for cubes
> A192420 <http://oeis.org/A192420> for fourth powers
>
> described in a further article by other authors.
>
> The search engine makes it difficult to find references for the
> discriminator as it is
> converted into the keyword "discriminant" which is quite frequent.
>
> Here is some code in "Wolfram Language"
>
> Clear[Discriminator];
>
> Discriminator[kl_: {__Integer}] :=
>  Module[{dn, sl, mn}, dn = 1;
>    Table[ sl = Abs[Take[kl, i]]; mn = Max[sl];
>     While[dn <= mn + 1 && Length[Union[Mod[sl, dn]]] < i, dn++];
>     dn, {i, 1, Length[kl]}]] /; (Sort[Abs[kl]] == Union[Abs[kl]])
>
>
> it computes the discriminator of a sequence of integers
> (but it cannot contain any duplicate).
>
> The Discriminator of odious numbers is
>
> A062383 <http://oeis.org/A062383>
>
> 1, 2, 4, 4, 8, 8, 8, 8, 16, 16, 16, 16, 16, 16, 16, 16, 32, 32, 32,...
>
> but we need to make a comment about it.
>
> The Discriminator of evil numbers starts
>
> 1, 2, 4, 4, 7, 8, 8, 8, 13, 16, 16, 16, 16, 16, 16, 16, 31, 32,
>
> but is not in the OEIS.
>
> Another related transform is the compressed or reduced version of the
> Discriminator
> and its change index for sequences who stay with the same modulo
> for quite some time.
>
> The compressed Discriminator of odious numbers as well as (n choose 2)
> is just the powers of 2 and the one for factorial is
>
> 1, 2, 3, 7, 10, 13, 31, 37, 61, 83, 127, 179, 193, 277, 383, 479, 541, 641,
> 877, ...
>
> (not in the OEIS)
>
> and for 2^n -1  or  2^n+1  is
>
> 1, 3, 5, 9, 11, 13, 19, 25, 29, 37, 53, 59, 61, 67, 83, 101, ...
>
> and seems to be A139099 <http://oeis.org/A139099>
>
> for 3^n-1 or 3^n+1
>
> 1, 4, 5, 7, 17, 19, 25, 29, 31, 43, 53, 79, 89, 101, ...
>
> (not in the OEIS)
>
> The Discriminator for integer partitions with distinct parts is
>
> 1, 3, 4, 4, 5, 6, 7, 8, 10, 12, 14, 17, 20, 24, 29, 34, 40, 48, 56,
> 66, 78, 91, 106, 124, 144, 167, 194, 224, 258, 298, ...
>
> (not in the OEIS)
>
> and the compressed one for integer partitions is
>
> 1, 2, 3, 5, 7, 11, 16, 42, 52, 68, 80, 83, 84, 101, 116
>
> (not in the OEIS)
>
> etc.
>
>
> Olivier
>
>
> On Tue, May 3, 2016 at 6:59 PM, Neil Sloane <njasloane at gmail.com> wrote:
> >
> > Dear Seqfans,
> >
> > Michel Marcus found a very nice paper on the arXiv that gives a new
> > transformation of sequences: you take a sequence a(n) and compute its
> > discriminator and you get a new sequence!
> >
> > Sajed Haque, Jeffrey Shallit, Discriminators and k-Regular Sequences,
> > arXiv:1605.00092, 2016
> >
> > It would be interesting to see what happens when this is applied to all
> our
> > favorite sequences.
> >
> > They give a couple of examples (evil, odious numbers, etc.), but
> > I don't even know if their discriminators are in the OEIS (I didn't
> check)
> >
> > They mention the OEIS, so I added it to the web page "Works Citing the
> > OEIS" on our wiki.
> >
> > 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
>