[seqfan] Re: The discriminator of a sequence

Richard J. Mathar mathar at mpia-hd.mpg.de
Wed May 4 11:04:37 CEST 2016


In response to http://list.seqfan.eu/pipermail/seqfan/2016-May/016352.html
and http://list.seqfan.eu/pipermail/seqfan/2016-May/016353.html:
The Maple implementation looks as follows. We adopt the convention that this
starts with a zero (see 3rd line into the  code) but that is sort of artificial.

# Discriminator sequence derived from a strictly increasing sequence.
# See Haque and Shallit arXiv:1605.00092 (May 2016).
# @param L The input sequence
# @return The initial elements of the discriminator.
#   If the prameter L is not an increasing sequence, that output is the empty list.
# @since 2016-05-04
# @author R. J. Mathar
# @example with input of squares, generating A016726
# L := [seq(n^2,n=1..10)] ;
# DISCRTR(L) ;
#
# @example with input the cubes, generating A192429
# L := [seq(n^3,n=1..10)] ;
# DISCRTR(L) ;

DISCRTR := proc(L::list)
    local Ldisc, i ,n ,m, el1, el2, mworks;
    # initial discriminator list
    Ldisc := [0] ;
    # number of elements in input list
    n :=  nops(L) ;

    # Test that input is monotonic
    for i from 2 to n do
        if op(i,L) <= op(i-1,L) then
            return [] ;
        end if;
    end do:

    # compute the i'th element of the output list by considering
    # the first i elements of the input
    for i from 1 to n do
        # brute force examination of the moduli
        for m from 1 do
            mworks := true;
            # examine all ordered pairs of input sequence
            for el1 from 1 to i-1 do
                for el2 from el1+1 to i do
                    if modp(op(el1,L),m)  = modp(op(el2,L),m) then
                        mworks := false;
                        break;
                    end if;
                end do:
                if mworks = false then
                    break;
                end if;
            end do:
            # found an m that works: append to output
            if mworks then
                Ldisc := [op(Ldisc),m] ;
                break ;
            end if;
        end do:
    end do:

    return Ldisc ;
end proc:


More information about the SeqFan mailing list