OEIS/Negative-Positive
Clark Kimberling defined - for example - A131388 with the following rules:
Rule 1 follows. For k >= 1, let A(k) = {a(1), …, a(k)} and D(k) = {d(1), …, d(k)}. Begin with k = 1 and nonnegative integers a(1) and d(1). Step 1: If there is an integer h such that 1 - a(k) < h < 0 and h is not in D(k) and a(k) + h is not in A(k), let d(k+1) be the greatest such h, let a(k+1) = a(k) + h, replace k by k + 1, and repeat Step 1; otherwise do Step 2. Step 2: Let h be the least positive integer not in D(k) such that a(k) + h is not in A(k). Let a(k+1) = a(k) + h and d(k+1) = h. Replace k by k+1 and do Step 1. Conjecture: if a(1) is an nonnegative integer and d(1) is an integer, then (a(n)) is a permutation of the nonnegative integers (if a(1) = 0) or a permutation of the positive integers (if a(1) > 0). Moreover, (d(n)) is a permutation of the integers if d(1) = 0, or of the nonzero integers if d(1) > 0.
Depending on the starting values a(1) and d(1), and with variations of the rules, there are several dozens of related sequences in the OEIS. There are lists of related sequences in A257705, A257883 and A257905.
List of Negative-Positive sequences
The list below tries to combine the partial lists of such sequences, and to describe the variations. The list has the following entries:
- the OEIS A-number,
- the major rule number as defined by C. Kimberling, except for "Rule 4" which he calls the "Algorithm",
- a minor rule number which gives the first constant (s = 0, 1) in Step 1 above: "... such that s - a(k) < h < 0 ...",
- a letter code for the type of the sequence:
a
for a(k),d
for d(k),in
for inverse(a(k)),cp
for positions of positive integers,cn
for positions of negative integers,d0
for positions of non-negative terms,dn
for positions of negative terms,
- the starting values a(1) and d(1).
A131388 Rule 1.1 a 1 0 A131389 Rule 1.1 d 1 0 A131390 Rule 1.1 in 1 0 A131391 Rule 1.1 cp 1 0 A131392 Rule 1.1 cn 1 0 A131393 Rule 2.1 a 1 0 A131394 Rule 2.1 d 1 0 A131395 Rule 2.1 in 1 0 A131396 Rule 2.1 cp 1 0 A131397 Rule 2.1 cn 1 0 A175007 Rule 1.1 d0 1 0 A175008 Rule 1.1 dn 1 0 A175498 Rule 4.0 a 1 0 A175499 Rule 4.0 d 0 1 A257705 Rule 1.1 a 0 0 A257706 Rule 1.0 a 0 1 A257876 Rule 1.1 a 0 2 A257877 Rule 1.1 a 0 3 A257878 Rule 1.1 a 1 1 A257879 Rule 1.0 a 2 0 A257880 Rule 1.0 d 2 0 A257881 Rule 1.0 a 2 1 A257882 Rule 1.0 a 2 2 A257883 Rule 4.0 a 0 0 A257884 Rule 4.0 a 0 1 A257885 Rule 4.0 a 0 2 A257902 Rule 4.0 d 0 2 A257903 Rule 4.0 a 0 3 A257904 Rule 4.0 d 0 3 A257905 Rule 3.1 a 0 0 A257906 Rule 3.1 a 0 1 A257907 Rule 3.1 d 0 1 A257908 Rule 3.0 a 0 2 A257909 Rule 3.0 d 0 2 A257910 Rule 3.0 a 0 3 A257911 Rule 4.0 a 2 2 A257912 Rule 4.0 d 2 2 A257915 Rule 1.1 d 0 3 A257918 Rule 1.0 d 2 2 A257980 Rule 3.1 d 0 3 A257981 Rule 3.1 a 1 1 A257982 Rule 3.1 d 1 1 A257983 Rule 3.1 a 1 2 A257985 Rule 3.1 a 2 0 A257986 Rule 3.1 a 2 1 A257987 Rule 3.1 a 2 2 A258046 Rule 3.1 a 1 0 A258047 Rule 3.1 d 1 0
Generating Perl program
The Perl program below can be used to generate all sequences of the list. It produces b-files with up to 100,000 terms rather rather quickly. The program takes parameters as described in the header. It contains the lost code portion of Rule 2 mentioned in the comment for A131393, and it implements the different variants depending on the parameter $op.
#!perl # Generate OEIS Sequence A131393 and its companions # as defined by Clark Kimberling # @(#) $Id$ # 2018-02-24, Georg Fischer #------------------------------------------------------ # C.f. list of sequences in https://oeis.org/search?q=A257705 # usage: # perl negpos.pl rule s noeis n op a1 d1 # rule = 1|2|3|4 # s = 0|1 # noeis = "131388|131389|131393|131394..." (without "A") # n = length of sequence to be generated # op = ak, dk, cp, cn, dp(positive d(K)), dn(negative d(k)), in(inverse) # a1 = starting value for a(1) # d1 = starting value for d(1) #------------------------------------------------------ # Formula (Rule 1): # a(k) = a(k-1) + d(k) # d(k) = max({s, s-1 ... 1-a(k-1)}) such that # d(k) not in d(1..k-1) and # a(k) not in a(1..k-1) # if no such d(k) exists, then # d(k) = min({1,2, ... a(k-1)}) such that # d(k) not in d(1..k-1) and # a(k) not in a(1..k-1) # s = -1 for A131388, and s = min(-1, d(k-1)) for A131393 #-------------------------------------------------------- use strict; my $rule = 1; if (scalar(@ARGV) > 0) { $rule = shift(@ARGV); } my $s = 1; if (scalar(@ARGV) > 0) { $s = shift(@ARGV); } my $noeis = ""; if (scalar(@ARGV) > 0) { $noeis = shift(@ARGV); } my $n = 1000; if (scalar(@ARGV) > 0) { $n = shift(@ARGV); } my $op = "ak"; if (scalar(@ARGV) > 0) { $op = shift(@ARGV); } my $a1 = 1; if (scalar(@ARGV) > 0) { $a1 = shift(@ARGV); } my $d1 = 0; if (scalar(@ARGV) > 0) { $d1 = shift(@ARGV); } my $k = 1; my $ak = $a1; my $akm1 = $ak; my %aset = ($ak, $k); my $dk = $d1; my $dkm1 = $dk; my %dset = ($dk, $k); # $dk is h print "# http://oeis.org/A$noeis/b$noeis.txt:" . " table n,a(n),n=1..$n\n"; # print "# ak = $ak, dk = $dk, akm1 = $akm1, dkm1 = $dkm1 \n"; if (0) { } elsif ($op eq "ak") { print "$k $ak\n"; } elsif ($op eq "dk") { print "$k $dk\n"; } my $busy; $k ++; while ($k <= $n) { $busy = 1; if (0) { } elsif ($rule == 1 or $rule == 2) { # for A131388, A257705 et al. $dk = -1; # start downwards if ($rule == 2 and $dkm1 < 0) { # for A131393 et al. $dk = $dkm1 - 1; } while ($busy == 1 and $dk > $s - $akm1) { # downwards $ak = $akm1 + $dk; if (!defined($aset{$ak}) and !defined($dset{$dk} and $ak>0)) { $busy=0; $aset{$ak} = $k; $dset{$dk}=$k; } else { $dk --; } } # while downwards if ($busy == 1) { $dk = +1; # start upwards } while ($busy == 1 ) { # upwards $ak = $akm1 + $dk; if (!defined($aset{$ak}) and !defined($dset{$dk} )) { $busy=0; $aset{$ak} = $k; $dset{$dk}=$k; } else { $dk ++; } } # while upwards } elsif ($rule == 3) { # for A257905, 908 # print "$k $akm1 dk=$dkm1\n"; $dk = $s - $akm1 + 1; # start upwards in negative while ($busy == 1 and $dk < 0) { $ak = $akm1 + $dk; if (!defined($aset{$ak}) and !defined($dset{$dk} and $ak>0)) { $busy=0; $aset{$ak} = $k; $dset{$dk}=$k; } else { $dk ++; } } # while negative if ($busy == 1) { $dk = +1; # start upwards } while ($busy == 1 ) { # upwards $ak = $akm1 + $dk; if (!defined($aset{$akm1 - $dk}) and !defined($dset{$dk} )) { $busy=0; $aset{$ak } = $k; $dset{$dk}=$k; } else { $dk ++; } } # while upwards } elsif ($rule == 4) { # "Algorithm" for A257883 et al. $dk = $s - $ak + 1; while ($busy == 1 ) { # upwards $ak = $akm1 + $dk; if (!defined($aset{$ak}) and !defined($dset{$dk} and $ak>0)) { $busy=0; $aset{$ak} = $k; $dset{$dk}=$k; } else { $dk ++; } } # while upwards } if (0) { } elsif ($op eq "ak") { print "$k $ak\n"; } elsif ($op eq "dk") { print "$k $dk\n"; } # print "\t# ak = $ak, dk = $dk, akm1 = $akm1, dkm1 = $dkm1\n"; $akm1 = $ak; $dkm1 = $dk; $k ++; # iterate } # while $k #-------- if ($op !~ m{ak|dk}) { # output of operations other than "ak", "dk" my @ainv = sort(map { $_ = sprintf("%06d %d", $_, $aset{$_}); $_ } keys(%aset)); my @dpos = sort(map { $_ = sprintf("%06d %d", $dset{$_}, $_); $_ } keys(%dset)); # my $temp = shift(@dpos); # accounts for positions "-1" # print join("\n", @dpos) . "\n"; if (0) { } elsif ($op =~ m{in}) { $k = 0; $busy = 1; while ($busy == 1 and $k < scalar(@ainv)) { my ($j, $aj) = split(/ /, $ainv[$k]); $j += 0; # removes the leading zeroes $busy = ($j == $k + 1 ? 1 : 0); if ($busy == 1) { print "$j $aj\n"; } $k ++; } # while $k } elsif ($op =~ m{cp|dp|c0|d0}) { my $k = 0; print join("", map { my ($j, $dj) = split(/\s+/); $j = ($op =~ m{\Ac}) ? $j - 1 : $j + 0; $_ = ""; if ($dj > (($op =~ m{0}) ? -1 : 0)) { $k ++; $_ = "$k $j\n"; } $_ } @dpos) . "\n"; } elsif ($op =~ m{cn|dn}) { my $k = 0; print join("", map { my ($j, $dj) = split(/\s+/); $j = ($op =~ m{\Ac}) ? $j - 1 : $j + 0; $_ = ""; if ($dj < 0) { $k ++; $_ = "$k $j\n"; } $_ } @dpos) . "\n"; } } # other oper # https://oeis.org/wiki/User:Georg_Fischer Feb. 24, 2018
makefile
A Unix makefile
was used
- to produce the list of sequences,
- to download (once) the corresponding b-files,
- to regenerate the particular sequences and
- to compare them against the stored b-files.
Results
The trailing terms of the 2 inverse sequences A131390 and A131395 were found to be wrong, maybe because too few terms of the normal sequence were used. For A131393 and its dependants, more terms up to 1000 were computed. All other b-files showed no differences. No differences were found either during a manual check of about 1/3 of the Mathematica programs.
#!make # Check OEIS sequences defined by Clark Kimberling # @(#) $Id$ # 2018-02-26: RULE= # 2018-02-23, Georg Fischer # # c.f. listing.tmp (produced by target "listing", below) #--------------------------------- TARGET=negpos LIMIT=2000 all: rule1 rule2 rule3 rule4 #---------- # Rule 1: Step 1 downwards, Step 2 upwards rule1: np131388 np257705 np257879 np257905 np131388: 131388 131388: 131389 175007 175008 131390 131391 131392 make $(TARGET) RULE=1 S=1 NOEIS=$@ LEN=$(LIMIT) OPER=ak A1=1 D1=0 131389: make $(TARGET) RULE=1 S=1 NOEIS=$@ LEN=$(LIMIT) OPER=dk A1=1 D1=0 175007: make $(TARGET) RULE=1 S=1 NOEIS=$@ LEN=$(LIMIT) OPER=d0 A1=1 D1=0 175008: make $(TARGET) RULE=1 S=1 NOEIS=$@ LEN=$(LIMIT) OPER=dn A1=1 D1=0 131390: make $(TARGET) RULE=1 S=1 NOEIS=$@ LEN=$(LIMIT) OPER=in A1=1 D1=0 # last 11 lines of b-file are wrong 131391: make $(TARGET) RULE=1 S=1 NOEIS=$@ LEN=$(LIMIT) OPER=cp A1=1 D1=0 131392: make $(TARGET) RULE=1 S=1 NOEIS=$@ LEN=$(LIMIT) OPER=cn A1=1 D1=0 #-------- # from A257705: # a(1) d(1) (a(n)) (d(n)) # 0 0 A257705 A131389 except for initial terms # 0 1 A257706 A131389 except for initial terms # 0 2 A257876 A131389 except for initial terms # 0 3 A257877 A257915 # 1 0 A131388 A131389 # 1 1 A257878 A131389 except for initial terms # 2 0 A257879 A257880 # 2 1 A257881 A257880 except for initial terms # 2 2 A257882 A257918 # Rule 1: Step 1 downwards, Step 2 upwards np257705: 257705 257876 257877 257915 257878 257705: make $(TARGET) RULE=1 S=1 NOEIS=$@ LEN=$(LIMIT) OPER=ak A1=0 D1=0 257876: make $(TARGET) RULE=1 S=1 NOEIS=$@ LEN=$(LIMIT) OPER=ak A1=0 D1=2 257877: make $(TARGET) RULE=1 S=1 NOEIS=$@ LEN=$(LIMIT) OPER=ak A1=0 D1=3 257915: make $(TARGET) RULE=1 S=1 NOEIS=$@ LEN=$(LIMIT) OPER=dk A1=0 D1=3 257878: make $(TARGET) RULE=1 S=1 NOEIS=$@ LEN=$(LIMIT) OPER=ak A1=1 D1=1 #-------- np257879: 257706 257879 257880 257881 257882 257918 # wrong descriptions with S=1 instead of 0 257706: make $(TARGET) RULE=1 S=0 NOEIS=$@ LEN=$(LIMIT) OPER=ak A1=0 D1=1 257879: make $(TARGET) RULE=1 S=0 NOEIS=$@ LEN=$(LIMIT) OPER=ak A1=2 D1=0 257880: make $(TARGET) RULE=1 S=0 NOEIS=$@ LEN=$(LIMIT) OPER=dk A1=2 D1=0 257881: make $(TARGET) RULE=1 S=0 NOEIS=$@ LEN=$(LIMIT) OPER=ak A1=2 D1=1 257882: make $(TARGET) RULE=1 S=0 NOEIS=$@ LEN=$(LIMIT) OPER=ak A1=2 D1=2 257918: make $(TARGET) RULE=1 S=0 NOEIS=$@ LEN=$(LIMIT) OPER=dk A1=2 D1=2 #---------------------------------------------------------------- rule2: np131393 # Rule 2 like Rule 1 with different start of $dk np131393: 131393 131394 131395 131396 131397 131393: make $(TARGET) RULE=2 S=1 NOEIS=$@ LEN=$(LIMIT) OPER=ak A1=1 D1=0 131394: make $(TARGET) RULE=2 S=1 NOEIS=$@ LEN=$(LIMIT) OPER=dk A1=1 D1=0 131395: make $(TARGET) RULE=2 S=1 NOEIS=$@ LEN=$(LIMIT) OPER=in A1=1 D1=0 # last 8 lines of b-file are wrong 131396: make $(TARGET) RULE=2 S=1 NOEIS=$@ LEN=$(LIMIT) OPER=cp A1=1 D1=0 131397: make $(TARGET) RULE=2 S=1 NOEIS=$@ LEN=$(LIMIT) OPER=cn A1=1 D1=0 #---------------------------------------------------------------- # Rule 3: rule3: # echo Rule 3 #---------------------------------------------------------------- # Rule 4: upwards from lowest rule4: np257883 np257883: 257883 257884 257885 257903 175498 257905 175499 257908 257909 257910 257911 257883: make $(TARGET) RULE=4 S=0 NOEIS=$@ LEN=$(LIMIT) OPER=ak A1=0 D1=0 # A175499 except for first initial terms 257884: 175499 make $(TARGET) RULE=4 S=0 NOEIS=$@ LEN=$(LIMIT) OPER=ak A1=0 D1=1 175499: make $(TARGET) RULE=4 S=0 NOEIS=$@ LEN=$(LIMIT) OPER=dk A1=0 D1=1 257885: 257902 make $(TARGET) RULE=4 S=0 NOEIS=$@ LEN=$(LIMIT) OPER=ak A1=0 D1=2 257902: make $(TARGET) RULE=4 S=0 NOEIS=$@ LEN=$(LIMIT) OPER=dk A1=0 D1=2 257903: 257904 make $(TARGET) RULE=4 S=0 NOEIS=$@ LEN=$(LIMIT) OPER=ak A1=0 D1=3 257904: make $(TARGET) RULE=4 S=0 NOEIS=$@ LEN=$(LIMIT) OPER=dk A1=0 D1=3 175498: make $(TARGET) RULE=4 S=0 NOEIS=$@ LEN=$(LIMIT) OPER=ak A1=1 D1=0 # A175499 except for first term 257908: 257909 make $(TARGET) RULE=3 S=0 NOEIS=$@ LEN=$(LIMIT) OPER=ak A1=0 D1=2 257909: make $(TARGET) RULE=3 S=0 NOEIS=$@ LEN=$(LIMIT) OPER=dk A1=0 D1=2 257910: make $(TARGET) RULE=3 S=0 NOEIS=$@ LEN=$(LIMIT) OPER=ak A1=0 D1=3 # A257909 except for initial terms 257911: 257912 make $(TARGET) RULE=4 S=0 NOEIS=$@ LEN=$(LIMIT) OPER=ak A1=2 D1=2 257912: make $(TARGET) RULE=4 S=0 NOEIS=$@ LEN=$(LIMIT) OPER=dk A1=2 D1=2 # from A257883: # a(1) d(1) (a(n)) (d(n)) # 0 0 A257883 A175499 except for initial terms # 0 1 A257884 A175499 # 0 2 A257885 A257902 # 0 3 A257903 A257904 # 1 0 A175498 A175499 except for first term # 1 1 A257905 A175499 # 2 0 A257908 A257909 # 2 1 A257910 A257909 except for initial terms # 2 2 A257911 A257912 #-------- np257905: \ 257905 258047 \ 257906 257907 \ 257908 257909 \ 257910 257980 \ 258046 258047 \ 257981 257982 \ 257983 257909 \ 257985 258047 \ 257986 257982 \ 257987 257909 257905: 258047 make $(TARGET) RULE=3 S=1 NOEIS=$@ LEN=$(LIMIT) OPER=ak A1=0 D1=0 258047: make $(TARGET) RULE=3 S=1 NOEIS=$@ LEN=$(LIMIT) OPER=dk A1=1 D1=0 257906: 257907 make $(TARGET) RULE=3 S=1 NOEIS=$@ LEN=$(LIMIT) OPER=ak A1=0 D1=1 257907: make $(TARGET) RULE=3 S=1 NOEIS=$@ LEN=$(LIMIT) OPER=dk A1=0 D1=1 257980: make $(TARGET) RULE=3 S=1 NOEIS=$@ LEN=$(LIMIT) OPER=dk A1=0 D1=3 258046: 258047 make $(TARGET) RULE=3 S=1 NOEIS=$@ LEN=$(LIMIT) OPER=ak A1=1 D1=0 257981: 257982 make $(TARGET) RULE=3 S=1 NOEIS=$@ LEN=$(LIMIT) OPER=ak A1=1 D1=1 257982: make $(TARGET) RULE=3 S=1 NOEIS=$@ LEN=$(LIMIT) OPER=dk A1=1 D1=1 257983: make $(TARGET) RULE=3 S=1 NOEIS=$@ LEN=$(LIMIT) OPER=ak A1=1 D1=2 # 257909.112: 257985: make $(TARGET) RULE=3 S=1 NOEIS=$@ LEN=$(LIMIT) OPER=ak A1=2 D1=0 # 258047 257986: 257982 make $(TARGET) RULE=3 S=1 NOEIS=$@ LEN=$(LIMIT) OPER=ak A1=2 D1=1 # 257982.121: 257987: make $(TARGET) RULE=3 S=1 NOEIS=$@ LEN=$(LIMIT) OPER=ak A1=2 D1=2 # 257909.122: # from A257905: # a(1) d(1) (a(n)) (d(n)) # 0 0 A257905 A258047 # 0 1 A257906 A257907 # 0 2 A257908 A257909 # 0 3 A257910 A257980 # 1 0 A258046 A258047 # 1 1 A257981 A257982 # 1 2 A257983 A257909 # 2 0 A257985 A257047 # 2 1 A257986 A257982 # 2 2 A257987 A257909 #--------------------------------------------------------------- negpos: # ------------------------------------------------------- echo perl negpos.pl $(RULE) $(S) $(NOEIS) $(LEN) $(OPER) $(A1) $(D1) test -s b$(NOEIS).txt || wget http://oeis.org/A$(NOEIS)/b$(NOEIS).txt perl negpos.pl $(RULE) $(S) $(NOEIS) $(LEN) $(OPER) $(A1) $(D1) > A$(NOEIS).pn.tmp grep -Ev "^ *#" b$(NOEIS).txt | head -n $(LIMIT) > bf.tmp grep -Ev "^ *#" A$(NOEIS).pn.tmp | head -n `wc -l bf.tmp | cut -d " " -f 1` > pn.tmp # diff -w -y --width=32 bf.tmp pn.tmp || : diff -w -y --suppress-common-lines --width=32 bf.tmp pn.tmp || : #-------- # chain, c.f. http://faculty.evansville.edu/ck6/integer/unsolved.html, Problem 13 chain389: perl a1313.pl A131389 100000 > t32k.tmp perl chain389.pl t32k.tmp # no output => no counterexample up to 100000 chain394: perl a1313.pl A131394 10000 > u32k.tmp perl chain389.pl u32k.tmp # no output => no counterexample up to 10000 block389: perl block2.pl t32k.tmp block394: perl block2.pl u32k.tmp #-------- wgetall: wget http://oeis.org/A131388/b131388.txt wget http://oeis.org/A131389/b131389.txt wget http://oeis.org/A131393/b131393.txt wget http://oeis.org/A131394/b131394.txt #------------------------------------------- # get the list of relevant sequence numbers nplists: Anoeis npname npseqs Anoeis: grep -E "^[0-9]" makefile | sed -e "s/^/A/" \ | cut -b 1-7 | sort | uniq | tee $@.tmp wc $@.tmp #---- # prepare the descriptions npname: Anoeis grep -f Anoeis.tmp ../names | sort \ | sed -e "s/generated by/ /" -e "s/(in Comments) with//" \ -e "s/Sequence//i" \ -e "s/Conjectured permutation of the //" \ -e "s/conjectured permutation//" \ | cut -b 1-80 \ | tee $@.tmp wc $@.tmp #---- # compare the sequence lists to the b-files npseqs: Anoeis wgetrest grep -f $@.tmp ../stripped | sort | tee npseqs.tmp perl npseqs.pl < npseqs.tmp #---- wgetrest: Anoeis cut -b 2-7 Anoeis.tmp > noeis.tmp cat noeis.tmp | xargs -l -i{} make wget1 NOEIS={} wget1: test -s b$(NOEIS).txt || wget http://oeis.org/A$(NOEIS)/b$(NOEIS).txt #---- listing: make -s all TARGET=list1 | sort \ | sed -e "s/ ak / a /" -e "s/ dk / d /"\ | tee listing.tmp wc listing.tmp list1: echo [https://oeis.org/A$(NOEIS) A$(NOEIS)] Rule $(RULE).$(S) $(OPER) $(A1) $(D1) #---- # e.g. https://oeis.org/search?q=id:A257908&fmt=text internal: Anoeis cat Anoeis.tmp | xargs -l -i{} make intern1 ANOEIS={} intern1: test -s $(ANOEIS).int || \ wget -O $(ANOEIS).int "http://oeis.org/search?q=id:$(ANOEIS)\&fmt=text"