[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